binary_traverse.cpp

C++的电子教程

#include<stdio.h>
#include<stdlib.h>
#define N 13

typedef struct node
{	char data;
	struct node *left,*right;
}NODE;

//创建二叉树
NODE * btree(char *list,int pos)   //使用递归建立二叉树//
{	NODE * p;
	if(list[pos]=='#' || pos>N)  //递归的终止条件
		return NULL;
	else
	{	p=(NODE *)malloc(sizeof(NODE));
		p->data=list[pos];
		p->left=btree(list,2*pos);
		p->right=btree(list,2*pos+1);
		return p;
	}
}

//输出二叉树
void Print(NODE* b)
{	if(b!=NULL)
	{	printf("%c",b->data);
		if(b->left!=NULL || b->right!=NULL)	printf("(");
		if(b->left)
		{	Print(b->left);
			if(b->right) printf(",");
			else printf(")");
		}
		if(b->right)
		{	Print (b->right);
			printf(")");
		}
	}
}

//前序遍历（递规算法）
void Rpreorder(NODE *T)
{	if(T)
	{	printf("[%c]",T->data);
		Rpreorder(T->left);
		Rpreorder(T->right);
	}
}

//前序遍历（非递规算法）
void preorder(NODE *t)     // 前序遍历二叉树非递归算法 
{	NODE* s[N];
	int top=0;
	if(!t) return;
	while(top>=0 )
	{	while(t)
		{	printf("[%c]",t->data);
			if(t->right) 
			{
				s[top++]=t->right;  //右子树根结点进栈
				//printf("%c",s[top-1]->data);///////////////////////
			}
			t=t->left;    //继续搜索左子树
		}
		if(top>0)  t=s[--top]; //右子树根结点出栈，开始搜索右子树
		else break;
	}
}

//中序遍历（递规算法）
void Rmidorder(NODE *T)
{	if(T)
	{	Rmidorder(T->left);
		printf("[%c]",T->data);
		Rmidorder(T->right);
	}
}

//中序遍历（非递规算法）
void midorder(NODE *t)   // 中序遍历二叉树非递归算法 
{	NODE* s[N];
	int top=0;
	if(!t) return;
	while(top>=0 )
	{	while(t)
		{	s[top++]=t;  //所遇结点进栈
			//printf("%c",s[top-1]->data);  ////////////////////////
			t=t->left;   //继续搜索左子树
		}
		if(top>0)
		{	t=s[--top];  //根结点出栈
			printf("[%c]",t->data);  //访问根结点
			t=t->right;   //继续搜索右子树
		}
		else break;
	}
}

//后序遍历（递规算法）
void Rposorder(NODE *T)
{	if(T)
	{	Rposorder(T->left);
		Rposorder(T->right);
		printf("[%c]",T->data);
	}
}

//后序遍历（非递规算法）
void posorder(NODE *t)  // 后序遍历二叉树非递归算法 
{	NODE* s1[N];
	int top=0,s2[N],b;
	if(!t) return;
	while(top>=0 )
	{	while(t)
		{	s1[top]=t;	s2[top++]=1;//结点首次入栈
			//printf("%c_1",s1[top-1]->data);//////////////////////////////
			t=t->left;//遍历其左子树
		}
		if(top>0)
		{	b=s2[--top];	t=s1[top];
			if(b==1)
			{	s1[top]=t;s2[top++]=2;  //结点第二次入栈
				//printf("%c_2",s1[top-1]->data);//////////////////////////////
				t=t->right;  //遍历其右子树
			}
			else   //访问根结点
			{	printf("[%c]",t->data);
				t=NULL;
			}
		}
		else break;
	}
}

//逐层遍历
void levorder(NODE *T)
{	int head,tail;
	NODE *q[N],*p;
	q[0]=T;   //根结点入队
	head=0;	tail=1;
	while(head<tail) //队列非空时
	{	p=q[head++]; //取出当前处理结点
		printf("[%c]",p->data);  //输出当前结点的值
		if(p->left) q[tail++]=p->left;  //左子树根结点入队
		if(p->right) q[tail++]=p->right;  //右子树根结点入队
	}
}

//求二叉树的深度
int depth(NODE* b)
{	int dep1,dep2;
	if(!b) return 0;
	dep1=depth(b->left);
	dep2=depth(b->right);
	return dep1>dep2? (dep1+1):(dep2+1);
}


void main()//主函数
{
	NODE * root=NULL;
	char list[]="#ABCDEFG##HI#J";  //编号1-13 (P129)
	//char list[]="#ce#db#####a";  //编号1-11 

	root=btree(list,1);  //创建二叉树
	Print(root);printf("\n");  //输出二叉树

	printf("Tree's depth = %d",depth(root));printf("\n");   //求深度

    printf("前序遍历结点：\n"); 
	//Rpreorder(root); printf("\n");
	preorder(root); printf("\n"); 

	printf("中序遍历结点：\n"); 
	//Rmidorder(root);printf("\n");	
	midorder(root); printf("\n");

	printf("后序遍历结点：\n"); 
	//Rposorder(root);printf("\n");	
	posorder(root); printf("\n");

	printf("逐层遍历结点：\n"); 
	levorder(root);	printf("\n");
}