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