1，什么是樹半抱？
2脓恕，什么是樹的度？
3窿侈，結(jié)點的層次
4 線性結(jié)構(gòu)和樹結(jié)構(gòu)的比較
5 樹的三種存儲結(jié)構(gòu)（雙親表示法炼幔，孩子表示法，孩子兄弟表示法）
6棉磨，二叉樹的定義
7江掩，滿二叉樹 和 完全二叉樹
8 学辱，二叉樹的性質(zhì)
9乘瓤， 二叉樹的存儲結(jié)構(gòu)
1，什么是樹策泣？
樹是n個結(jié)點的有序集合衙傀，n = 0 時為空樹，
1萨咕，在非空樹中统抬，有且僅有一個可以稱為根的結(jié)點。
2危队，n>1時聪建，其余結(jié)點可分為m個互不相交的有限集，其中每一個集合本身是一顆樹茫陆，并且稱為根的子樹金麸。
注意子樹一定是不可以相交的
2，什么是樹的度簿盅？
1挥下，樹內(nèi)各結(jié)點的度的最大值
2揍魂，結(jié)點擁有的子樹數(shù)稱為結(jié)點的度
3，結(jié)點的層次
從根開始定義棚瘟，根為第一層现斋。根的孩子為第二層，依次類推偎蘸。
樹中結(jié)點的最大層次稱為樹的深度或高度庄蹋。
4 線性結(jié)構(gòu)和樹結(jié)構(gòu)的比較
- 線性結(jié)構(gòu)
第一個數(shù)據(jù)元素?zé)o前驅(qū)
最后一個數(shù)據(jù)元素?zé)o后繼
中間元素，一個前驅(qū)一個后繼 - 樹結(jié)構(gòu)
根結(jié)點迷雪，無雙親蔓肯，唯一
葉結(jié)點，無孩子振乏，可以有多個
中間結(jié)點蔗包，一個雙親，多個孩子慧邮。
5 樹的三種存儲結(jié)構(gòu)（雙親表示法调限，孩子表示法，孩子兄弟表示法）
- 雙親表示法
1误澳，連續(xù)的空間地址作儲存結(jié)點
2耻矮，data 數(shù)據(jù)域 指針域指向雙親
缺點是找不到孩子結(jié)點
改進(jìn)方式是再增加一個指針域指向孩子結(jié)點 - 孩子表示法
設(shè)計思想：每個結(jié)點有多個指針域，每個指針指向一棵子樹的根結(jié)點忆谓。這種方法叫多重鏈表表示法
方案一：每個結(jié)點指針域的個數(shù)等于樹的度
當(dāng)所有的結(jié)點度數(shù)大致相等時才會高效
方案二：每個結(jié)點有三部分構(gòu)成data 數(shù)據(jù)域裆装，degree度域，指針域
但是需要維護(hù)每個結(jié)點的度的數(shù)值倡缠，運算上帶來時間上的損耗哨免。
孩子表示法：有2部分構(gòu)成
1，順序存儲結(jié)構(gòu)存儲一個一維數(shù)組昙沦，數(shù)據(jù)域放data琢唾，指針域指向該結(jié)點的孩子鏈表
2，線性表中的元素盾饮，數(shù)據(jù)域放的是指向該元素在數(shù)組中的下標(biāo)采桃。指針域指向下一個孩子結(jié)點的指針
缺點：找不到雙親 ，在表頭結(jié)點里再加一個指針域丘损，指向父母結(jié)點普办。 - 孩子兄弟表示法
聽名字就知道它的指針域要指向孩子和兄弟
孩子指針域：指向第一個孩子結(jié)點
兄弟指針域：指向此結(jié)點右邊的兄弟結(jié)點
6，二叉樹的定義
二叉樹是n個結(jié)點的有限集合徘钥，該集合或者為空集（空二叉樹）或者由一個根結(jié)點和兩顆互不相交的衔蹲，分別稱為根結(jié)點的左子樹和右子樹的二叉樹組成。
左子樹和右子樹是有順序的吏饿，次序不能顛倒踪危。
7蔬浙，滿二叉樹 和 完全二叉樹
所有的分支結(jié)點都存在左子樹和右子樹。
對于一個n個結(jié)點的二叉樹贞远，如果編號為i的結(jié)點與同樣深度的滿二叉樹中編號為i的結(jié)點位置完全一致畴博。
給每個結(jié)點按照滿二叉樹的結(jié)構(gòu)逐層順序編號，如果編號出現(xiàn)空檔蓝仲，說明不是完全二叉樹俱病。否則就是。
8 二叉樹的性質(zhì)
1在二叉樹的第i層上最多有2^（i-1） 個結(jié)點
2深度為k的二叉樹袱结，至多有(2^k) - 1個結(jié)點
3n0 = n2 + 1
假設(shè)終端結(jié)點個數(shù)為n0亮隙，度為2的結(jié)點個數(shù)為n2，度為1的結(jié)點個數(shù)為n1
2個等式
n = n1 + n2 + n0
總線數(shù) = n-1 = n1 + 2n2
4二叉樹的深度為|log 2 n| + 1
|x|代表不大于x的最大整數(shù)
5對一顆有n個結(jié)點的完全二叉樹,對任一結(jié)點i
5.1i = 1 ,結(jié)點i 是二叉樹的根垢夹，無雙親溢吻。若i > 1則其雙親是結(jié)點|i / 2|
5.2如果2i > n 則結(jié)點i 無左孩子（結(jié)點i 為葉子結(jié)點）。否則其左孩子為結(jié)點2i
5.3如果2i + 1 > n 則結(jié)點i無右孩子
（5果元，1先推導(dǎo)完全二叉樹的左側(cè)左孩子的特點促王，2，再推導(dǎo)中間結(jié)點和左孩子的特點關(guān)系）
否則其右孩子是結(jié)點2i+ 1
9 二叉樹的存儲結(jié)構(gòu)
- 二叉樹的順序存儲結(jié)構(gòu)
用一維數(shù)組存儲二叉樹中的結(jié)點
把不存在的結(jié)點設(shè)為^
一般用于完全二叉樹 - 二叉鏈表
結(jié)點 一個數(shù)據(jù)域而晒，2個指針域
如果有需要還可以增加一個指向雙親的指針域蝇狼，那么就成三叉鏈表了
