簡述： 二叉樹是十分重要的數據結構，主要用來存放數據，並且方便查找等操作，在很多地方有廣泛的應用。 二叉樹有很多種類，比如線索二叉樹，二叉排序樹，平衡二叉樹等，本文寫的是最基礎最簡單的二叉樹。 思路： 二叉樹的建立採用的是遞歸的思想：給定一個指向根節點的指針，然後遞歸調用ceate()函數，自動生成 ...
簡述：
二叉樹是十分重要的數據結構，主要用來存放數據，並且方便查找等操作，在很多地方有廣泛的應用。
二叉樹有很多種類，比如線索二叉樹，二叉排序樹，平衡二叉樹等，本文寫的是最基礎最簡單的二叉樹。
思路：
二叉樹的建立採用的是遞歸的思想：給定一個指向根節點的指針，然後遞歸調用ceate()函數，自動生成一個二叉樹。就像是在地上挖了個坑（根節點）
，然後他會拿著鏟子（create函數）按照一定的規則自動挖一個很大的洞穴（二叉樹）出來。當然挖坑前需要先定義每個洞長什麼樣（定義節點結構）。
二叉樹的遍歷採用的也是遞歸的思想：如果節點有數據，則按照遍歷規則列印根節點和孩子節點，沒有數據則返回直到所有數據都遍歷完，遞歸結束。
代碼如下：
#include "stdafx.h" //我自己的編譯器的問題所以要加
#include<iostream>
using namespace std;
typedef char TElemType;
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree; //*BiTree的意思是給 struct BiTNode*起了個別名，叫BiTree，故BiTree為指向節點的指針。
void createBiTree(BiTree &T) //創建二叉樹。
{
char ch;
cin >> ch;
if ('#' == ch)
T = NULL;
else
{
T = new BiTNode;
T->data = ch;
createBiTree(T->lchild);
createBiTree(T->rchild);
}
}
void PerOrderTraverse(BiTree T) //前序遍歷二叉樹並列印。
{
if (T)
{
cout << T->data<<" ";
PerOrderTraverse(T->lchild);
PerOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiTree T) //中序遍歷二叉樹並列印。
{
if (T)
{
InOrderTraverse(T->lchild);
cout << T->data<<" ";
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiTree T) //後序遍歷二叉樹並列印。
{
if (T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout << T->data<<" ";
}
}
void Copy(BiTree T, BiTree &NewT) //二叉樹的拷貝
{
if (T == NULL)
{
NewT = NULL;
return;
}
else
{
NewT = new BiTNode;
NewT->data = T->data;
cout << NewT->data<<" ";
Copy(T->lchild, NewT->lchild);
Copy(T->rchild, NewT->rchild);
}
}
int NodeCount(BiTree T) //求二叉樹中結點個數
{
if (T == NULL)
return 0;
else
return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}
int LeafCount(BiTree T) {
//求二叉樹中葉子(終端節點)個數
if (T == NULL)
return 0;
if (T->lchild == NULL && T->rchild == NULL)
return 1;
else
return LeafCount(T->lchild) + LeafCount(T->rchild);
}
int main()
{
BiTree T; //聲明一個指向二叉樹根節點的指針
BiTree NewT; //聲明一個指向二叉樹根節點的NewT指針，用於複製T的內容
createBiTree(T);
cout << "二叉樹創建完畢!" << endl;
cout << "二叉樹中結點個數:" << endl;
cout<<NodeCount(T)<<endl;
cout << "二叉樹中葉子個數:" << endl;
cout << LeafCount(T) << endl;
cout << "拷貝結果:" << endl;
Copy(T, NewT);
cout << endl;
cout << "前序遍歷二叉樹:" << endl;
PerOrderTraverse(T);
cout << endl;
cout << "中序遍歷二叉樹:" << endl;
InOrderTraverse(T);
cout << endl;
cout << "後序遍歷二叉樹:" << endl;
PostOrderTraverse(T);
cout << endl;
return 0;
}
測試樣例+結果：
假設我們要建立一個如下圖所示的二叉樹，#代表空節點，按照前序遍歷順序二叉樹表示為：ab##c## (此處為前序)
下麵是代碼的運行結果：
