二叉樹是數據結構的最重要的內容之一，之所以引入二叉樹，是因為良好的數據結構非常有助於數據的排序，查詢等操作，也是在空間和效率上做個平衡！！
二叉樹的定義：每個節點至多有倆顆子樹（即二叉樹中不存在度大於2的節點），並且，二叉樹的子樹有左右之分，其次序不能任意顛倒 形如：
節選自：《數據結構》 嚴蔚敏 圖6.4
二叉樹的分類：滿二叉樹，完全二叉樹，一般二叉樹（暫且列舉簡單的）。
（a）滿二叉樹，，根節點的度為1，葉節點的度為0，其余節點的度為2.
（b）完全二叉樹：理解上很簡單，在滿二叉樹的基礎上，去掉序號靠後的節點，注意必須從倒數第一個點算起。b 就是，而c,d 都不是。因此c，d只是一般的二叉樹。
二叉樹的幾個重要術語： 度，深度，根節點，雙親，葉節點，子樹。
度：每個節點可以有的子節點的個數。深度：層數；根節點：最頂層的那個點；雙親：其實是一個節點，如(a)中4和5的雙親是2；葉節點：度為0的節點；子樹：如(a),做標記的部分是1的子樹。
樹的相關性質：1，第i層上至多有2的（i-1）次方個節點；
2，深度為k的二叉樹至多有2^k-1個節點；
3，度為0 的節點數n0,度為2的節點數n2，則n0=n2+1;
4，主要是關於節點之間的位置關系，啰嗦一堆，其實很簡單，就不再貼出來了。
樹的建立和遍歷：
包括前序 中序 和後序 ，其實就是元素訪問的順序，比如如上圖 (d):前序 124536 , 中序：425136 ， 後序： 452631。簡單畫畫就可以了。
代碼如下：
[cpp] /*
email:[email protected]
qq:501968942
*/
#include<iostream>
using namespace std;
struct Tnode
{
char value;
struct Tnode* lChild;
struct Tnode* rChild;
};
typedef Tnode* BiTree;
void InitBiTree(BiTree& T)
{
char inChar=getchar();
//# 表示空節點，但是也要輸入，為了保證樹的完整性
if(inChar=='#')
T=0;
else
{
T=(BiTree)malloc(sizeof(Tnode));
if(!T) throw "Invalid Address";
else
{
T->value=inChar;
InitBiTree(T->lChild);
InitBiTree(T->rChild);
}
}
}
//前序訪問
void PreOrder(BiTree & T)
{
if(T)
{
cout<<"node is: "<<T->value<<endl;
PreOrder(T->lChild);
PreOrder(T->rChild);
}
}
//中虛訪問
void InOrder(BiTree &T)
{
if(T)
{ InOrder(T->lChild);
cout<<"node is : "<<T->value<<endl;
InOrder(T->rChild);
}
}
//後續訪問
void PostOrder(BiTree &T)
{
if(T)
{
PostOrder(T->lChild);
PostOrder(T->rChild);
cout<<"node is : "<<T->value<<endl;
}
}
int main()
{
BiTree t;
cout<<"請輸入節點值：";
InitBiTree(t);
cout<<"前序訪問："<<endl;
PreOrder(t);
cout<<"中序訪問："<<endl;
InOrder(t);
cout<<"後序訪問："<<endl;
PostOrder(t);
}
/*
email:[email protected]
qq:501968942
*/
#include<iostream>
using namespace std;
struct Tnode
{
char value;
struct Tnode* lChild;
struct Tnode* rChild;
};
typedef Tnode* BiTree;
void InitBiTree(BiTree& T)
{
char inChar=getchar();
//# 表示空節點，但是也要輸入，為了保證樹的完整性
if(inChar=='#')
T=0;
else
{
T=(BiTree)malloc(sizeof(Tnode));
if(!T) throw "Invalid Address";
else
{
T->value=inChar;
InitBiTree(T->lChild);
InitBiTree(T->rChild);
}
}
}
//前序訪問
void PreOrder(BiTree & T)
{
if(T)
{
cout<<"node is: "<<T->value<<endl;
PreOrder(T->lChild);
PreOrder(T->rChild);
}
}
//中虛訪問
void InOrder(BiTree &T)
{
if(T)
{ InOrder(T->lChild);
cout<<"node is : "<<T->value<<endl;
InOrder(T->rChild);
}
}
//後續訪問
void PostOrder(BiTree &T)
{
if(T)
{
PostOrder(T->lChild);
PostOrder(T->rChild);
cout<<"node is : "<<T->value<<endl;
}
}
int main()
{
BiTree t;
cout<<"請輸入節點值：";
InitBiTree(t);
cout<<"前序訪問："<<endl;
PreOrder(t);
cout<<"中序訪問："<<endl;
InOrder(t);
cout<<"後序訪問："<<endl;
PostOrder(t);
}
輸入：124##5##3#6
可見，與之前手工推導結果一致，注意一定不要漏了 #，否則 不但輸出結果有誤，而且 不能正常如期運行
