---

二叉树的存储结构

typedef struct BiTNode
{
	char data;
	struct BiTNode* lchild,*rchild;
}BiTNode,*BiTree;

结点由存放数据元素的数据域和存放放左右孩子结点地址的指针域组成

---

一、先序遍历建立二叉链表

目的：以先序遍历的方法建立二叉链表
实现：从键盘输入，检测到“#”即设置指针为空，否则分配内存空间建立新结点，以先序遍历的方法递归建立二叉链表

void PreCreateBiTree(BiTree &T)						
{
	char ch;
	cin>>ch;
	if (ch=='#')
	{
		T=NULL;
	}
	else
	{
		T=new BiTNode;
		if(!T) cout<<"error!"<<endl;
		(T)->data=ch;
		PreCreateBiTree((T)->lchild);
		PreCreateBiTree((T)->rchild);
	}
}

---

通过先序遍历建立二叉树要求我们将没有数据的结点用“#”代替输入，输入的字符串应该是对于拼凑后的二叉树的序列

“拼凑”后的完全二叉树如图
此二叉树的先序遍历为“AB#D##C##”

二、二叉树的遍历

先序遍历

即先访问根结点，再先序遍历左子树、右子树

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;
}

即按照“左右中”的方式：先访问左子树的最深的左儿子结点，再访问左儿子的右兄弟，再访问双亲结点，以此类推。遍历结点的左子树、节点的右子树、结点本身。最后一个访问根结点。

---

三、复制二叉树

功能：将二叉树复制
实现：当T为空时新树指针为空，否则分配内存空间，将原二叉树的值赋值给新的二叉树，并递归复制左右儿子结点。

void Copy(BiTree T,BiTree &NewT)
{
	if (T==NULL)
	{
		NewT=NULL;
		return ;
	}
	else
	{
		NewT=new BiTNode;
		NewT->data=T->data;
		Copy(T->lchild,NewT->lchild);
		Copy(T->rchild,NewT->rchild);
	}
}

---

四、利用递归计算结点个数

计算结点总个数

功能：计算结点总个数
实现：若指针为空就返回0，否则返回左儿子个数加右儿子个数再加一

int CountLeaves(BiTree T)
{
	if(T==NULL) return 0;
	else 
	{
		return CountLeaves(T->lchild)+CountLeaves(T->rchild)+1;
	}
}

计算叶子结点个数

功能：计算叶子结点个数
实现：若指针为空就返回0，若当前节点左右孩子皆为空，则说明是叶子结点，返回1；遍历结点的所有子树即可。

int CountLeaves(BiTree T)
{
	if(T==NULL) return 0;
	if(T->lchild==NULL&&T->rchild==NULL) return 1;
	return CountLeaves(T->lchild)+CountLeaves(T->rchild);
}

计算非叶子结点个数

功能：计算非叶子结点个数
实现：若指针为空就返回0，若当前节点左右孩子皆为空，则说明是叶子结点，返回0，剩余则都是非叶子节点，递归过程中累加即可。

int CountNotLeaves(BiTree T)
{
	if(T==NULL) return 0;
	if(T->lchild==NULL&&T->rchild==NULL) return 0;
	return CountNotLeaves(T->lchild)+CountNotLeaves(T->rchild)+1;
}

---

五、计算二叉树高

功能：计算二叉树的深度
实现：若指针为空就返回0，否则判断左右子树深度，返回较大的一个再加一即为总树高。

int TreeDepth(BiTree T)
{
	if(T==NULL) return 0;
	else 
	{
		int n=TreeDepth(T->lchild);
		int m=TreeDepth(T->rchild);
		if (m>n) return (m+1);
		else return (n+1);
	}
}

---

六、清空二叉树

功能：将二叉链表清空
实现：从根结点开始遍历，按照后序遍历的方式依次释放结点，最后释放根结点

void ClearTree(BiTree T)
{
	if(T==NULL) return ;
	ClearTree(T->lchild);
	ClearTree(T->rchild);
	delete(T);
}

---

总结

本篇介绍了二叉树的结构和对二叉链表进行的操作

测试代码及运行实例

int main()
{
	BiTree cr,me;
	PreCreateBiTree(cr);
	PreOrderTraverse(cr);
	Copy(cr,me);
	cout<<endl;
	InOrderTraverse(me);
	cout<<endl;
	PostOrderTraverse(cr);
	cout<<endl;
	cout<<"树的深度为："<<TreeDepth(cr)<<endl;
	cout<<"结点的个数是："<<CountLeaves(cr)<<endl;
	ClearTree(cr);
	return 0;
}