樹的定義
1.樹是由根結(jié)點(diǎn)和若干顆子樹構(gòu)成的赶么。樹是由一個集合以及在該集合上定義的一種關(guān)系構(gòu)成的肩豁。集合中的元素稱為樹的結(jié)點(diǎn)，所定義的關(guān)系稱為父子關(guān)系辫呻。父子關(guān)系在樹的結(jié)點(diǎn)之間建立了一個層次結(jié)構(gòu)清钥。在這種層次結(jié)構(gòu)中有一個結(jié)點(diǎn)具有特殊的地位，這個結(jié)點(diǎn)稱為該樹的根結(jié)點(diǎn)放闺，或稱為樹根祟昭。
（1）有且只有一個稱為根的節(jié)點(diǎn)。
（2）有若干個互不相交的樹怖侦，這些子樹本也是一顆樹 篡悟。樹由節(jié)點(diǎn)和邊構(gòu)成（指針域） ，每個節(jié)點(diǎn)只有一個父節(jié)點(diǎn)但可以有多個子節(jié)點(diǎn)匾寝，但有一個節(jié)點(diǎn)例外搬葬，該節(jié)點(diǎn)沒有根節(jié)點(diǎn)，此節(jié)點(diǎn)稱為根節(jié)點(diǎn)
二叉樹
專業(yè)術(shù)語
節(jié)點(diǎn) 父節(jié)點(diǎn) 子節(jié)點(diǎn) 子孫 堂兄弟
深度：從根節(jié)點(diǎn)到最底層節(jié)點(diǎn)的層數(shù)稱之為深度,上圖有4層艳悔。
葉子節(jié)點(diǎn)：沒有子節(jié)點(diǎn)的節(jié)點(diǎn)急凰，如上圖中的#節(jié)點(diǎn)。
非終端節(jié)點(diǎn)：非葉子節(jié)點(diǎn)猜年。
度：子節(jié)點(diǎn)的個數(shù)（樹內(nèi)所有節(jié)點(diǎn)度的最大值）抡锈。
樹的分類
一般樹 二叉樹 森林
一般樹：任意一個節(jié)點(diǎn)的子節(jié)點(diǎn)的個數(shù)都不受限制
二叉樹：任意一個節(jié)點(diǎn)的子節(jié)點(diǎn)的個數(shù)最多兩個，且子節(jié)點(diǎn)的位置不可更改（有序乔外，從上到下床三，從左到右）。（上圖為二叉樹）
森林 ：n個互補(bǔ)相交的樹的集合
二叉樹的分類
一般二叉樹：袁稽。勿璃。。推汽。补疑。
滿二叉樹：在不增加樹的層數(shù)的前提下，無法再多添加一個節(jié)點(diǎn)的二叉樹就是滿二叉樹歹撒。
完全二叉樹：如果只是刪除了滿二叉樹最底層最右邊的連續(xù)若干個節(jié)點(diǎn)莲组，這樣形成的二叉樹就是完全二叉樹。
完全二叉樹包含滿二叉樹
樹的存儲(重點(diǎn))
二叉樹的存儲：連續(xù)存儲【完全二叉樹】和鏈?zhǔn)酱鎯?/h5>
（1）連續(xù)存儲【完全二叉樹（用貼的方法）】：為什么要轉(zhuǎn)換為完全而二叉樹的原因：樹為非線性二連續(xù)存儲為線性暖夭，且如果只存取有效節(jié)點(diǎn)則無法還原以前二叉樹的本來面目锹杈。無法確定關(guān)系.
優(yōu)點(diǎn)：查找某個節(jié)點(diǎn)的父節(jié)點(diǎn)和子節(jié)點(diǎn)（也包括判斷有咩有）速度很快
缺點(diǎn)：耗用內(nèi)存空間過大
(2)鏈?zhǔn)酱鎯Γㄖ羔槪?/p>一般樹的存儲（非線性結(jié)構(gòu)用線性結(jié)構(gòu)來存儲）
（1）雙親表示法(求父節(jié)點(diǎn)方便)
（2）孩子表示法（求子節(jié)點(diǎn)方便）
（3）雙親孩子表示法（求父節(jié)點(diǎn)和子節(jié)點(diǎn)）
（4）二叉樹表示法 把一個普通書轉(zhuǎn)化為二叉樹來存儲撵孤。
轉(zhuǎn)換方法為：設(shè)法保證任意一個節(jié)點(diǎn)的左指針域指向它的第一個孩子，右指針域指向它的下一個兄弟竭望。只要能滿足此條件邪码，就可以把一個普通樹轉(zhuǎn)化成二叉樹。一個普通樹轉(zhuǎn)化成的二叉樹一定沒有右子樹（是根節(jié)點(diǎn) 視頻p65 22：33）森林的存儲
先把森林轉(zhuǎn)化為二叉樹咬清，再存儲二叉樹闭专，具體方式為：根節(jié)點(diǎn)之間可以當(dāng)成是兄弟來看待
構(gòu)造二叉樹代碼
typedef struct NODE//定義節(jié)點(diǎn)
{
int data;//數(shù)據(jù)域
struct NODE * Left;//左指針 （左孩子）
struct NODE * Right; //右指針 （右孩子）
}BTree,*PBTree;
void Creat_BTree(PBTree &T)//先輸入根，再輸入左子樹旧烧，再輸入右子樹（左邊優(yōu)先
{
int val;
cin>>val;
if(val==-1) T=NULL;//節(jié)點(diǎn)指向空 ,輸入-1結(jié)束影钉。
else
{
T=(PBTree)malloc(sizeof(BTree));
T->data=val;
Creat_BTree(T->Left);//遞歸
Creat_BTree(T->Right);
}
}
輸入值要有一些操作
若想得到圖中的二叉樹要這樣輸入：
1 2 4 -1 -1 5 -1 -1 3 -1 6 -1 -1
先序遍歷
遞歸版
例1的結(jié)果為 1 2 4 5 3 6過程
void preoder(PBTree &T)
{
if(T!=NULL)
{
cout<<T->data<<" ";
preoder(T->Left);
preoder(T->Right);
}
return;
}
非遞歸版
非遞歸的前序遍歷需要用到棧的性質(zhì)，也就是先進(jìn)后出掘剪。在這里偷些懶平委，直接使用#include<stack>，直接使用棧的頭文件夺谁。
偷些懶廉赔，直接使用#include<stack>，直接使用棧的頭文件予权。
void preoder(PBTree &T)//先序遍歷昂勉。
{
PBTree temp=T;//臨時指針
stack<PBTree>s ;//創(chuàng)建一個新的棧來存儲節(jié)點(diǎn)。
while(temp||!s.empty())//當(dāng)temp!=NULL或者棧s為空時
{
while(temp)//控制左節(jié)點(diǎn)扫腺，只有當(dāng)左節(jié)點(diǎn)為空時，才會想起他的右孩子村象。當(dāng)節(jié)點(diǎn)不為空時笆环，一定要向左孩子看一下。
{
cout<<temp->data<<" ";
s.push(temp);//將節(jié)點(diǎn)壓入棧厚者，方便回溯
temp=temp->Left;//左節(jié)點(diǎn)
}
// 當(dāng)空節(jié)點(diǎn)時躁劣，跳出循環(huán)
temp = s.top();
s.pop();
// 找到右孩子
temp = temp->Right;
}
return ;
}
中序遍歷
遞歸版
例1的結(jié)果為4 2 5 1 3 6過程
void inoder(PBTree &T)
{
if(T!=NULL)
{
inoder(T->Left);
cout<<T->data<<" ";
inoder(T->Right);
}
return;
}
非遞歸版
void inorder(PBTree &T)
{
// 用于儲存遍歷的元素
stack<node*> s;
while( T || !s.empty() )
{
if ( T!= NULL )
{
s.push(T);
T= T->Left;
}
else
{
T= s.top();
s.pop();
cout << T->data << " ";
T = T->Right;
}
}
}
后序遍歷
遞歸版
例1的結(jié)果為 4 5 2 6 3 1過程
void postoder(PBTree &T)
{
if(T!=NULL)
{
postoder(T->Left);
postoder(T->Right);
cout<<T->data<<" ";
}
return;
}
層次遍歷
遞歸版
例1的結(jié)果為
