1、二叉樹的定義
2、二叉樹的性質
3、二叉樹的順序存儲結構
4、二叉樹的鍊式存儲結構
二叉樹是一種重要的數據結構，與數組、向量、鍊表都是一種順序容器，它們提供了按位置訪問數據的手段。但是有一個缺點，它們都是按照位置來确定數據，想要通過值來獲取數據，隻能通過遍曆的方式。而二叉樹在很大程度上解決了這個缺點，二叉樹是按值來保存元素，也按值來訪問元素。
二叉樹由一個個節點組成，一個節點最多隻能有兩個子節點，從根節點開始左右擴散，分左子節點和右子節點，向下一直分支。
許多實際問題抽象出來的數據結構往往是二叉樹的形式，即使是一般的樹也能簡單地轉換為二叉樹，而且二叉樹的存儲結構及其算法都較為簡單，因此二叉樹在數據結構與算法中特别重要。
一、二叉樹的定義
二叉樹（Binary Tree）是n（n≥0）個結點所構成的集合，它或為空樹（n=0）；或為非空樹，對于非空樹T：
（1）有且僅有一個稱之為根的結點；
（2）除根結點以外的其餘結點分為兩個互不相交的子集T1和T2，分别稱為T的左子樹和右子樹，且T1和T2本身又都是二叉樹。
二叉樹與樹一樣具有遞歸性質，二叉樹與樹的區别主要有以下兩點：
（1）二叉樹每個結點至多隻有兩棵子樹（即二叉樹中不存在度大于2的結點）；
（2）二叉樹的子樹有左右之分，其次序不能任意颠倒。
二、二叉樹的性質
1、二叉樹中，第 i 層最多有 個結點。
2、如果二叉樹的深度為 K，那麼此二叉樹最多有 -1 個結點。
3、二叉樹中，終端結點數（葉子結點數）為 ，度為 2 的結點數為 ，則 = 1。
二叉樹還可以繼續分類，衍生出滿二叉樹和完全二叉樹。
（一）滿二叉樹：如果二叉樹中除了葉子結點，每個結點的度都為 2，則此二叉樹稱為滿二叉樹。
圖二 滿二叉樹
如上圖 2 所示就是一棵滿二叉樹。滿二叉樹除了滿足普通二叉樹的性質，還具有以下性質：
1、滿二叉樹中第 i 層的節點數為 -1 個。
2、深度為 k 的滿二叉樹必有 -1 個節點 ，葉子數為 -1。
3、滿二叉樹中不存在度為 1 的節點，每一個分支點中都兩棵深度相同的子樹，且葉子節點都在最底層。
4、具有 n 個節點的滿二叉樹的深度為 (n 1)。
（二）完全二叉樹：深度為k的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹中編号從1至n的結點一一對應時，稱之為完全二叉樹。
圖三 滿二叉樹與完全二叉樹
滿二叉樹的特點是：每一層上的結點數都是最大結點數，即每一層i的結點數都具有最大值 -1。可以對滿二叉樹的結點進行連續編号，約定編号從根結點起，自上而下，自左至右。由此可引出完全二叉樹的定義。根據上面的圖三，很容易判斷兩者的不同。
（1）葉子結點隻可能在層次最大的兩層上出現；
（2）對任一結點，若其右分支下的子孫的最大層次為m，則其左分支下的子孫的最大層次必為m或m 1。圖4中（c）和（d）不是完全二叉樹。
圖四 非完全二叉樹
三、二叉樹的順序存儲結構
二叉樹的順序存儲，雖然樹是非線性存儲結構，但也可以用順序表存儲。需要注意的是，順序存儲隻适用于完全二叉樹。對于普通的二叉樹，必須先将其轉化為完全二叉樹，才能存儲到順序表中。滿二叉樹也是完全二叉樹，可以直接用順序表存儲。
所謂順序存儲完全二叉樹，就是從樹的根結點開始，按照層次将樹中的結點逐個存儲到數組中。
圖五 完全二叉樹
各個結點在順序表中的存儲狀态如下圖所示：
上面例子說的完全二叉樹，那如果是普通二叉樹呢？
圖6 普通二叉樹(a)的轉化成普通二叉樹（b)
圖 6 左側(a)是普通二叉樹，右側(b)是轉化後的完全（滿）二叉樹。解決了二叉樹的轉化問題，接下來各個結點在順序表中的存儲狀态如圖 如下：
二叉樹的順序存儲結構用 C 語言表示為：
#define NODENUM 7 //二叉樹中的結點數量
#define ElemType int //結點值的類型
//自定義 BiTree 類型，表示二叉樹
typedef ElemType BiTree[MaxSize];
（1）存儲二叉樹
void InitBiTree(BiTree T) {
ElemType node;
int i = 0;
printf("按照層次從左往右輸入樹中結點的值，0 表示空結點，# 表示輸入結束:");
while (scanf("%d", &node))
{
T[i] = node;
i ;
}
}
（2）查找某個結點的雙親結點的值
ElemType Parent(BiTree T, ElemType e) {
int i;
if (T[0] == 0) {
printf("存儲的是一棵空樹\n");
}
else
{
if (T[0] == e) {
printf("當前結點是根節點，沒有雙親結點\n");
return 0;
}
for (i = 1; i < NODENUM; i ) {
if (T[i] == e) {
//借助各個結點的标号(數組下标 1)，找到雙親結點的存儲位置
return T[(i 1) / 2 - 1];
}
}
printf("二叉樹中沒有指定結點\n");
}
return -1;
}
（3）查找某個結點的左孩子結點的值
ElemType LeftChild(BiTree T, ElemType e) {
int i;
if (T[0] == 0) {
printf("存儲的是一棵空樹\n");
}
else
{
for (i = 1; i < NODENUM; i ) {
if (T[i] == e) {
//借助各個結點的标号(數組下标 1)，找到左孩子結點的存儲位置
if (((i 1) * 2 < NODENUM) && (T[(i 1) * 2 - 1] != 0)) {
return T[(i 1) * 2 - 1];
}
else
{
printf("當前結點沒有左孩子\n");
return 0;
}
}
}
printf("二叉樹中沒有指定結點\n");
}
return -1;
}
（4）查找某個結點的右孩子結點的值
ElemType RightChild(BiTree T, ElemType e) {
int i;
if (T[0] == 0) {
printf("存儲的是一棵空樹\n");
}
else
{
for (i = 1; i < NODENUM; i ) {
if (T[i] == e) {
//借助各個結點的标号(數組下标 1)，找到左孩子結點的存儲位置
if (((i 1) * 2 1 < NODENUM) && (T[(i 1) * 2] != 0)) {
return T[(i 1) * 2];
}
else
{
printf("當前結點沒有右孩子\n");
return 0;
}
}
}
printf("二叉樹中沒有指定結點\n");
}
return -1;
}
順序查找某個結點的雙親結點和孩子結點，用到了完全二叉樹具有的性質：将樹中節點按照層次并從左到右依次标号 1、2、3、...（程序中用數組下标 1 表示），若節點 i 有左右孩子，則其左孩子節點的标号為 2*i，右孩子節點的标号為 2*i 1。
雖然二叉樹是非線性存儲結構，但也可以存儲到順序表中。但順序表隻能存儲完全二叉樹，普通的二叉樹必須先轉化為完全二叉樹之後才能用順序表存儲。實際場景中，并非每個二叉樹都是完全二叉樹，用順序表存儲普通二叉樹或多或少存在空間浪費的情況。
四、二叉樹的鍊式存儲結構
通過學習就會發現，其實二叉樹并不适合用順序表存儲，因為并不是每個二叉樹都是完全二叉樹，普通二叉樹使用順序表存儲或多或多會存在内存浪費的情況。
所謂二叉樹的鍊式存儲，其實就是用鍊表存儲二叉樹，具體的存儲方案是：從樹的根節點開始，将各個節點及其左右孩子使用鍊表存儲。例如圖 1 是一棵普通的二叉樹，如果選擇用鍊表存儲，各個結點的存儲狀态如下圖所示：
圖6二叉樹鍊式存儲結構示意圖
由圖 6可知，采用鍊式存儲二叉樹時，樹中的結點由 3 部分構成（如圖 3 所示）：
（1）指向左孩子節點的指針（Lchild）；
（2）節點存儲的數據（data）；
（3）指向右孩子節點的指針（Rchild）；
圖 7 二叉樹節點結構
C 語言表示節點結構的代碼為：
typedef struct BiTNode{
TElemType data;//數據域
struct BiTNode *lchild,*rchild;//左右孩子指針
}BiTNode,*BiTree;
（1）存儲二叉樹
void CreateBiTree(BiTree* T) {
*T = (BiTNode*)malloc(sizeof(BiTNode));
(*T)->data = 1;
(*T)->lchild = (BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->data = 2;
(*T)->rchild = (BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild->data = 3;
(*T)->rchild->lchild = NULL;
(*T)->rchild->rchild = NULL;
(*T)->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->lchild->data = 4;
(*T)->lchild->rchild = NULL;
(*T)->lchild->lchild->lchild = NULL;
(*T)->lchild->lchild->rchild = NULL;
}
(2)後序遍曆二叉樹，釋放樹占用的内存
void DestroyBiTree(BiTree T) {
if (T) {
DestroyBiTree(T->lchild);//銷毀左孩子
DestroyBiTree(T->rchild);//銷毀右孩子
free(T);//釋放結點占用的内存
}
}
我們運行一下案例：
int main() {
BiTree Tree;
CreateBiTree(&Tree);
printf("根節點的左孩子結點為：%d\n", Tree->lchild->data);
printf("根節點的右孩子結點為：%d\n", Tree->rchild->data);
DestroyBiTree(Tree);
return 0;
}
程序輸出結果：
根節點的左孩子結點為：2
根節點的右孩子結點為：3
設計不同的結點結構可構成不同形式的鍊式存儲結構，例如，在某些實際場景中，可能會做 "查找某節點的父節點" 的操作，這時可以在節點結構中再添加一個指針域，用于各個節點指向其父親節點：
圖 8 三叉樹鍊
在不同的存儲結構中，實現二叉樹的操作方法也不同，如找結點x的雙親PARENT(T, e)，在三叉鍊表中很容易實現，而在二叉鍊表中則需從根指針出發巡查。由此，在具體應用中采用什麼存儲結構，除根據二叉樹的形态之外還應考慮需進行何種操作。
【參考文獻】數據結構(C語言版）、大話數據結構、算法導論、算法設計與分析基礎。
,更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!
zpostcode 
Recruit 
weather 
mreligion 
Yellowpages 
sport 
constellation 
shopping 
name 
game 
directory 
literature 
Word 
tour 
furnish 
Lottery 
tftnews 
lyrics 
News 
digital 
car 
dir 
Edu 
Finance 
