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