【数据结构】二叉树的基本操作

根据二叉树的特性，栈式创建结构体

typedef struct BiTNode{
   char   data;
   struct  BiTNode   *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree; 
typedef struct stack_1//顺序栈
{
	tree* a[MAX];//用来存树的每一个结点
	int tag[MAX];//起标记作用，用于非递归建树和非递归后序遍历
	int top;//始终指向当前栈中元素的下一个位置，下标从零开始
}stack;

问题：

1、编写函数，创建一棵二叉树（递归算法和非递归算法）；

2、编写函数，按树状结构输出二叉树；

3、编写函数，用递归算法分别求二叉树的各种遍历序列；

算法思想阐述：

递归建树：

依次读入输入的字符序列ch，若ch是一个’#’字符，则表明该树为空树，否则：

• 申请一个结点空间T；
• 将ch赋给T->data；
• 递归创建T的左子树；
• 递归创建T的右子树；

非递归建树:

分别定义树根、左子树、右子树的结构体指针，用先序遍历的顺序分别对树根、左子树、右子树进行入栈操作，当左右子树都已建立时，进行出栈操作；

树状输出二叉树：

最直观的打印二叉树，只能用队列记录二叉树的层次遍历，并记录每个节点的层数及这层里的列数，最后再调整位置打印输出。这样的方法实现起来非常麻烦，所以本报告采用逆90度输出的方法打印二叉树。

每个节点都是独立的一行，记录当前是第几层次，根据层数控制输出位置。从最右子树开始输出，再输出根结点，最后输出左子树。

先序递归遍历：

采用递归，先判断节点是否为空，如果为空则返回。先打印当前节点内容，然后依次递归所有左子节点，再依次递归所有右子节点。

中序递归遍历：

采用递归，先判断节点是否为空，如果为空则返回。先依次递归所有左子节点，然后打印当前节点内容，再递归所有右子节点。

后序递归遍历：

采用递归，先判断节点是否为空，如果为空则返回。先依次递归所有左子节点，再递归所有右子节点，最后打印当前节点内容。

一、各函数代码如下

解题一： 

//入栈
void push(stack* st, tree* t){
	st->a[st->top] = t;
	st->top++;
}

//出栈，即删除栈顶元素，并返回指向已删除元素的指针
tree* pop(stack* st){
	if (st->top != 0)
	{
		st->top--;
		return st->a[st->top];
	}
	else
		return NULL;
}

//取栈顶元素，但不删除，返回指向栈顶元素的指针
tree* top(stack* st){
	if (st->top != 0)
	{
		return st->a[st->top - 1];
	}
	else
	{
		return NULL;
	}
}

//非递归建树
tree* NoRecursiveCreate(){
	//0---左孩子为空，1---右孩子为空，2建树完成，"#"代表空；
	stack_1 A;
	stack_1 *st;
	st = &A;
	tree *root;//树的根结点
	tree *p1, *p2;//因为根结点不能动，所有用两个移动指针，用来建树，
	int i = 0;//访问ch数组
	char ch[MAX];//存放结点的data值的字符数组。
	scanf("%s", &ch);
	st->top = 0;//栈初始化
	while (ch[i] != '\0')
	{
		if (i == 0)//建立根结点
		{
			root = (tree*)malloc(sizeof(tree));//建立根结点
			root->data = ch[i];
			root->lchild = NULL;//左右孩子都置空；
			root->rchild = NULL;
			p1 = root;//p1代替root操作，因为root不能移动。
			push(st, p1);//入栈
			st->tag[st->top - 1] = 0;//将他标记为0---左孩子为空，当然右孩子也为空，但是用不着标记，
			//因为是按照前序遍历的顺序来建树，即：根节点-左子树-右子树。先建左树

		}
		else//非根节点
		{
			if (ch[i] != '#'&&st->tag[st->top - 1] == 0)//建左树(元素非空，即输入不是"#"，并且他的标记是0)；
			{
				p2 = (tree*)malloc(sizeof(tree));//创建一个新结点
				p2->data = ch[i];
				p2->lchild = NULL;//一定要有，不然会和下面的代码冲突，可以看做是对这个结点的初始化；
				p2->rchild = NULL;
				push(st, p2);//入栈
				p1->lchild = p2;//将新创建的左孩子连接的树上
				p1 = p2;//指针下移，即：指针指向现在的左孩子。
				st->tag[st->top - 1] = 0;//标记为0，表示此节点没有左孩子
			}
			else if (ch[i] == '#'&&st->tag[st->top - 1] == 0)//左树完成
			{
				p1->lchild = NULL;
				st->tag[st->top - 1] = 1;//左子树构建完成
			}
			else if (ch[i] == '#'&&st->tag[st->top - 1] == 1)//右树完成
			{
				p1->rchild = NULL;
				st->tag[st->top - 1] = 2;//右子树构建完成，即：这课小树构建完成;
			}
			else if (ch[i] != '#'&&st->tag[st->top - 1] == 1)//建右树
			{
				p2 = (tree*)malloc(sizeof(tree));
				p2->data = ch[i];
				p2->lchild = NULL;
				p2->rchild = NULL;
				push(st, p2);
				p1->rchild = p2;
				p1 = p2;
				st->tag[st->top - 1] = 0;
			}
			while (st->tag[st->top - 1] == 2)//是否出栈操作，当左右子树都已建立时，出栈
			{
				st->tag[st->top - 1] = 0;//出栈之后，清除标记
				p1 = pop(st);//出栈
				
				if(st->top != 0)//避免最后一个节点误操作，如果没有此句，会导致栈的top越界
					p1 = top(st);//取当前的栈顶元素
				else
					break;//所有元素均已出栈，当前的栈为空
				if (st->tag[st->top - 1] == 1)//说明此时结点的左子树已存在，并且当前指针是从下一右子树返上来的结点，即：右子树也存在；
				{
					st->tag[st->top - 1] = 2;
				}
			}
			if (p1->lchild != NULL || st->tag[st->top - 1] ==1)//对返上来的结点进行判断，有左子树则改变标记为1
			{
				st->tag[st->top - 1] = 1;
			}
		}
		i++;//输入下一个元素
	}
	return root;
}

//递归先序输出非递归创建的树 
void PreprintNoRecursive(tree* t){
	tree* p1;
	p1 = t;
	if (!p1)
		return;
	else
	{
		printf("%c ", p1->data);
		PreprintNoRecursive(p1->lchild);
		PreprintNoRecursive(p1->rchild);
	}
}

//递归中序输出非递归创建的树 
void InprintNoRecursive(tree* t){
	tree* p1;
	p1 = t;
	if (!p1)
		return;
	else
	{
		InprintNoRecursive(p1->lchild);
		printf("%c ", p1->data);
		InprintNoRecursive(p1->rchild);
	}
}

//递归后序输出非递归创建的树 
void PostprintNoRecursive(tree* t){
	tree* p1;
	p1 = t;
	if (!p1)
		return;
	else
	{
		PostprintNoRecursive(p1->lchild);
		PostprintNoRecursive(p1->rchild);
		printf("%c ", p1->data);
	}
}

//递归建树 
void RecursiveCreate(BiTree &T){//按先序输入
	cin>>ch;
	if(ch =='#'){
		T = NULL; //递归结束，建空树
	}
	else{
		T = new BiTNode;
		T->data = ch; //生成根结点
		RecursiveCreate(T->lchild);  //递归创建左子树
		RecursiveCreate(T->rchild);  //递归创建右子树
	}
}

//递归先序输出递归创建的树
void PreprintRecursive(BiTree T){
	int n = 0,i;
    if(T == NULL)	return;
    printf("%c ", T->data);
    for(i = 0; i < n;i++)
        printf(" ");
    PreprintRecursive(T->lchild);
    PreprintRecursive(T->rchild);
}

//递归中序输出递归创建的树
void InprintRecursive(BiTree T){
	int n = 0,i;
    if(T == NULL)	return;
    InprintRecursive(T->lchild);
    for(i = 0; i < n;i++)
        printf(" ");
    printf("%c ", T->data);
    InprintRecursive(T->rchild);
}

//递归后序输出递归创建的树
void PostprintRecursive(BiTree T){
	int n = 0,i;
    if(T == NULL)	return;
    PostprintRecursive(T->lchild);
    for(i = 0; i < n;i++)
        printf(" ");
    PostprintRecursive(T->rchild);
	printf("%c ", T->data);
}

//树状打印二叉树:   type : 0表示根节点，１表示左节点，２表示右节点. level表示层次，用于控制显示的距离
void printTree(BiTNode *n, int type,  int level){
	int i = 0;
	if (NULL == n)
		return;
	printTree(n->rchild,2,level+1);
	switch (type)
	{
		case 0:
			printf("%2c\n", n->data);
			break;
		case 1:
			for (i = 0; i < level; i++)	
				printf("\t");
			printf("\\\n");//转义打印"\"并换行 
			for (i = 0; i < level; i++)	
				printf("\t");
			printf("  %2c\n", n->data);
	
			break;
		case 2:
			for (i = 0; i < level; i++)	
				printf("\t");
			printf(" %2c\n", n->data);
			for (i = 0; i < level; i++)	
				printf("\t");
			printf("/\n");
			break;	
	}
	printTree(n->lchild,1,level+1);
}

//构造一个选择，以实现用户交互
void Switchice(){
	BiTree T;
	int choice = 0;
	cout<<"请选择一个功能："<<endl;
	cout<<"1、递归创建二叉树      2、非递归创建二叉树"<<endl;
	scanf("%d",&choice);
	switch(choice)
	{
		case 1: cout<<"按扩展先序遍历序列建立二叉树，请输入序列(一个结点存一个字符):"<<endl;
				RecursiveCreate(T);
				cout<<"递归创建完成！"<<endl<<endl;
				cout<<"逆90°树状打印二叉树,把屏幕逆时针旋转90°食用更佳！"<<endl;
				printTree(T,0,0);
				printf("\n\n先序遍历输出：");PreprintRecursive(T); cout<<endl;
				printf("中序遍历输出：");InprintRecursive(T);  cout<<endl;
				printf("后序遍历输出：");PostprintRecursive(T);cout<<endl;
				system("pause");
				system("cls");
				Switchice();//递归实现清屏 
				break;
		case 2: tree* F;
				printf("输入一组数据(以#分隔):\n");
				F = NoRecursiveCreate();
				cout<<"非递归创建完成！"<<endl<<endl;
				cout<<"逆90°树状打印二叉树,把屏幕逆时针旋转90°食用更佳！"<<endl;
				printTree(F,0,0);
				printf("\n\n先序遍历输出：");PreprintNoRecursive(F); cout<<endl;
				printf("中序遍历输出：");InprintNoRecursive(F);  cout<<endl;
				printf("后序遍历输出：");PostprintNoRecursive(F);cout<<endl;
				system("pause");
				system("cls");
				Switchice();//递归实现清屏 
				break;
	}
}

 

解题一完整代码：

#include <iostream.h>
#include <stdlib.h>
#define MAX 100
#define OK 1
using namespace std;
typedef struct BiTNode{
   char   data;
   struct  BiTNode   *lchild,*rchild; //左右孩子指针
}BiTNode,*BiTree,tree; 
/*以下是非递归创建二叉树的各函数*/
typedef struct stack_1//顺序栈
{
	tree* a[MAX];//用来存树的每一个结点
	int tag[MAX];//起标记作用，用于非递归建树和非递归后序遍历
	int top;//始终指向当前栈中元素的下一个位置，下标从零开始
}stack;
char ch;//某些函数用到(char)ch,故在函数外规范以减少代码量


//入栈
void push(stack* st, tree* t){
	st->a[st->top] = t;
	st->top++;
}

//出栈，即删除栈顶元素，并返回指向已删除元素的指针
tree* pop(stack* st){
	if (st->top != 0)
	{
		st->top--;
		return st->a[st->top];
	}
	else
		return NULL;
}

//取栈顶元素，但不删除，返回指向栈顶元素的指针
tree* top(stack* st){
	if (st->top != 0)
	{
		return st->a[st->top - 1];
	}
	else
	{
		return NULL;
	}
}

//非递归建树
tree* NoRecursiveCreate(){
	//0---左孩子为空，1---右孩子为空，2建树完成，"#"代表空；
	stack_1 A;
	stack_1 *st;
	st = &A;
	tree *root;//树的根结点
	tree *p1, *p2;//因为根结点不能动，所有用两个移动指针，用来建树，
	int i = 0;//访问ch数组
	char ch[MAX];//存放结点的data值的字符数组。
	scanf("%s", &ch);
	st->top = 0;//栈初始化
	while (ch[i] != '\0')
	{
		if (i == 0)//建立根结点
		{
			root = (tree*)malloc(sizeof(tree));//建立根结点
			root->data = ch[i];
			root->lchild = NULL;//左右孩子都置空；
			root->rchild = NULL;
			p1 = root;//p1代替root操作，因为root不能移动。
			push(st, p1);//入栈
			st->tag[st->top - 1] = 0;//将他标记为0---左孩子为空，当然右孩子也为空，但是用不着标记，
			//因为是按照前序遍历的顺序来建树，即：根节点-左子树-右子树。先建左树

		}
		else//非根节点
		{
			if (ch[i] != '#'&&st->tag[st->top - 1] == 0)//建左树(元素非空，即输入不是"#"，并且他的标记是0)；
			{
				p2 = (tree*)malloc(sizeof(tree));//创建一个新结点
				p2->data = ch[i];
				p2->lchild = NULL;//一定要有，不然会和下面的代码冲突，可以看做是对这个结点的初始化；
				p2->rchild = NULL;
				push(st, p2);//入栈
				p1->lchild = p2;//将新创建的左孩子连接的树上
				p1 = p2;//指针下移，即：指针指向现在的左孩子。
				st->tag[st->top - 1] = 0;//标记为0，表示此节点没有左孩子
			}
			else if (ch[i] == '#'&&st->tag[st->top - 1] == 0)//左树完成
			{
				p1->lchild = NULL;
				st->tag[st->top - 1] = 1;//左子树构建完成
			}
			else if (ch[i] == '#'&&st->tag[st->top - 1] == 1)//右树完成
			{
				p1->rchild = NULL;
				st->tag[st->top - 1] = 2;//右子树构建完成，即：这课小树构建完成;
			}
			else if (ch[i] != '#'&&st->tag[st->top - 1] == 1)//建右树
			{
				p2 = (tree*)malloc(sizeof(tree));
				p2->data = ch[i];
				p2->lchild = NULL;
				p2->rchild = NULL;
				push(st, p2);
				p1->rchild = p2;
				p1 = p2;
				st->tag[st->top - 1] = 0;
			}
			while (st->tag[st->top - 1] == 2)//是否出栈操作，当左右子树都已建立时，出栈
			{
				st->tag[st->top - 1] = 0;//出栈之后，清除标记
				p1 = pop(st);//出栈
				
				if(st->top != 0)//避免最后一个节点误操作，如果没有此句，会导致栈的top越界
					p1 = top(st);//取当前的栈顶元素
				else
					break;//所有元素均已出栈，当前的栈为空
				if (st->tag[st->top - 1] == 1)//说明此时结点的左子树已存在，并且当前指针是从下一右子树返上来的结点，即：右子树也存在；
				{
					st->tag[st->top - 1] = 2;
				}
			}
			if (p1->lchild != NULL || st->tag[st->top - 1] ==1)//对返上来的结点进行判断，有左子树则改变标记为1
			{
				st->tag[st->top - 1] = 1;
			}
		}
		i++;//输入下一个元素
	}
	return root;
}

//递归先序输出非递归创建的树 
void PreprintNoRecursive(tree* t){
	tree* p1;
	p1 = t;
	if (!p1)
		return;
	else
	{
		printf("%c ", p1->data);
		PreprintNoRecursive(p1->lchild);
		PreprintNoRecursive(p1->rchild);
	}
}

//递归中序输出非递归创建的树 
void InprintNoRecursive(tree* t){
	tree* p1;
	p1 = t;
	if (!p1)
		return;
	else
	{
		InprintNoRecursive(p1->lchild);
		printf("%c ", p1->data);
		InprintNoRecursive(p1->rchild);
	}
}

//递归后序输出非递归创建的树 
void PostprintNoRecursive(tree* t){
	tree* p1;
	p1 = t;
	if (!p1)
		return;
	else
	{
		PostprintNoRecursive(p1->lchild);
		PostprintNoRecursive(p1->rchild);
		printf("%c ", p1->data);
	}
}

//递归建树 
void RecursiveCreate(BiTree &T){//按先序输入
	cin>>ch;
	if(ch =='#'){
		T = NULL; //递归结束，建空树
	}
	else{
		T = new BiTNode;
		T->data = ch; //生成根结点
		RecursiveCreate(T->lchild);  //递归创建左子树
		RecursiveCreate(T->rchild);  //递归创建右子树
	}
}

//递归先序输出递归创建的树
void PreprintRecursive(BiTree T){
	int n = 0,i;
    if(T == NULL)	return;
    printf("%c ", T->data);
    for(i = 0; i < n;i++)
        printf(" ");
    PreprintRecursive(T->lchild);
    PreprintRecursive(T->rchild);
}

//递归中序输出递归创建的树
void InprintRecursive(BiTree T){
	int n = 0,i;
    if(T == NULL)	return;
    InprintRecursive(T->lchild);
    for(i = 0; i < n;i++)
        printf(" ");
    printf("%c ", T->data);
    InprintRecursive(T->rchild);
}

//递归后序输出递归创建的树
void PostprintRecursive(BiTree T){
	int n = 0,i;
    if(T == NULL)	return;
    PostprintRecursive(T->lchild);
    for(i = 0; i < n;i++)
        printf(" ");
    PostprintRecursive(T->rchild);
	printf("%c ", T->data);
}

//树状打印二叉树:   type : 0表示根节点，１表示左节点，２表示右节点. level表示层次，用于控制显示的距离
void printTree(BiTNode *n, int type,  int level){
	int i = 0;
	if (NULL == n)
		return;
	printTree(n->rchild,2,level+1);
	switch (type)
	{
		case 0:
			printf("%2c\n", n->data);
			break;
		case 1:
			for (i = 0; i < level; i++)	
				printf("\t");
			printf("\\\n");//转义打印"\"并换行 
			for (i = 0; i < level; i++)	
				printf("\t");
			printf("  %2c\n", n->data);
	
			break;
		case 2:
			for (i = 0; i < level; i++)	
				printf("\t");
			printf(" %2c\n", n->data);
			for (i = 0; i < level; i++)	
				printf("\t");
			printf("/\n");
			break;	
	}
	printTree(n->lchild,1,level+1);
}

//构造一个选择，以实现用户交互
void Switchice(){
	BiTree T;
	int choice = 0;
	cout<<"请选择一个功能："<<endl;
	cout<<"1、递归创建二叉树      2、非递归创建二叉树"<<endl;
	scanf("%d",&choice);
	switch(choice)
	{
		case 1: cout<<"按扩展先序遍历序列建立二叉树，请输入序列(一个结点存一个字符):"<<endl;
				RecursiveCreate(T);
				cout<<"递归创建完成！"<<endl<<endl;
				cout<<"逆90°树状打印二叉树,把屏幕逆时针旋转90°食用更佳！"<<endl;
				printTree(T,0,0);
				printf("\n\n先序遍历输出：");PreprintRecursive(T); cout<<endl;
				printf("中序遍历输出：");InprintRecursive(T);  cout<<endl;
				printf("后序遍历输出：");PostprintRecursive(T);cout<<endl;
				system("pause");
				system("cls");
				Switchice();//递归实现清屏 
				break;
		case 2: tree* F;
				printf("输入一组数据(以#分隔):\n");
				F = NoRecursiveCreate();
				cout<<"非递归创建完成！"<<endl<<endl;
				cout<<"逆90°树状打印二叉树,把屏幕逆时针旋转90°食用更佳！"<<endl;
				printTree(F,0,0);
				printf("\n\n先序遍历输出：");PreprintNoRecursive(F); cout<<endl;
				printf("中序遍历输出：");InprintNoRecursive(F);  cout<<endl;
				printf("后序遍历输出：");PostprintNoRecursive(F);cout<<endl;
				system("pause");
				system("cls");
				Switchice();//递归实现清屏 
				break;
	}
}

int main(int argc, char *argv[])
{
	Switchice(); 
	return 0;
}

分享完毕~

欢迎小伙伴们在文下评论和私信喔~