定義
二叉樹（Binary Tree）是一種特殊的樹。
特點(diǎn)：
1.每個(gè)結(jié)點(diǎn)至多只有兩棵子樹（即二叉樹中不存在度大于2的結(jié)點(diǎn)）。
2.二叉樹的子樹有左右之分，其次序不能任意顛倒蛮粮。
性質(zhì)
性質(zhì)1
第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i>=1)。
性質(zhì)2
深度為K的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)谜慌。
性質(zhì)3
對(duì)于任何一棵二叉樹T然想，如果其終端結(jié)點(diǎn)數(shù)為，度為2的結(jié)點(diǎn)為
欣范，則
=
+1
拓展
完全二叉樹和滿二叉樹是樹的兩種特殊形態(tài)的二叉樹
一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹变泄。
深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹恼琼，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一 一對(duì)應(yīng)時(shí)妨蛹，稱之為完全二叉樹。
性質(zhì)4
具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[
性質(zhì)5
如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹（其深度為[
1.如果i=1颤难，則結(jié)點(diǎn)i是二叉樹的根神年，無(wú)雙親；如果i>1行嗤，則其雙親Parent(i)是結(jié)點(diǎn)[i/2]已日。
2.如果2i>n，則結(jié)點(diǎn)i無(wú)左孩子（結(jié)點(diǎn)i為葉子結(jié)點(diǎn)）栅屏；否則其左孩子Lchild(i)是結(jié)點(diǎn)2i飘千。
3.如果2i+1>n，則結(jié)點(diǎn)i無(wú)右孩子既琴；否則其右孩子Rchild(i)是結(jié)點(diǎn)2i+1占婉。
二叉樹兩種存儲(chǔ)結(jié)構(gòu)
1.順序存儲(chǔ)結(jié)構(gòu)
僅適用于完全二叉樹泡嘴。最壞的情況下甫恩，一個(gè)深度為k且只有k個(gè)結(jié)點(diǎn)的單支樹（樹中不存在度為2的結(jié)點(diǎn)）卻需要長(zhǎng)度為2k-1的一維數(shù)組。
2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
設(shè)計(jì)不同的結(jié)點(diǎn)結(jié)構(gòu)可構(gòu)成不同形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)酌予。二叉樹的鏈表中的結(jié)點(diǎn)至少包含3個(gè)域：數(shù)據(jù)域和左磺箕、右指針域。
拓展：線索鏈表
拓展
遍歷二叉樹
線索二叉樹
遍歷二叉樹
以下是二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)抛虫，以及先序松靡、中序、后序遞歸遍歷輸出結(jié)點(diǎn)的代碼建椰。
前期就先把代碼放這了雕欺，后期就放到我的GitHub上去
#include <iostream>
#include <cmath> /* 包含OVERFLOW */
#include <malloc.h> /* 包含malloc()函數(shù) */
using namespace std;
typedef char TElemType; //二叉樹結(jié)點(diǎn)內(nèi)部數(shù)據(jù)類型
/* 鏈?zhǔn)酱鎯?chǔ)二叉樹結(jié)構(gòu)定義 */
typedef struct BiTNode
{
TElemType data; //數(shù)據(jù)域
struct BiTNode *lchild, *rchild; //指針域
} BiTNode, *BiTree;
/* #表示空，以先序序列構(gòu)造二叉樹 */
void CreateBiTree(BiTree *T)
{
TElemType ch;
cin>>ch;
if(ch=='#')
*T = NULL;
else
{
*T = (BiTree)malloc(sizeof(BiTNode));
if(!*T)
exit(OVERFLOW);
(*T)->data = ch;
CreateBiTree(&(*T)->lchild); //繼續(xù)構(gòu)建左孩子結(jié)點(diǎn)
CreateBiTree(&(*T)->rchild); //繼續(xù)構(gòu)建右孩子結(jié)點(diǎn)
}
}
/* 先序序列輸出 */
void PreOrderTraverse(BiTree T)
{
if(T == NULL)
return;
cout<<T->data;
PreOrderTraverse(T->lchild); //遍歷左子樹
PreOrderTraverse(T->rchild); //遍歷右子樹
}
/* 中序序列輸出 */
void InOrderTraverse(BiTree T)
{
if(T == NULL)
return;
InOrderTraverse(T->lchild); //遍歷左子樹
cout<<T->data;
InOrderTraverse(T->rchild); //遍歷右子樹
}
/* 后序序列輸出 */
void PostOrderTraverse(BiTree T)
{
if(T == NULL)
return;
PostOrderTraverse(T->lchild); //遍歷左子樹
PostOrderTraverse(T->rchild); //遍歷右子樹
cout<<T->data;
}
/* 判斷二叉樹是否為空 */
bool IsEmpty(BiTree T)
{
if(T != NULL)
return false;
else
return true;
}
/* 銷毀二叉樹 */
bool DestroyBiTree(BiTree *T)
{
BiTree lchild, rchild; //臨時(shí)保存左右孩子結(jié)點(diǎn)
if(*T == NULL)
return false;
lchild = (*T)->lchild; //臨時(shí)保存左孩子結(jié)點(diǎn)
rchild = (*T)->rchild; //臨時(shí)保存右孩子結(jié)點(diǎn)
(*T) = NULL; //將被銷毀結(jié)點(diǎn)內(nèi)容提前賦值為NULL
free(*T); //銷毀當(dāng)前結(jié)點(diǎn),銷毀后地址內(nèi)容不會(huì)改變
DestroyBiTree(&lchild); //銷毀左孩子結(jié)點(diǎn)
DestroyBiTree(&rchild); //銷毀右孩子結(jié)點(diǎn)
return true;
}
int main()
{
/* 測(cè)試用例1 abc##d##e#f## */
/* 測(cè)試用例2 abcd#####*/
BiTree T;
CreateBiTree(&T);
cout<<"先序序列為:";
PreOrderTraverse(T);
putchar('\n');
cout<<"中序序列為:";
InOrderTraverse(T);
putchar('\n');
cout<<"后序序列為:";
PostOrderTraverse(T);
putchar('\n');
if(IsEmpty(T) == true)
cout<<"二叉樹為空!\n";
else
cout<<"二叉樹不為空!\n";
if(DestroyBiTree(&T) == true)
cout<<"二叉樹銷毀成功!\n";
if(IsEmpty(T) == true)
cout<<"二叉樹為空!\n";
else
cout<<"二叉樹不為空!\n";
return 0;
}
