第C語言數(shù)據(jù)結(jié)構(gòu)詳細(xì)解析二叉樹的操作目錄二叉樹分類二叉樹性質(zhì)性質(zhì)的使用二叉樹的遍歷前序遍歷中序遍歷后序遍歷層序遍歷求二叉樹的節(jié)點(diǎn)數(shù)求二叉樹葉子結(jié)點(diǎn)個(gè)數(shù)求二叉樹的最大深度二叉樹的銷毀

二叉樹分類

滿二叉樹

除最后一層無任何子節(jié)點(diǎn)外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)的二叉樹。也可以理解為每一層的結(jié)點(diǎn)數(shù)都達(dá)到最大值的二叉樹。

完全二叉樹

一棵深度為k的有n個(gè)結(jié)點(diǎn)的二叉樹，對樹中的結(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號，如果編號為i（1in）的結(jié)點(diǎn)與滿二叉樹中編號為i的結(jié)點(diǎn)在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。

簡單的說，完全二叉樹就是最后一層可以有缺失的滿二叉樹(完全二叉樹是一種特殊的滿二叉樹)，并且是從右往左的缺失。

二叉樹性質(zhì)

若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵樹非空二叉樹的第i層上最多有2^(i-1)個(gè)節(jié)點(diǎn)。若規(guī)定根節(jié)點(diǎn)層數(shù)為1，則深度為h的二叉樹的最大節(jié)點(diǎn)數(shù)是2^h1對任何一顆二叉樹，如果葉節(jié)點(diǎn)(度為0的節(jié)點(diǎn))個(gè)數(shù)為n0，度為2的節(jié)點(diǎn)個(gè)數(shù)為n2，則n0=n2+1。若規(guī)定根節(jié)點(diǎn)層數(shù)為1，具有N個(gè)節(jié)點(diǎn)的滿二叉樹的深度為小于（log_2）?N+1的最大整數(shù)。

性質(zhì)的使用

在具有2n個(gè)結(jié)點(diǎn)的完全二叉樹中，葉子結(jié)點(diǎn)個(gè)數(shù)為()

An

Bn+1

Cn-1

Dn/2

分析：

設(shè)度為0的結(jié)點(diǎn)有x0個(gè)

設(shè)度為1的結(jié)點(diǎn)有x1個(gè)

設(shè)度為2的結(jié)點(diǎn)有x2個(gè)

x0+x1+x2=2n

x0=x2+1

由上面兩個(gè)式子可推出：2*2x2+x1+1=2n

因?yàn)槭峭耆鏄?，x1可能是0，1，但是要使上式結(jié)果為偶數(shù)，x1只能是1，所以x2等于n，選A。

二叉樹的遍歷

首先我們先創(chuàng)建一個(gè)簡單的二叉樹

typedefcharBTDataType;

typedefstructBinaryTreeNode{

structBinaryTreeNode*left;

structBinaryTreeNode*right;

BTDataTypedata;

}BTNode;

intmain()

BTNode*A=(BTNode*)malloc(sizeof(BTNode));

A-data='A';

A-left=NULL;

A-right=NULL;

BTNode*B=(BTNode*)malloc(sizeof(BTNode));

B-data='B';

B-left=NULL;

B-right=NULL;

BTNode*C=(BTNode*)malloc(sizeof(BTNode));

C-data='C';

C-left=NULL;

C-right=NULL;

BTNode*D=(BTNode*)malloc(sizeof(BTNode));

D-data='D';

D-left=NULL;

D-right=NULL;

BTNode*E=(BTNode*)malloc(sizeof(BTNode));

E-data='E';

E-left=NULL;

E-right=NULL;

A-left=B;

A-right=C;

B-left=D;

B-right=E;

LevelOrder(A);

}

前序遍歷

前序(先序)：根-左子樹-右子樹

預(yù)期結(jié)果：ABDEC

//前序

voidPrevOrder(BTNode*root)

if(root==NULL)

//為了結(jié)果更加直觀，將NULL打印

printf("NULL");

return;

//先打印根的數(shù)據(jù)

printf("%c",root-data);

//遍歷左子樹

PrevOrder(root-left);

//遍歷右子樹

PrevOrder(root-right);

編譯結(jié)果：

中序遍歷

中序：左子樹-根-右子樹

預(yù)期結(jié)果：DBEAC

voidMidOrder(BTNode*root)

//為了結(jié)果更加直觀，將NULL打印

if(root==NULL)

printf("NULL");

return;

MidOrder(root-left);

printf("%c",root-data);

MidOrder(root-right);

編譯結(jié)果：

后序遍歷

后續(xù)：左子樹-右子樹-根

預(yù)期結(jié)果：DEBCA

voidPostOrder(BTNode*root)

if(root==NULL)

printf("NULL");

return;

PostOrder(root-left);

PostOrder(root-right);

printf("%c",root-data);

編譯結(jié)果：

層序遍歷

voidLevelOrder(BTNode*root)

//創(chuàng)建隊(duì)列q

Queueq;

//初始化隊(duì)列

QueueInit(

//如果根結(jié)點(diǎn)不為空，將根節(jié)點(diǎn)入隊(duì)列

if(root)QueuePush(q,root);

//進(jìn)行循環(huán)，直到隊(duì)列為空

while(!QueueEmpty(q))

//獲取隊(duì)列的第一個(gè)數(shù)據(jù)，并打印

QDataTypefront=QueueFront(

printf("%c",front-data);

//對頭數(shù)據(jù)出隊(duì)列

QueuePop(

//如果左子樹不為空，左子樹入隊(duì)列

if(front-left!=NULL)

QueuePush(q,front-left);

//如果右子樹不為空，右子樹入隊(duì)列

if(front-right!=NULL)

QueuePush(q,front-right);

}

求二叉樹的節(jié)點(diǎn)數(shù)

intBTSize(BTNode*root)

returnroot==NULL0:1+BTSize(root-left)+BTSize(root-right);

求二叉樹葉子結(jié)點(diǎn)個(gè)數(shù)

intBTLeafSize(BTNode*root)

if(root==0)return0;

returnroot-left==NULLroot-right==NULL1:BTLeafSize(root-right)+BTLeafSize(root-left);

求二叉樹的最大深度

intmaxDepth(BTNode*root)

if(root==NULL)

return0;

return1+fmax(maxDepth(root-left),maxDepth(root-right));

二叉樹的銷毀

//二叉樹的銷毀

//傳