mytree.cpp

一个比较全的关于二叉树的操作的程序

#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();
}