#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
#define MAXSIZE 32 //最多结点数,五层完全二叉树结点数为31
int selfNum = 0; //记录递归函数调用的次数,第一次调用则该次建立的结点为根结点
int nodeNum = 0; //结点数初始化为0
typedef struct bitnode //binary_tree_node
{
char data;
struct bitnode *lchild, *rchild; //二叉链表
}bitnode, *bitree; //binary_tree
bitree root, root2; //根结点指针
/*bitree creatbitree()
{ //按先序序列输入结点,输入#表示空,建立二叉树的二叉链表.递归算法.
bitree T = (bitree)malloc(sizeof(bitnode));
char ch;
cout<<"请按先序输入结点的值:"<<endl<<"(当某一非空结点的下一结点为空时,需为该空结点输入#)"<<endl;
cin>>ch;
if(ch=='#')
T=NULL;
else
{
T->data=ch;
T->lchild=creatbitree();
T->rchild=creatbitree();
}
if (selfNum == 0)
{
root = T;
}
selfNum++;
return T;
}
*/
void creatbitree2(bitree &t)
{ //按先序序列输入结点,输入#表示空,建立二叉树的二叉链表.递归算法.
char ch;
t=(bitree)malloc(sizeof(bitnode));
cout<<"请按先序输入结点的值:"<<endl<<"(当某一非空结点的下一结点为空时,需为该空结点输入#)"<<endl;
cin>>ch;
if(ch=='#')
t=NULL;
else
{
t->data=ch;
creatbitree2(t->lchild);
creatbitree2(t->rchild);
}
if (selfNum == 0)
{
root2 = t;
}
selfNum++;
}
void creattree(bitree &t,char *str)
{ //通过输入广义表构造二叉树
bitree p=0,stack[MAXSIZE]; //简易堆栈用stack[]数组表示,最多32元素
int j=0,k,top=-1; //初始化,top指向栈顶
char ch=str[j];
t=0;
while(ch)
{
switch(ch)
{
case '(': //表示下一结点为p的左孩子
stack[++top]=p; //进栈,Push
k=1;
break;
case ',': //表示下一结点为p的右孩子
k=2;
break; //
case')': //表示下一结点不再是p的孩子
top--; //出栈,栈顶指针减1
break;
default:
p=(bitree)malloc(sizeof(struct bitnode));
p->data=ch;
p->lchild=p->rchild=0;
if(t==0)
t=p;
else
{
switch(k)
{
case 1:
stack[top]->lchild=p; //getTop
break;
case 2:
stack[top]->rchild=p; //getTop
break;
}
}
}
ch=str[++j];
}
cout<<"通过广义表"<<str<<"成功建立二叉树"<<endl;
}
void preorder(bitree t)
{ //先序遍历二叉树的递归算法
//if(!t)
// return;
//else
if(t)
{
cout<<t->data<<" ";
preorder(t->lchild);
preorder(t->rchild);
}
}
void inorder(bitree t)
{ //中序遍历二叉树的递归算法
if(!t)
return ;
else
{
preorder(t->lchild);
cout<<t->data<<" ";
preorder(t->rchild);
}
}
void postorder(bitree t)
{ //后序遍历二叉树的递归算法
if(!t)
return;
else
{
postorder(t->lchild);
postorder(t->rchild);
cout<<t->data<<" ";
}
}
void preorder2(bitree t)
{ //先序遍历二叉树的非递归算法.
bitree stack[MAXSIZE],p; //简易堆栈用stack[]数组表示,最多32元素
int top=-1; //初始化,top指向栈顶
cout<<"先序序列(非递归):"<<endl;
stack[++top]=t; //根结点入栈,Push
while(top>=0)
{
p=stack[top--]; //弹出一个元素,Pop
cout<<p->data<<" "; //输出该元素的值
if(p->rchild)
stack[++top]=p->rchild; //该元素的右孩子入栈,Push
if(p->lchild)
stack[++top]=p->lchild; //该元素的左孩子入栈,Push
}
cout<<endl;
}
void inorder2(bitree t)
{ //中序遍历二叉树的非递归算法.
bitree stack[MAXSIZE],p; //简易堆栈用stack[]数组表示,最多32元素
int top=-1; //初始化,top指向栈顶
cout<<"中序序列(非递归):"<<endl;
p=t;
while(p || top >= 0)
{
if(p)
{
stack[++top]=p; //入栈,Push
p=p->lchild;
}
else
{
p=stack[top--]; //出栈,Pop
cout<<p->data<<" ";
p=p->rchild;
}
}
cout<<endl;
}
void postorder2(bitree t)
{//后序遍历二叉树的非递归算法
bitree stack[MAXSIZE],p;
int tag[MAXSIZE],top=-1;
cout<<"后序序列(非递归):"<<endl;
p=t;
while(p || top >=0)
{
if(p)
{
stack[++top]=p;
p=p->lchild;
tag[top]=0;
}
else
{
if((top>=0)&&(tag[top]==1))
{
cout<<stack[top]->data<<" ";
top--;
}
else
{
p=stack[top];
p=p->rchild;
tag[top]=1;
}
}
}
}
void nodestree(bitree t,int &i)
{ //递归计算二叉树结点数
if(t) {
// return;
i++;
nodestree(t->lchild,i);
nodestree(t->rchild,i);
}
}
int depth(bitree t)
{ //递归计算二叉树的深度
int lchilddep,rchilddep;
if(t==0)
return 0;
else
{
lchilddep=depth(t->lchild);
rchilddep=depth(t->rchild);
if(lchilddep>rchilddep)
return (lchilddep+1);
else
return (rchilddep+1);
}
}
int countleaf(bitree t)
{//递归计算叶子结点的个数
if(t==0) return 0;
else if((t->lchild==0)&&(t->rchild==0) )
return 1;
else return countleaf(t->lchild)+countleaf(t->rchild);
}
int countdegreeone(bitree t)
{//递归计算树中度数为1的结点的个数
if((t==0)||((t->lchild==0)&&(t->rchild==0)))
return 0;
else if(((t->lchild!=0)&&(t->rchild==0) )||((t->lchild==0)&&(t->rchild!=0)))
return 1;
else return countdegreeone(t->lchild)+countdegreeone(t->rchild);
}
void destroytree(bitree t)
{ //递归销毁二叉树
if(t)
{
destroytree(t->lchild);
destroytree(t->rchild);
free(t);
t=0;
}
}
void main()
{ //验证上述函数是否正确的主函数
bitree t;
int n=-1;
cout<<" 0.退出"<<endl;
cout<<" 1.按先序扩展序列建立二叉树"<<endl;
cout<<" 2.通过输入广义表构造二叉树"<<endl;
cout<<" 3.先序遍历二叉树的递归算法"<<endl;
cout<<" 4.中序遍历二叉树的递归算法"<<endl;
cout<<" 5.后序遍历二叉树的递归算法"<<endl;
cout<<" 6.先序遍历二叉树的非递归算法"<<endl;
cout<<" 7.中序遍历二叉树的非递归算法"<<endl;
cout<<" 8.后序遍历二叉树的非递归算法"<<endl;
cout<<" 9.递归计算二叉树结点数"<<endl;
cout<<" 10.递归计算叶子结点的个数"<<endl;
cout<<" 11.递归计算树中度数为1的结点的个数"<<endl;
cout<<" 12.递归销毁二叉树"<<endl;
while(n!=0)
{
cout<<"请输入序号:";
cin>>n;
switch (n)
{
case 1:creatbitree2(t);
cout<<"成功按先序扩展序列建立二叉树"<<endl<<endl;break;
case 2:creattree(t,"a(b(,x),c(,d))");
cout<<endl<<endl;break;
case 3:cout<<"先序序列(递归):"<<endl;
preorder(t);
cout<<endl<<endl;break;
case 4:cout<<"中序序列(递归):"<<endl;
inorder(t);
cout<<endl<<endl;break;
case 5:cout<<"后序序列(递归):"<<endl;
postorder(t);
cout<<endl<<endl;break;
case 6:preorder2(t);
cout<<endl;break;
case 7:inorder2(t);
cout<<endl;break;
case 8:postorder2(t);
cout<<endl<<endl;break;
case 9:nodestree(t, nodeNum);
cout<<"该树的总结点数为:"<<nodeNum<<endl<<endl; break;
case 10:cout<<"该树的深度为:"<<depth(t)<<endl<<endl;break;
case 11:cout<<"该树的度数为1的叶子结点个数为:"<<countdegreeone(t)<<endl<<endl;break;
case 12:destroytree(t);
cout<<"该树已被成功销毁"<<endl<<endl;break;
//default :cout<<"您输入的序号不正确!"<<endl<<endl;break;
}
}
//getch();
}
评论0