Posted on 2012-08-06 11:26
C小加 閱讀(5559)
評論(3) 編輯 收藏 引用 所屬分類:
數據結構和算法
基本數據結構：二叉樹（binary tree）
作者：C小加 更新時間：2012-8-6
二叉樹首先是一棵樹，每個節點都不能有多于兩個的兒子，也就是樹的度不能超過2。二叉樹的兩個兒子分別稱為“左兒子”和“右兒子”，次序不能顛倒。如圖1是一個簡單的二叉樹。
二叉樹的種類
一種是滿二叉樹，除了最后一層的葉子節點外，每一層的節點都必須有兩個兒子節點。如圖2是一個滿二叉樹。
另一種是完全二叉樹，一棵二叉樹去掉最后一層后剩下的節點組成的樹為滿二叉樹，最后一層的節點從左到右連續，沒有空出的節點，這樣的樹稱為完全二叉樹。如圖3是一棵完全二叉樹。
二叉樹的實現
因為一棵樹有最多只有兩個兒子，所以我們可以用指針直接指向他們。一個節點包括值（data）、指向左兒子的指針（lson）和指向右兒子的指針（rson）。
struct treenode
{
int data;
struct treenode* lson;
struct treenode* rson;
}
二叉樹的插入,刪除,查找和鏈表差不多,不同的是需要指定是左兒子還是右兒子。
二叉樹的數組實現也很簡單，假如說根節點在arr[0]這個位置，那么它的左兒子就在arr[2*0+1]，也就是arr[1]這個位置，它的右兒子在arr[2*0+2] ，也就是arr[2]這個位置。對于下標為i的節點來說，它的左兒子的下標為2*i+1，右兒子的下標為2*i+2。
二叉樹的遍歷
二叉樹的遍歷有三種，分別為先序遍歷，中序遍歷和后序遍歷。這三種遍歷方式是根據根節點的讀取順序來分的：
先序遍歷，就是最先讀取根節點，然后再讀取左子樹（按照同樣的方法讀取子樹上的節點），最后讀取右子樹；
中序遍歷，就是第二個讀取根節點，最先要讀取的是左子樹，然后根節點，最后右子樹；
后序遍歷，就是最后一個讀取根節點，最先讀取的是左子樹，第二個讀取右子樹，最后讀取根節點。
先序遍歷的遞歸實現代碼：
void insubtree（struct treenode* tree）
{
If(tree==NULL) return;
cout<<tree->data;
insubtree(tree->lson);
insubtree(tree->rson);
}