树(术语, 表示, 二叉树)

1. 树的基本术语

1.1 节点的度(Degree): 节点的字数个数
1.2 树的度: 树的所有节点中最大的度数
1.3 叶节点(Leaf): 度为0的节点
1.4 父节点(Parent): 有子树的节点是其子树的根节点或父节点
1.5 子节点(Child): 若A节点是B节点的父节点, 则称B节点是A节点的子节点，或孩子节点
1.6 兄弟节点(Sibling): 具有统一父节点的各个节点彼此是兄弟节点
1.7 路径和路径长度: 从节点N1到Nk的路径为一个节点序列N1,N2, ..., Nk，Ni是Ni-+1的父节点。路径所包含的边的个数为路径长度。
1.8 祖先节点(Ancestor): 沿树根到某一节点路径上的所有节点都是这个节点的祖先节点。
1.9 子孙节点(Descendant): 某一节点的子树中的所有节点是这个节点的子孙
1.10 节点的层次(Level): 规定根节点在1层,其他任一节点的层次是其父节点的层数加1
1.11 树的深度(Depth): 数中所有节点中的最大层次是这棵树的深度

2. 树的表示

2.1 儿子-兄弟表示法
2.2 二叉树表示
typedef struct TNode* Position;
typedef Position BinTree;     /*二叉树类型*/
struct TNode{
    ElementType Data;
    BinTree Left;        /*左子树*/
    BinTree Right;    /*右子树*/
};

3. 二叉树

二叉树T: 一个有穷的节点集合, 可以为空, 若不为空,则它是由根节点和称其为左子树Tl和右子树Tr的两个不相交的二叉树组成。二叉树的子树有左右之分。

3.1 二叉树的五种形态

3.1.1 空树
3.1.2 只有根节点
3.1.3 有根节点和左子树
3.1.4 有根节点和右子树
3.1.5 有根节点也有左右子树

3.2 特殊二叉树

3.2.1 斜二叉树 ( Skewed Binary Tree )
只有左子树或只有右子树
3.2.2 完美二叉树(Perfect Binary Tree) 满二叉树(Full Binary Tree)
所有根节点都有左右子树
3.2.3 完全二叉树(Complete Binary Tree)
有n个节点的二叉树，对书中的节点按从上到下、从左到右顺序编号, 编号为i（1<= i<=n）节点与满二叉树中编号为i节点在二叉树中位置相同

3.3 二叉树的几个重要性质

3.3.1 一个二叉树第i层的最大节点数为: 2^(i-1)，i>=1
3.3.2 深度为k的二叉树有最大节点总数为: 2^(k)-1, k>=1
3.3.3 对任何非空二叉树T, 若n0表示叶子节点的个数, n2表示度为2的非叶子节点个数, 那么两者满足关系 n0 = n2 + 1

3.4 二叉树的抽象类型定义 ADT

操作集合
Boolean IsEmpty( BinTree BT ); /*判空*/
void Traversal( BinTree BT ); /*遍历, 按某顺序访问每个节点*/
BinTree CreateBinTree(); /*创建二叉树*/
常用的遍历法:
void PreOrderTraversal( BinTree BT );/*先顺 -- 跟、左子树、右子树*/
void InOrderTraversal( BinTree BT ); /*中序--左子树、跟、右子树*/
void PostOrderTraversal( BinTree BT );/*后序--左子树、右子树、跟*/
void LevelOrderTraversal( BinTree BT );/*层次遍历, 从上到下、从左到右*/

3.5 二叉树的存储结构

3.5.1 顺序存储结构
完全二叉树: 按从上到下、从左到右顺序存储n个节点的完全二叉树的节点关系:
(1) 非根节点(序号i>1)的父节点的序号是 i/2 的下取整
(2) 节点(序号为i)的左孩子节点的序号是 2i, (若 2i<=n 则没有左孩子)
(3) 节点(序号为i)的右孩子节点的序号是 2i+1 (若2i+1<=n 则没有有孩子)
一般二叉树也可以采用这种结构，但会造成空间浪费
3.5.2 链表存储
typedef struct TreeNode* BinTree;
typedef BinTree Position;
struct TreeNodeP{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

3.6 二叉树的递归遍历

3.6.1 先序遍历
void PreOrderTraversal( BinTree BT )
{
	if( BT )
	{
		printf("%d ", BT->Data);
		PreOrderTraversal( BT->Left );
		PreOrderTraversal( BT->Right );
	}
}

3.6.2 中序遍历
void InOrderTraversal( BinTree BT )
{
	if (BT){
		InOrderTraversal( BT->Left );
		printf("%d ", BT->Data);
		InOrderTraversal( BT->Right );
	}
}

3.6.3 后序遍历
void PostOrderTraversal( BinTree BT )
{
	PostOrderTraversal( BT->Left );
	PostOrderTraversal( BT->Right );
	printf("%d ", BT->Data);
}

3.7 二叉树的非递归遍历

非递归遍历实现的基本思路: 使用堆栈

3.7.1 中序遍历的非递归算法
(1) 遇到一个节点，就把它压栈，并去遍历它的左子树
(2) 当左子树遍历结束后, 从栈顶弹出这个节点并访问它
(3) 然后按其右指针再去中序遍历该节点的右子树

void InOrderTraversal( BinTree BT )
{
	BinTree T=BT;
	Stack S = CreateStack( MaxSize ); /*创建并初始化堆栈*/
	whlie (T || !IsEmptyStack(S)){
		while (T){ /*一直向左并将沿途节点压入堆栈*/
			Push(S, T);
			T = T->Left;
		}
		if( !IsEmpty(S) ){
			T = Pop(S);/*节点弹出*/
			printf("%d", T->Data);/*访问节点*/
			T = T->Right;/*转向右子树*/
		}
	}
}

3.7.2 先序遍历的非递归算法

void InOrderTraversal( BinTree BT )
{
	BinTree T = BT;
	Stack S = CreateStack( MaxSize );
	while(T || !IsEmpty(S)){
		Push(S, T);
		printf("%d", T->Data);
		T = T->Left;
	}
	if (!IsEmpty(S)){
		T = Pop(S);
		T = T->Right;
	}
}

3.8 层次遍历

二叉树遍历的核心问题：二维结构的线性化
队列实现：遍历从根节点开始，首先将根节点入队，然后开始执行循环：节点出队、访问该节点、其左右儿子入队。层序遍历基本过程： 先是根节点入队，然后
(1) 从队列中取出一个元素
(2) 访问该元素节点
(3) 若该元素所指节点的左、右孩子节点非空，则将其左、右孩子的指针顺序入队。

void LevelOrderTraversal( BinTree BT )
{
	Queue Q;
	BinTree T;
	if( !BT ) return; /*空树直接返回*/
	Q = CreateQueue( MaxSize );
	AddQ( Q, BT );
	while ( !IsEmptyQ( Q ) ){
		T = DeleteQ( Q );
		printf("%d", T->Data); /*访问出队元素*/
		if( T->Left )
			AddQ(Q, T->Left);
		if( T->Right )
			AddQ(Q, T->Right);
	}
}

3.9 二叉树遍历的应用

3.9.1 输出二叉树的叶子节点

void PreOrderPrintLeaves( BinTree BT )
{
	if( BT ){
		if ( !BT->Left && !BT->Right ) /*左右子树为空就是叶子节点*/
			printf("%d", BT->Data);
		PreOrderPrintLeaves( BT->Left );
		PreOrderPrintLeaves( BT->Right );
	}
}

3.9.2 求二叉树的高度
二叉树的高度 = max( H左, H右 ) + 1

int PostOrderGetHeight( BinTree BT )
{
	int HL, HR, MaxH;
	if( BT ) {
		HL = PostOrderGetHeight( BT->Left );
		HR = PostOrderGetHeight( BT->Right );
		MaxH = (HL > HR) ? HL : HR;/*取左右子树较大的深度*/
		return ( MaxH + 1 );/*返回树的深度*/
	}
	else
		return 0; /*空树深度为0*/
}

3.9.3 二元运算表达树
（1）先序遍历得到前缀表达式
（2）中序遍历得到中缀表达式
（3）后序遍历得到后缀表达式
3.9.4 由两种遍历序列确定二叉树
（1）先序和中序遍历序列确定一颗二叉树
[1] 根据先序遍历序列第一个节点确定根节点
[2] 根据根节点在中序遍历序列中分割出左右子序列
[3] 对左子树和右子树分别递归使用相同的方法继续分解
（2）类似地，后序和中序遍历也可以确定一颗二叉树

3.10 二叉树的同构

给定两颗树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是"同构"的。

bool IsOmorphic( BinTree BT1, BinTree BT2 )
{
	if( (BT1==NULL) && (BT2==NULL) ) /*两颗空树同构*/
		return true;
	if ( ((BT1==NULL) && (BT2!=NULL)) || ((BT1!=NULL) && (BT2)==NULL) )
		return false; /*一空一非空，不同构*/
	if ( BT1->Data != BT2->Data ) /*根值不同*/
		return false;

	if ( IsOmorphic(BT1->Left, BT2->Left) )
	{
		return IsOmorphic(BT1->Right, BT2->Right);
	}
	else
	{
		if ( IsOmorphic(BT1->Left, BT2->Right) )
			return IsOmorphic(BT1->Right, BT2->Left);
		else
			return false;
	}
}