第6章樹
6.1 樹的定義
線性結構：一對一。樹形結構：一對多。圖形結構：多對多。
1、樹Tree)是n(n>=0)個節點的有限集。n=0時稱為空樹。在任意一棵非空樹中：1）有且僅有一個特定的稱為根Root）的節點；(2)當n>1時，其余節點可分為m(m>0)個互不相交的有限集T1，T2，......，Tm，其中每一個集合本身又是一棵樹，並且稱為根的子樹SubTree)。
1）數據結構中的樹只能有一個根節點。
2）子樹的個數沒有限制，但它們一定是互不相交的。
2、樹的節點包含一個數據元素及若干指向其子樹的分支。節點擁有的子樹數目稱為節點的度Degree）。度為0的節點稱為葉節點或終端節點。度不為0的節點稱為非終端節點或分支節點。除根節點外，分支節點也稱為內部節點。樹的度是樹內各節點的度的最大值。
3、節點的子樹的根稱為該節點的孩子Child)，相應的，該節點稱為孩子的雙親。同一個雙親的孩子之間合成兄弟。節點的祖先是從根到該節點所經分支上的所有節點，反之，以某節點為根的子樹中的任一節點都稱為該節點的子孫。
4、雙親在同一層次的節點互為堂兄弟。樹中節點的最大層次稱為樹的深度Depth）或高度。如果樹中節點的各子樹看成從左至右是有次序的，不能互換的，則該樹稱為有序樹，否則稱為無序樹。
5、森林Forest）是m(m>=0)棵互不相交的樹的集合。對樹中的每個節點而言，其子樹的集合即是森林。
線性結構：
1）第一個數據元素：無前驅。
2）最後一個數據元素：無後繼。
3）中間元素：一個前驅一個後繼。
樹結構：
1）根節點：無雙親，唯一。
2）葉節點：無孩子，可以有多個。
3）中間節點：一個雙親多個孩子。
6.2 樹的存儲結構
順序存儲和鏈式存儲。
6.2.1雙親表示法
除了根節點外，其余每個節點，它不一定有孩子，但是一定有且僅有一個雙親。
節點結構由一個數據域和一個指針域組成。
data
parent
data是數據域，存儲節點的數據信息。parent是指針域，存儲該節點的雙親在數組中的下標用數組存儲）。約定根節點的指針域設置為-1。
類似的還有孩子表示方法、孩子兄弟表示法。
6.3 二叉樹
6.3.1二叉樹的定義
1、二叉樹Binary Tree)是n(n>=0)個節點的有限集合，該集合或者為空集稱為空二叉樹），或者由一個根節點和兩棵互不相交的、分別稱為根節點的左子樹和有子樹的二叉樹組成。
特點：
1）每個節點最多有兩個子樹，二叉樹樹中不存在度大於2的節點。不是只有兩棵子樹，而是最多有。
2）左子樹和右子樹是有順序的。
3）即使某節點只有一棵子樹，也要區分它是左子樹還是右子樹。
2、特殊二叉樹。
1）斜樹，左斜樹、右斜樹。
2）滿二叉樹
3）完全二叉樹。
6.3.2二叉樹的性質
1、二叉樹的第i層最多有2i-1個節點。
2、深度為k的二叉樹至多有2k-1個節點。
3、對任何一個二叉樹，如果葉子節點數為n0，度為2的節點數n2，則n0=n2+1；
證明：總節點數= n0 + n1 + n2；總節點數 = 總分支數 + 1；總分支數 = n1 + 2n2;
得到n0 = n2 + 1;
4、具有n個節點的完全二叉樹的深度為[log2n] + 1。
5、如果對一棵有n個節點的完全二叉樹其深度為[log2n] + 1）的節點按層序標號，對任一節點i(1<=i<=n)有：
1）如果i=1，則節點是二叉樹的根，無雙親。如果i>1，則其雙親是節點[i/2]。
2）如果2i>n，則節點i無左孩子節點i為葉子節點);否則其左孩子是節點2i。
3）如果2i+1>n，則節點i無右孩子；否則其右孩子是節點2i+1；
6.3.3二叉樹的存儲結構
1、順序存儲
如果為完全二叉樹，則可按層序順序存儲，如果不是完全二叉樹，則將缺失的位置也分配存儲空間，只是什麼數據都不存儲。浪費空間。
2 、鏈式存儲
二叉樹每個節點最多有兩個孩子，所以為它設計一個數據域和兩個指針域，稱這樣的鏈表叫做二叉鏈表。
lchild
data
rchild
typedef struct BitNode
{
int data;
struct BitNode *lchild, *rchild;
} BitNode, *BitTree；
6.3.4遍歷二叉樹
二叉樹的遍歷：從根節點出發，按照某種次序依次訪問二叉樹中的所有節點，使得每個節點被訪問依次僅且訪問一次。
1、前序遍歷：根節點，左子樹，右子樹。
void PreOrderTraverse(BitTree T)
{
if(T == NULL)
return ;
printf("%c",T->data);/*顯示節點數據，可以更改為其它對節點操作。*/
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
2、中序遍歷：左子樹，根節點，右子樹。
void InOrderTraverse(BitTree T)
{
if(T == NULL)
return ;
InOrderTraverse(T->lchild);
printf("%c",T->data);/*顯示節點數據，可以更改為其它對節點操作。*/
InOrderTraverse(T->rchild);
}
3、後序遍歷：左子樹，右子樹，根節點
void PostOrderTraverse(BitTree T)
{
if(T == NULL)
return ;
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c",T->data);/*顯示節點數據，可以更改為其它對節點操作。*/
}
前序遍歷的第一個節點為根節點。中序遍歷的根節點會在中間出現，其左面的為左子樹的節點，右面的右子樹的節點。後序遍歷的最後一個節點為根節點。
已知前序遍歷和中序遍歷或者後序遍歷和中序遍歷均可確定一棵二叉樹。但是已知前序遍歷和後序遍歷不能唯一確定一棵二叉樹。
6.4 二叉樹的建立
1、建立步驟
1）將一個二叉樹變為擴展二叉樹。擴展二叉樹是指將將一個非空節點的空孩子用#表示，就變為擴展二叉樹，當遇到#時，就知道此節點為空。
2）按前序遍歷擴展二叉樹也可按其他順序，創建的代碼就會有所不同）。
如：AB#D##C##。
3）實現的算法前序遍歷的序列）
void CreatBitTree(BitTree *T)
{
char ch;
scanf("%c",&ch); // 依次輸入AB#D##C##
if(ch == '#')
*T = NULL;
else
{
*T = (BitTree) malloc(sizeof(BitNode));
if(!*T)
exit(OVERFLOW);
(*T)->data = ch;/*生成根節點*/
CreateBitTree(&(*T)->lchild);/*構造左子樹*/
CreateBitTree(&(*T)->rchild); /*構造右子樹*/
}
}
6.5 線索二叉樹
假如一個二叉樹節點數目為n，則指針域有2n個，但其中包含空指針域有n+1個。將這些空閒的位置用來存儲節點的前驅和後繼。稱相應的二叉樹為線索二叉樹。
如果一個節點的lchild為空，則讓它指向該節點的前驅，且ltag=1。否則指向左孩子，ltag=0;
如果一個節點的rchild為空，則讓它指向該節點的後繼,，且rtag=1。否則指向右孩子，rtag=0;
本文出自 “李海川” 博客，請務必保留此出處http://lihaichuan.blog.51cto.com/498079/1285890
