六、二叉树的存储结构和遍历算法

顺序存储结构仅适用于完全二叉树，在最坏的情况下，一个深度为k且只有k个结点的单支树（树中不存在度为2的结点）却需要长度为2^k-1的一维数组。这造成了存储空间的极大浪费，所以对于一般二叉树，适合采用链式存储结构：

二叉链表存储结构：

typedef struct BiTNode{
	TElemType data;	//结点数据域 
	struct BiTNode *lchild,*rchild;//左右孩子指针 
}BiTNode,*Bitree;

先序创建二叉链表：

void CreateBiTree(BiTree &T)
{//先序创建二叉树T 
	cin >> ch;
	if(ch=='#')
	{//递归结束，建空树 
		T=NULL;
	} 
	else
	{
		T=new BiTNode;//生成根结点 
		T->data=ch;//根结点数据域置为ch 
		CreateBiTree(T->lchild);//递归创建左子树 
		CreateBiTree(T->rchild);//递归创建右子树 
	}
}

中序遍历二叉树：

void InOrderTraverse(BiTree T)
{//中序遍历二叉树T的递归算法 
	if(T)
	{
		InOrderTraverse(T->lchild);
		cout<<T->data;
		InOrderTraverse(T->rchild);
	 } 
 }

改变cout的位置便是先序和后续遍历二叉树

复制二叉树:

void Copy(BiTree T,BiTre &NewT)
{//复制一颗和T完全相同的二叉树 
	if(T==NULL)
	{//如果是空树,递归结束 
		NewT==NULL;
		return;
	}
	else
	{
		NewT=new BiTNode;
		NewT->data=T->data;//复制根节点 
		Copy(T->lchild,NewT->lchild);//递归复制左子树 
		Copy(T->lchild,NewT->rchild);//递归复制右子树 
	}
 }

计算二叉树的深度:

void Depth(BiTree T)
{//计算二叉树T的深度 
	if(T==NULL)
	{//如果是空树,深度为0,递归结束 
		return 0;
	}
	else
	{
		m=Depth(T->lchild);//递归计算左子树深度计为m 
		n=Depth(T->rchild);//递归计算左子树深度计为n 
		if(m>n)
		{//二叉树深度为m与n的较大者加1 
			return(m+1);
		}
		else
		{
			return(n+1); 
		}
	}
 }

统计二叉树中结点的个数:

int NodeCount(BiTree T)
{//统计二叉树T中结点的个数 
	if(T==NULL)
	{//如果是空树,则结点个数位0,递归结束。 
		return 0;
	}
	else
	{//否则结点个数为左子树结点个数+右子树结点个数+1 
		return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
	}
}