利用一个简单的菜单，通过菜单项进行选择，实现和完成如下功能：建立二叉树存储结构、求二叉树的前序遍历
发布网友
发布时间：2022-05-09 22:16
共1个回答
热心网友
时间：2023-10-24 14:29
#include<iostream.h>
class BTreeNode
{int data;
BTreeNode *lchild;
BTreeNode *rchild;
public:
friend class BTree;
BTreeNode(){data=0;lchild=NULL;rchild=NULL;};
BTreeNode &operator=(const BTreeNode&);
};
class BTree
{BTreeNode *build0(int i);
int*a;int n;
protected:
BTreeNode *root;
public:
BTree(){};
BTree(int a[],int i){this->a=a;this->n=i;root=build0(1);};
void inorder(BTreeNode *t);
void inorder1(){cout<<"中序递归遍历:"<<'\t';inorder(root);cout<<endl;};
void inorder0(BTreeNode *t);
void inorder01(){cout<<"中序非递归遍历:"<<'\t';inorder0(root);cout<<endl;};
void preorder(BTreeNode *s);
void preorder1(){cout<<"前序递归遍历:"<<'\t';preorder(root);cout<<endl;};
void preorder0(BTreeNode *q);
void preorder01(){cout<<"前序非递归遍历：";preorder0(root);}
void postorder(BTreeNode *t);
void postorder1(){cout<<"后续递归遍历："<<'\t';postorder(root);cout<<endl;};
void postorder0(BTreeNode *tree);
void postorder01(){cout<<"后序非递归遍历：";postorder0(root);cout<<endl;};
int depth(BTreeNode *t);
void depth0(){cout<<"树的层数(树高)为:"<<'\t'<<depth(root)<<endl;}
void changshu(BTreeNode*p);
void changshu1(){BTreeNode *p=root;cout<<"现在交换了左右子树！"<<endl;changshu(p);}
int leaf(BTreeNode* T);
void leaf1(){cout<<"叶子总数为："<<'\t'<<leaf(root)<<endl;}
void prnt(BTreeNode *p,int l);
void prnt(){prnt(root,n);}
};
void BTree::prnt (BTreeNode *p,int n)
{if(p!=NULL)
{prnt(p->rchild ,n+1);
for(int i=0;i<6*(n-1);i++)cout<<" ";
cout<<"..."<<p->data <<endl;
prnt(p->lchild ,n+1);
}
};
void BTree::postorder0(BTreeNode *tree)//非递归后序遍历
{
BTreeNode *p;
BTreeNode *s[100];//用一个指针数组来用作栈
int top=-1;//下标
int mack[100];//标志数组
p=tree;
do
{
while(((p->lchild)!=NULL)&&(mack[top+1]!=2))//循环 直到让p向左滑到最左子树
{
top=top+1;
s[top]=p;//每循环一次，当前结点入栈
mack[top]=1;//结点第一次入栈时，标志为1
p=p->lchild;//找最左子树
}
cout<<p->data<<'\t'; //输出末节点 //非递归后序遍历！
p=s[top];//出栈顶元素
top=top-1;//每出一个栈顶元素，下标就后退一位
while(mack[top+1]==1)//若结点是第一次出栈，则再入栈
{
top=top+1;
s[top]=p;
mack[top]=2;//结点第二次入栈时，标志为2
p=p->rchild;//访问右子树
}
}
while(top!=-1);
cout<<s[0]->data ;
};
void BTree::preorder0(BTreeNode *q) //前序非递归遍历函数
{
BTreeNode *stack[30],*p;
int top;top=0;
//for(int i=0;i<30;i++) stack[i]=new BTreeNode;
stack[top]=root;
while(top>=0)
{
while(stack[top]!=NULL)
{
p=stack[top];
cout<<p->data<<'\t';
p=p->lchild;
stack[++top]=p;
}
top--;
if(top>=0)
{
p=stack[top];
stack[top]=p->rchild;
}
}
cout<<endl;
};
void BTree::changshu(BTreeNode *p)
{
BTreeNode *temp;
if (p == NULL) return; //交换左右子树！！！！！！
temp = NULL;
temp = p ->lchild;
p->lchild = p ->rchild;
p->rchild = temp;
changshu(p ->lchild);
changshu(p ->rchild);
};
int BTree::leaf(BTreeNode *T)
{
if(T!=NULL)
if((T->lchild==NULL)&&(T->rchild==NULL))
return 1; //求叶子总数！！！！！！
else return leaf(T->lchild )+leaf(T->rchild );
else return 0;
};
int BTree::depth(BTreeNode *t)
{if (t==NULL) return NULL;
else
return ((depth(t->lchild)+1)>(depth(t->rchild )+1)?(depth(t->lchild)+1):(depth(t->rchild )+1));
};
BTreeNode &BTreeNode::operator=(const BTreeNode &obj)
{data=obj.data;
lchild=obj.lchild;
rchild=obj.rchild;
return *this;
};
BTreeNode * BTree::build0(int i)
{int r,l;BTreeNode *p;
if((i<=n)&&(a[i-1]!=NULL))
{r=2*i+1;
l=2*i; //建二叉树
p=new BTreeNode;
p->data=a[i-1];
p->lchild=build0(l);
p->rchild=build0(r);
return (p);}
else return (NULL);
};
void BTree::inorder(BTreeNode *t)
{if(t!=NULL) //中序遍历
{inorder(t->lchild);
cout<<t->data<<'\t';//用 visit？
inorder(t->rchild);
};
};
void BTree::inorder0(BTreeNode *t)
{
int top=0;
BTreeNode *stack[10],*p;
stack[top]=t;
while(top>=0)
{ //非递归中序
while(stack[top]!=NULL)
{p=stack[top]->lchild;
stack[++top]=p;}
top--;
if(top>=0)
{p=stack[top];
cout<<stack[top]->data<<'\t';
stack[top]=p->rchild;
}
};
};
void BTree::preorder(BTreeNode *s)
{if(s!=NULL)
{cout<<s->data<<'\t';
preorder(s->lchild); //前序遍历
preorder(s->rchild);};
};
void BTree::postorder(BTreeNode *t)
{if(t!=NULL)
{postorder(t->lchild );
postorder(t->rchild );
cout<<t->data<<'\t';}; //后序遍历
};
void main()
{int x=0;int b[100];int v,i;
while(x!=1){cout<<"请选择功能,第一次必须先建立二叉树！："<<endl<<"1--建立一棵二叉树"<<endl<<"2--前序遍历递归算法"<<endl<<"3--前序遍历非递归算"<<endl<<"4--中序遍历递归算法"<<endl<<"5--中序遍历非递归算法"<<endl;
cout<<"6--后序遍历递归算法"<<endl<<"7--后序遍历非递归算法"<<endl<<"8--求树高"<<endl<<"9--求叶子总数"<<endl<<"10--输出二叉树"<<endl<<"11--交换左右子树"<<endl<<"12--退出"<<endl;
cin>>x;}
cout<<"请输入二叉树个数："<<endl;cin>>v;cout<<"请从逐层左到右输入二叉树:"<<endl;for(i=0;i<v;i++)cin>>b[i];cout<<"输入完成";BTree a(b,v);
while (x!=12)
{
switch(x)
{
case 2:a.preorder1 ();break;
case 3:a.preorder01();break;
case 4:a.inorder1();break;
case 5:a.inorder01();break;
case 6:a.postorder1();break;
case 7:a.postorder01();break;
case 8:a.depth0();break;
case 10:a.prnt();break;
case 9:a.leaf1();break;
case 11:a.changshu1();cout<<"交换完成！";break;
case 12:cout<<"欢迎再次使用！"<<endl;return;
};
cout<<"请再次输入需要的操作：";
cin>>x;};
}
