柚子快報邀請碼778899分享：c語言 二叉樹的鏈?zhǔn)浇Y(jié)構(gòu)

http://yzkb.51969.com/

前言

Hello,友友們，小編將繼續(xù)重新開始數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)，前面講解了堆的部分知識，今天將講解二叉樹的鏈?zhǔn)浇Y(jié)構(gòu)的部分內(nèi)容。

1.概念回顧與新增

二叉樹是一種數(shù)據(jù)結(jié)構(gòu)，其中每個節(jié)點(diǎn)最多有兩個子節(jié)點(diǎn)，分別是左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。二叉樹的鏈?zhǔn)浇Y(jié)構(gòu)表示是使用指針（或引用）來連接節(jié)點(diǎn)，形成樹形結(jié)構(gòu)。每個節(jié)點(diǎn)包含一個數(shù)據(jù)元素和兩個指向子節(jié)點(diǎn)的指針。

2.簡單創(chuàng)建二叉樹

分為節(jié)點(diǎn)的定義，創(chuàng)建節(jié)點(diǎn)，創(chuàng)建樹

下面我們將簡單的手撕一個二叉樹：

typedef struct BTnode {

int val;

struct BTnode* left;

struct BTnode* right;

}Node;

//節(jié)點(diǎn)創(chuàng)建

Node* BuyNode(int x) {

Node* node = (Node*)malloc(sizeof(Node));

if (node == NULL) {

perror("node fail");

return NULL;

}

node->val = x;

node->left = NULL;

node->right = NULL;

return node;

}

//樹的創(chuàng)建

Node* CreatTree() {

Node* node1 = BuyNode(1);

Node* node2 = BuyNode(2);

Node* node3 = BuyNode(3);

Node* node4 = BuyNode(4);

Node* node5 = BuyNode(5);

Node* node6 = BuyNode(6);

node1->left = node2;

node1->right = node4;

node2->left = node3;

node4->left = node5;

node4->right = node6;

return node1;

}

注意：上述代碼并不是創(chuàng)建二叉樹的方式，真正創(chuàng)建二叉樹方式后序詳解重點(diǎn)講解。

二叉樹建立過后，接下來我們要進(jìn)行二叉樹的遍歷操作

3.二叉樹的遍歷

所謂二叉樹遍歷(Traversal)是按照某種特定的規(guī)則，依次對二叉樹中的結(jié)點(diǎn)進(jìn)行相應(yīng)的操作，并且每個結(jié)點(diǎn)只操作一次。訪問結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問題。 遍歷是二叉樹上最重要的運(yùn)算之一，也是二叉樹上進(jìn)行其它運(yùn)算的基礎(chǔ)。

按照規(guī)則，二叉樹的遍歷有：

前序

/

中序

/

后序的遞歸結(jié)構(gòu)遍歷

：

1.

前序遍歷

(Preorder Traversal

亦稱先序遍歷

)——

訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之前。

2.

中序遍歷

(Inorder Traversal)——

訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之中（間）。

3.

后序遍歷

(Postorder Traversal)——

訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之后。

由于被訪問的結(jié)點(diǎn)必是某子樹的根，

所以

N(Node

）、

L(Left subtree

）和

R(Right subtree

）又可解釋為，

根的左子樹和根的右子樹

。

NLR

、

LNR

和

LRN

分別又稱為先根遍歷、中根遍歷和后根遍歷。

注意：為了方便理解，我們將空節(jié)點(diǎn)都視作為NULL

3.1前序遍歷

代碼：

void PreOrder(Node* root) {

if (root == NULL) {

printf("N ");

return;

}

printf("%d ", root->val);

PreOrder(root->left);

PreOrder(root->right);

}

遞歸圖解：

代碼遞歸理解：

運(yùn)行結(jié)果：1 2 3 N N N 4 5 N N 6 N N

注意：中序和后序與前序的遞歸展開圖類似，小編就不在展示了。

3.2中序遍歷

void InOrder(Node* root) {

if (root == NULL) {

printf("N ");

return;

}

InOrder(root->left);

printf("%d ", root->val);

InOrder(root->right);

}

運(yùn)行結(jié)果：N 3 N 2 N 1 N 5 N 4 N 6 N?

3.3后序遍歷

void PostOrder(Node* root) {

if (root == NULL) {

printf("N ");

return;

}

PostOrder(root->left);

PostOrder(root->right);

printf("%d ", root->val);

}

運(yùn)行結(jié)果:N N 3 N 2 N N 5 N N 6 4 1

3.4層序遍歷

層序遍歷

：除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進(jìn)行層序遍歷。設(shè)二叉樹的根結(jié)點(diǎn)所在層數(shù)為1

，層序遍歷就是從所在二叉樹的根結(jié)點(diǎn)出發(fā)，首先訪問第一層的樹根結(jié)點(diǎn)，然后從左到右訪問第

2

層上的結(jié)點(diǎn)，接著是第三層的結(jié)點(diǎn)，以此類推，自上而下，自左至右逐層訪問樹的結(jié)點(diǎn)的過程就是層序遍歷。

層序遍歷較為復(fù)雜，這里我們采用隊(duì)列的方式來實(shí)現(xiàn)層序遍歷。

這里我們簡單的用動態(tài)數(shù)組實(shí)現(xiàn)隊(duì)列，包括了隊(duì)列的初始化，入隊(duì)出隊(duì)判空的操作。

3.4.1隊(duì)列的實(shí)現(xiàn)

// 隊(duì)列結(jié)構(gòu)

typedef struct Queue {

Node* data[MAX];

int front;

int rear;

} Queue;

// 初始化隊(duì)列

void initQueue(Queue* q) {

q->front = 0;

q->rear = 0;

}

// 入隊(duì)

void enqueue(Queue* q, Node* node) {

if ((q->rear + 1) % MAX == q->front) {

printf("Queue is full\n");

return;

}

q->data[q->rear] = node;

q->rear = (q->rear + 1) % MAX;

}

// 出隊(duì)

Node* dequeue(Queue* q) {

if (q->front == q->rear) {

printf("Queue is empty\n");

return NULL;

}

Node* node = q->data[q->front];

q->front = (q->front + 1) % MAX;

return node;

}

// 判斷隊(duì)列是否為空

int isEmpty(Queue* q) {

return q->front == q->rear;

}

3.4.2層序遍歷實(shí)現(xiàn)

從根節(jié)點(diǎn)開始，將每個節(jié)點(diǎn)的值打印出來，并依次將其左子節(jié)點(diǎn)和右子節(jié)點(diǎn)加入隊(duì)列。

// 層序遍歷函數(shù)

void levelOrder(Node* root) {

if (root == NULL) {

return;

}

Queue q;

initQueue(&q);

enqueue(&q, root);

while (!isEmpty(&q)) {

Node* node = dequeue(&q);

printf("%d ", node->val);

if (node->left) {

enqueue(&q, node->left);

}

if (node->right) {

enqueue(&q, node->right);

}

}

}

3.5主函數(shù)測試代碼

int main() {

Node* root = CreatTree();

PreOrder(root);

printf("\n");

InOrder(root);

printf("\n");

PostOrder(root);

printf("\n");

levelOrder(root);

return 0;

}

運(yùn)行結(jié)果展示：

4.遍歷相關(guān)選擇練習(xí)

1.

某完全二叉樹按層次輸出（同一層從左到右）的序列為

ABCDEFGH

。該完全二叉樹的前序序列為（ A）

A .? ? ABDHECFG

B.? ? ABCDEFGH

C.? ? HDBEAFCG

D.? ? HDEBFGCA

2.

二叉樹的先序遍歷和中序遍歷如下：先序遍歷：

EFHIGJK;

中序遍歷：

HFIEJKG.

則二叉樹根結(jié)點(diǎn)為（A）

A .? E? ? ? ? ? ? ? ? ? ? ? ? B.? ?F? ? ? ? ? ? ? ? ? ? ? C.? ?G? ? ? ? ? ? ? ? ? ? ? ? ? D.? ?H

3.

設(shè)一課二叉樹的中序遍歷序列：

badce

，后序遍歷序列：

bdeca

，則二叉樹前序遍歷序列為(D)

A. adbce? ? ? ? ? ? ? ? ? ?B. decab? ? ? ? ? ? ? ? C. debac? ? ? ? ? ? ? ? ? ? D. abcde

4.

某二叉樹的后序遍歷序列與中序遍歷序列相同，均為

ABCDEF ，則按層次輸出（同一層從左到右）的序列

為(A)

A. FEDCBA

B. CBAFED

C. DEFCBA

D. ABCDEF

結(jié)束語

好了，本節(jié)內(nèi)容到此結(jié)束了，主要對二叉樹的遍歷有了新的認(rèn)識理解，下一節(jié)小編將介紹二叉樹的相關(guān)計(jì)算操作。

最后感謝友友們的支持，動下手指給小編點(diǎn)點(diǎn)贊，發(fā)個評論吧！??！

柚子快報邀請碼778899分享：c語言 二叉樹的鏈?zhǔn)浇Y(jié)構(gòu)

http://yzkb.51969.com/

精彩內(nèi)容