二叉树遍历算法的应用

1.建立二叉链表（在先序遍历基础上）

void CreateBiTree(BiTree &T){
//扫描字符序列，读入字符ch
	cin >> ch;
//(if)如果ch为字符#，表明该二叉树为空树，即T为NULL，否则(else)指向以下操作：
	if(ch=='#')
		T = NULL;
	else{
	//1.申请一个结点空间T
	T = new BiTNode;
	//2.将ch赋值给T->data
	T->data = ch;
	//3.递归创建T的左子树
	CreateBiTree(T->lchild);
	//4.递归创建T的右子树
	CreateBiTree(T->rchild);
	}
}

根据上图二叉树给出程序运行过程
(点击图片即可放大)

2.复制二叉树（在先序遍历基础上）

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

根据上图二叉树给出程序运行过程
(点击图片即可放大)

3.计算二叉树的深度（在后序遍历基础上）

int Depth(BiTree T){
	if(T==NULL)	//二叉树结点（根结点或其他结点）为空
		return 0;	//函数结束(或返回递归的上一层函数未执行的语句)
	else{
	//递归计算左子树的深度记为 m（以根结点左孩子为根的树，不包括根结点）
		m = Depth(T->lchild);
	//递归计算右子树的深度记为 n（以根结点右孩子为根的树，不包括根结点）
		n = Depth(T->rchild);
		if(m > n)	//比较左右子树深度，选择深度较大的一个
			return (m+1);	//左子树深度+根结点=二叉树深度
		else
			return (n+1);	//右子树深度+根结点=二叉树深度
	}
}

根据上图二叉树给出程序运行过程
(点击图片即可放大)