问题描述
- 有哪位哥哥姐姐可以帮我写下程序（关于二叉树的 或者栈）
-
那个运用c++编写两个程序，其中一个是实现二叉树（或者栈），另一个是运用二叉树（或者栈）解决实际问题。谢谢啦，实在是没搞懂。
解决方案
/**
- <!--
- File : stack.h
- Author : fancy
- Email : fancydeepin@yeah.net
- Date : 2013-02-03
- --!>
*/
#include
#include
#include
#define Element char
#define INIT_SIZE 10
#define INCREMENT_SIZE INIT_SIZE / 2
typedef struct TStack {
Element *base;
Element *top;
int size;
} *Stack;
//栈的构造器,创建空栈
void stackConstructor(Stack &stack){
stack->base = (Element *)malloc(INIT_SIZE * sizeof(Element));
if(!stack->base){
printf("n为栈分配内存空间失败!n");
exit(0);
}
stack->top = stack->base; //空栈 top == base
stack->size = INIT_SIZE;
}
//是否为空栈
bool isEmpty(Stack stack){
if(stack->top == stack->base){
return true;
}
return false;
}
//压栈
bool push(Stack &stack, Element e){
if(stack->top - stack->base >= stack->size){ //栈满
stack->base = (Element *)realloc(stack->base, (stack->size + INCREMENT_SIZE) * sizeof(Element));
if(!stack->base){
printf("n为栈扩展内存空间失败!n");
return false;
}
stack->top = stack->base + stack->size;
stack->size += INCREMENT_SIZE;
}
*stack->top++ = e;
return true;
}
//弹栈
Element pop(Stack stack){
if(isEmpty(stack)){
printf("n栈为空,弹栈操作失败!n");
return ' ';
}
return *--stack->top;
}
/**
- <!--
- File : Stack.cpp
- Author : fancy
- Email : fancydeepin@yeah.net
- Date : 2013-02-03
- --!>
*/
#include "stack.h"
int main() {
Stack stack;
stackConstructor(stack);
push(stack, 'f');
push(stack, 'a');
push(stack, 'n');
push(stack, 'c');
push(stack, 'y');
printf("%c", pop(stack));
printf("%c", pop(stack));
printf("%c", pop(stack));
printf("%c", pop(stack));
printf("%c", pop(stack));
//output[result]: ycnaf
return 0;
}
解决方案二：
C++实现二叉树的基本操作
包括 添加节点、删除节点、前序遍历、中序遍历、后续遍历、层序遍历、最大值、最小值、二叉树的高度
//Tree.h 头文件
#include
class Tree
{
private :
//节点元素类型为结构体
struct LinkNode
{
int data;
LinkNode *left;
LinkNode *right;
LinkNode(const int& dat,LinkNode *l,LinkNode *r):data(dat),left(l),right(r){}
};
LinkNode *head;//表头节点
//添加节点
void AddTreeNode(LinkNode *node,LinkNode *newNode);
//显示中序排列
void ShowCLR(LinkNode *root);
//显示前序排列
void ShowLCR(LinkNode *root);
//显示右序排列
void ShowLRC(LinkNode *root);
//高度
int Height(LinkNode *root);
public :
//添加节点
bool AddTreeNode(int data);
//显示中序排列
bool ShowCLR();
//显示前序排列
bool ShowLCR();
//显示右序排列
bool ShowLRC();
//前序排列
bool Floor();
//最小值
bool Min(int** minValue);
//最大值
bool Max(int** maxValue);
//是否是空树
bool Empty();
//高度
void Height(int** height);
~Tree()
{
delete[] head;
}
Tree()
{
head=new LinkNode(-1,NULL,NULL);
}
};
//实现文件Tree.cpp
#include "stdafx.h"
#include
#include
using namespace std ;
#include "Tree.h";
#include
//添加节点
void Tree::AddTreeNode(LinkNode *node,LinkNode *newNode)
{
if(node->data>newNode->data)
{
if(node->left==NULL)
{
node->left=newNode;
}else{
AddTreeNode(node->left,newNode);
}
}else if(node->datadata)
{
if(node->right==NULL)
{
node->right=newNode;
}else{
AddTreeNode(node->right,newNode);
}
}
}
//添加节点
bool Tree::AddTreeNode(int data)
{
LinkNode *node=new LinkNode(data,NULL,NULL);
if(head->left==NULL)
{
head->left=node;
}
AddTreeNode(head->left,node);
return true;
}
//中序遍历
void Tree::ShowCLR(LinkNode *root)
{
if(root!=NULL){
cout<data<<" ";
}
if(root->left!=NULL)
{
ShowCLR(root->left);
}
if(root->right!=NULL)
{
ShowCLR(root->right);
}
}
//中序遍历
bool Tree::ShowCLR()
{
if(Empty())
{
return false;
}
ShowCLR(head->left);
return true;
}
//前序遍历
void Tree::ShowLCR(LinkNode *root)
{
if(root->left!=NULL)
{
ShowLCR(root->left);
}
if(root!=NULL){
cout<data<<" ";
}
if(root->right!=NULL)
{
ShowLCR(root->right);
}
}
//前序遍历
bool Tree::ShowLCR()
{
if(Empty())
{
return false;
}
ShowLCR(head->left);
return true;
}
//后序遍历
void Tree::ShowLRC(LinkNode *root)
{
if(root->left!=NULL)
{
ShowLRC(root->left);
}
if(root->right!=NULL)
{
ShowLRC(root->right);
}
if(root!=NULL){
cout<data<<" ";
}
}
//后序遍历
bool Tree::ShowLRC()
{
if(Empty())
{
return false;
}
ShowLRC(head->left);
return true;
}
//最小值
bool Tree::Min(int** minValue)
{
if(Empty())
{
return false;
}
LinkNode *tmp=head->left;
while(tmp!=NULL && tmp->left!=NULL)
{
tmp=tmp->left;
}
**minValue= tmp->data;
return true;
}
//最大值
bool Tree::Max(int** maxValue)
{
if(Empty())
{
return false;
}
LinkNode *tmp=head->left;
while(tmp!=NULL && tmp->right!=NULL)
{
tmp=tmp->right;
}
**maxValue= tmp->data;
return true;
}
//判断树是否为空
bool Tree::Empty()
{
return head->left==NULL;
}
//用队列实现二叉树层序遍历
//1:添加根节点
//2:打印根节点的数据,添加根节点的子节点，弹出根节点
//3:循环第二步
bool Tree::Floor()
{
queue q;
LinkNode* cur=head->left;
q.push(head->left);
while(!q.empty())
{
cur=q.front();
cout<data<<" ";
if(cur->left!=NULL){
q.push(cur->left);
}
if(cur->right!=NULL)
{
q.push(cur->right);
}
q.pop();
}
return true;
}
//求两个数中较大的一个
int max(int a,int b)
{
if(a>b)
{
return a;
}else
{
return b;
}
}
//递归求二叉树的高度
//二叉树的高度就是左子树和右子树中较大一颗二叉树的高度
int Tree::Height(LinkNode *root)
{
if(root==NULL)
{
return 0;
}
return 1+max(Height(root->left),Height(root->right));
}
//用指向指针的指针接受二叉树的高度
void Tree::Height(int** height)
{
**height=Height(head->left);
}
#include "stdafx.h"
#include
#include
using namespace std;
#include "Tree.h"
void TreeTest() ;
int main()
{
TreeTest();
int a=0;
cin>>a;
return 0;
}
//指针类型调用属性和方法用“->” 对象类型用“.”
//变量在不需要使用的时候就要释放掉它的内存
void TreeTest()
{
Tree tree;
int a[]={1,3,6,7,8,2,4,9,10,5};
for(int i=0;i<10;i++){
tree.AddTreeNode(a[i]);
}
cout<<"-----------原始数组----------"<<endl;
for(int i=0;i<10;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<endl;
cout<<"-----------中序排列----------"<<endl;
tree.ShowCLR();
cout<<endl;cout<<endl;
cout<<"-----------前序排列----------"<<endl;
tree.ShowLCR();
cout<<endl;cout<<endl;
cout<<"-----------后序排列----------"<<endl;
tree.ShowLRC();
cout<<endl;
cout<<endl;
cout<<"-----------层序排列----------"<<endl;
cout<<endl;
tree.Floor();
cout<<endl;
int min=-1;
int *pmin=&min;
tree.Max(&pmin);
cout<<endl;
cout<<"最大值:"<<min<<endl;
cout<<endl;
tree.Min(&pmin);
cout<<"最小值:"<<min<<endl;
cout<<endl;
int h=-1;
int *height=&h;
tree.Height(&height);
cout<<"高度:"<<h<<endl;
}