数据结构——二叉树

二叉树的遍历算法：前序算法，中序算法、后序算法

 1 //中序遍历非递归遍历算法 
 2 void InOrderTraversal(BinTree BT) 
 3 {
 4     BinTree T=BT;
 5     Stack S=CreatStack(MaxSize);//创建并初始化堆栈S
 6     while(T||!IsEmpty(S)){
 7         while(T){//一直向左并将沿途节点压入栈堆 
 8             Push(S,T);//第一次碰到该节点 
 9             T=T->Left;
10         }
11         if(!IsEmpty(S)){
12             T=Pop(S);//节点弹出堆栈 ，（第二次碰到该节点） 
13             printf("%5d",T->Data);//（访问）打印节点 
14             T=T->Right;//转向右子树 
15         }
16     } 
17 }
18 
19 //先序遍历的非递归遍历算法 
20 void InOrderTraversal(BinTree BT) 
21 {
22     BinTree T=BT;
23     Stack S=CreatStack(MaxSize);//创建并初始化堆栈S
24     while(T||!IsEmpty(S)){
25         while(T){//一直向左并将沿途节点压入栈堆 
26             Push(S,T);
27             printf("%5d",T->Data);//（访问）打印节点 
28             T=T->Left;
29         }
30         if(!IsEmpty(S)){
31             T=Pop(S);//节点淡出堆栈 
32             T=T->Right;//转向右子树 
33         }
34     } 
35 }
36 
37 //后序遍历的非递归遍历算法 
38 void InOrderTraversal(BinTree BT) 
39 {
40     BinTree T=BT;
41     Stack S=CreatStack(MaxSize);//创建并初始化堆栈S
42     while(T||!IsEmpty(S)){
43         while(T){//一直向左并将沿途节点压入栈堆 
44             Push(S,T); 
45             T=T->Left;
46         }
47         if(!IsEmpty(S)){
48             T=Pop(S);//节点淡出堆栈 
49             T=T->Right;//转向右子树 
50         }
51         printf("%5d",T->Data);//（访问）打印节点 
52     } 
53 }

层序遍历

核心问题：二维结构的线性化

　　·从节点访问左右儿子

　　·访问左儿子后，右儿子节点怎么办——1.需要一个堆栈保存暂时不访问的节点2.尊出结果：堆栈、队列

队列实现：遍历总根节点开始，首先将根节点入队，然后开始执行循环：节点出队、访问该节点其左右儿子入队。

 1 //层序遍历（队列实现） 
 2 void LevelOrderTraversal(BinTree)
 3 {
 4     Queue Q;
 5     BinTree T;
 6     if(!BT) return;//若是空树直接返回
 7     Q=CreatQueue(MaxSize);//创建并初始化队列Q
 8     AddQ(Q,BT);
 9     while(!IsEmptyQ(Q)){
10         T=DeleteQ(Q);
11         printf("%d/n",T->Data);//访问取出队列的节点
12         if(T->Left) AddQ(Q,T->Left);
13         if(T->Right) AddQ(Q,Right); 
14     } 
15 }

二叉树表示算术表达式

叶子节点是树，根节点的运算符。

前序、后续：运算结果相同，但不能确定唯一的一棵树；

中序：运算结果受运算符优先级影响（可用加括号的方式解决，即每遍历前和遍历完一棵树加括号），可唯一确定一棵树。

先序和中序遍历来确定一棵二叉树

1.根据先序遍历序列第一个节点来确定根节点

2.根据根节点在中序遍历序列中分割出左右两个子序列

3.对左子树和右子树分别递归使用相同的方法继续分解

树的同构判断

树的同构：T1可通过若干次左右孩子互换变成T2，则T1与T2同构。

二叉树表示：

结构数组表示二叉树：静态链表

//结构数组表示二叉树：静态链表
#define MaxTree 10
#define ElementType char
#define Tree int
#define Null -1

struct TreeNode
{
    ElementType Element;
    Tree Left;
    Tree Right;
}T1[MaxTree],T2[MaxTree];

堆的两个特性：

结构性：用数组表示的完全二叉树

有序性：任一节点的关键字是其子树所有节点的最大值（最大堆）或最小值（最小堆）