数据结构：二叉树

实验目标：

提示

（1）以二叉树的先序序列创建二叉树的二叉链表存储结构，先序序列包含空结点

（2）用递归算法实现前序遍历二叉树，输出遍历序列

（3）用递归算法实现中序遍历二叉树，输出遍历序列

（4）用递归算法实现后序遍历二叉树，输出遍历序列

（5）用非递归算法实现中序遍历二叉树，输出遍历序列

（6）求二叉树深度，返回深度值

（7）统计二叉树结点个数，返回二叉树结点个数

（8）查找二叉树结点，在根指针为 T 的二叉树中，查找值为 x 的结点， 查找成功， p 赋值为该结点指针，返回 true；查找失败， p==NULL ，返回 false

---

实验代码

#include<bits/stdc++.h>
using namespace std;

#define TRUE         1
#define FALSE        0
#define OK           1
#define ERROR        0
#define INFEASIBLE  -1
#define OVERFLOW    -2

typedef char TElemType;

#define MAX_TREE_SIZE 100
typedef TElemType SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;

typedef struct BiNode
{
	TElemType data;
	struct BiNode *lchild, *rchild;
}*BiTree,BiNode;

void CreateBiTree(BiTree &T)
{
	char ch;
	cout<<"请输入要插入的值：";
	cin>>ch;
	cout<<endl;
	if(ch=='#') T=NULL;
	else{
		T=(BiTree)malloc(sizeof(BiNode));
		if(T==NULL){
			cout<<"分配存储空间失败！"<<endl;
			return;
		}
		T->data=ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
	return;
}

void PreOrderTraverse (BiTree T)
{
	if(T==NULL) return;
	cout<<T->data<<" ";
	PreOrderTraverse(T->lchild);
	PreOrderTraverse(T->rchild);
}

void InOrderTraverse (BiTree T)
{
	if(T==NULL) return;
	InOrderTraverse(T->lchild);
	cout<<T->data<<" ";
	InOrderTraverse(T->rchild);	
}

void PostOrderTraverse (BiTree T)
{
	if(T==NULL) return;
	PostOrderTraverse(T->lchild);
	PostOrderTraverse(T->rchild);
	cout<<T->data<<" ";
}

void InOrderTraverseNon (BiTree T)
{
	BiTree stack[MAX_TREE_SIZE],Node;
	int top=0;
	if(T==NULL) return;

	Node=T;

	while (Node != NULL || top>0){
		while(Node != NULL){
			stack[++top]=Node;
			Node=Node->lchild;
		}

		Node=stack[top--];
		cout<<Node->data<<" ";
		Node=Node->rchild;
	}
}

int Depth(BiTree T)
{
	if(T==NULL) return ERROR;
	
	char maxLeft=Depth(T->lchild);
	char maxRight=Depth(T->rchild);
	if(maxLeft>maxRight) return (1+maxLeft);
	else return (1+maxRight);
}

int Count(BiTree T)
{
	if(T==NULL) return ERROR;

	else return Count(T->lchild) + Count(T->rchild)+1;
}

bool Search(BiTree T, TElemType x, BiTree &p)
{
	if(T==NULL) return ERROR;

	if(T->data==x){
		p=T;
		return p;
	}

	if(Search(T->lchild,x,p)) return Search(T->lchild,x,p);
	else return Search(T->rchild,x,p);
}

int main()
{
	BiTree T;
	while(1){
		cout<<endl;
		cout<<"**************************************************************************"<<endl;
		cout<<"**1,创建二叉树,结束输入请输入“#”                                    \t**"<<endl;
		cout<<"**2,先序遍历                                                      \t**"<<endl;
	    cout<<"**3,中序遍历                                                       \t**"<<endl;
	    cout<<"**4,后序遍历                                                       \t**"<<endl;
		cout<<"**5,以非递归函数中序遍历                                             \t**"<<endl;
		cout<<"**6,最大深度                                                        \t**"<<endl;
		cout<<"**7,节点数                                                          \t**"<<endl;
		cout<<"**8,查找值为x的结点                                                    \t**"<<endl;
		cout<<"**0,退出系统                                                         \t**"<<endl;
		cout<<"**************************************************************************"<<endl<<endl;

		int choice;
		cout<<"请输入要进行的操作：";
		cin>>choice;
		cout<<endl;

		switch(choice){
			case 1:{
				CreateBiTree(T);
				cout<<endl;
				break;
			}
			case 2:PreOrderTraverse(T);cout<<endl;break;
			case 3:InOrderTraverse(T);cout<<endl;break;
			case 4:PostOrderTraverse(T);cout<<endl;break;
            case 5:InOrderTraverseNon(T);cout<<endl;break;
			case 6:cout<<Depth(T)<<endl;cout<<endl;break;
			case 7:cout<<Count(T)<<endl;cout<<endl;break;
			case 8:{
				TElemType x;
				cout<<"请输入要查找的值：";
				cin>>x;
				cout<<endl;
				BiTree p;
				Search(T,x,p);
				cout<<"查找成功！"<<endl;
				break;
			}
			case 0:exit(0);
		}
	}
	return 0;
}