樹的定義：一棵樹是由n（n>0）個元素組成的有限集合赊锚。
（1）每個元素稱之為結點（node）。
（2）有一個特定的結點酱床，稱為根結點或樹根（root）羊赵。
（3）除根結點外，其余結點能分成m（m>=0）個互不相交的有限集合扇谣，
………
昧捷。其中的每個子集又都是一棵樹，這些集合稱為這棵樹的子樹罐寨。
樹的基本概念：
（1）樹是遞歸定義的靡挥。
（2）一棵樹中至少有一個結點。這個結點就是根結點鸯绿，它沒有前驅(qū)跋破，其余每個結點都有唯一的一個前驅(qū)結點簸淀。每個結點可以有0或多個后繼結點。因此樹雖然是非線性結構毒返，但也是有序結構租幕，至于前驅(qū)后繼結點是哪個，還要看樹的遍歷方法拧簸。
（3）一個結點的子樹個數(shù)劲绪，稱為這個結點的度（degree）；度為0的結點稱為葉結點（樹葉leaf）狡恬；度不為0的結點稱為分支結點珠叔；根以外的分支結點又稱為內(nèi)部結點蝎宇；樹中各結點的度的最大值稱為這棵樹的度弟劲。
（4）在用圖形表示的樹形結構中，對兩個用線段（樹枝）連接的相關聯(lián)的結點姥芥，稱上端結點為下端結點的父結點兔乞，稱下端結點為上端結點的子結點。稱同一個父結點的多個子結點為兄弟結點凉唐。稱從根結點到某個子結點所經(jīng)過的所有結點為這個子結點的祖先庸追。稱從某個結點為根的子樹中的任一結點都是該結點的子孫。
（5）定義一棵樹的根結點的層次（level）為0台囱，其他結點的層次等于它的父結點層次加一淡溯。一棵樹中所有的結點的層次的最大值稱為樹的深度。
（6）對于樹中任意兩個不同的結點簿训，如果從一個結點出發(fā)咱娶，自上而下沿著樹中連著結點的線段能到達另一結點，稱他們之間存在一條路徑强品”煳辏可用路徑所經(jīng)過的所有結點序列表示路徑，路徑的長度等于路徑上的結點個數(shù)減一的榛。注意琼了，不同子樹上的結點之間不存在路徑，從根結點出發(fā)夫晌，到樹中其他結點一定存在著一條路徑雕薪。
（7）森林（forest）是m（m>=0）棵互不相交的樹的集合。
樹的存儲結構：
方法一:數(shù)組晓淀，稱為“父親表示法”所袁。
const int m=10;//樹的結點數(shù)
struct node{
int data,parent;//數(shù)據(jù)域，指針域
}tree[m];
優(yōu)缺點：利用了樹中除根結點之外每個結點都有唯一的父結點這個性質(zhì)要糊，很容易找到樹根纲熏，但找孩子時需要遍歷整個線性表妆丘。
方法二：樹形單鏈表結構，稱為孩子表示法局劲，每個結點包括一個數(shù)據(jù)域和一個指針域（指向若干子結點）勺拣。假設樹的度為10，樹的結點僅存放字符鱼填，則這棵樹的數(shù)據(jù)結構定義如下：
const int m=10;
struct node;
node *tree;
struct node{
char data;
tree child[m];
};
tree t;
缺點：只能從父結點遍歷到子結點药有，不能從子結點返回到它的父結點（可以多定義一個指針存儲父結點）
方法三：樹形雙鏈表結構，稱為父親孩子表示法苹丸，每個結點包括一個數(shù)據(jù)域和兩個指針域（一個指向若干子結點愤惰，一個指向父結點）：
const int m=10;
struct node;
node *tree;
struct node{
char data;
tree child[m];
tree father;
};
tree t;
方法四：二叉樹型表示法，稱為孩子兄弟表示法赘理，是雙鏈表結構宦言，每個結點包括一個數(shù)據(jù)域，兩個指針域（一個指向該結點的第一個孩子結點商模，一個指向該結點的下一個兄弟結點）：
struct node;
node *tree;
struct node{
char data;
tree firstchild,next;
};
tree t;
樹的遍歷：
1.先序遍歷奠旺，根左右
2.后序遍歷，左右根
3.層次遍歷施流，廣搜
4.葉結點遍歷响疚，leaf
二叉樹：
五種基本形態(tài)
性質(zhì)：
1.在二叉樹的第i層最多有二的i-1次方個結點（i>=1）
2.深度為k的二叉樹至多有個結點（k>=1）
3.對任意一棵二叉樹，如果其葉結點數(shù)為瞪醋，度為2的結點數(shù)為
忿晕，則一定滿足：
+
+1。
4.具有n個結點的完全二叉樹的深度為floor（）+1银受。
5.對于一棵n個結點的完全二叉樹践盼，對任一個結點（編號為i）有：
（1）如果i=1，則結點i為根蚓土，無父結點宏侍；如果i>1，則其父結點編號為i/2蜀漆。
如果2*i>n谅河，則結點i無左孩子（當然也無右孩子，因為結點i為葉結點）确丢；否則左孩子編號為2*i绷耍。
（2）如果2*i+1>n,則結點i無右孩子；否則右孩子編號為2*i+1鲜侥。
