【原】數(shù)據(jù)結(jié)構(gòu)—樹|二叉樹|前序遍歷、中序遍歷、后序遍歷【圖解實(shí)現(xiàn)】

知識分享家 2021-04-19

展開全文

數(shù)據(jù)
結(jié)構(gòu)

二叉樹的遍歷

一、樹

在談二叉樹的知識點(diǎn)之前，我們首先來看一下樹和圖的基本概念。

樹：不包含回路的連通無向圖，樹是一種簡單的非線性結(jié)構(gòu)。

由于樹有一個(gè)不包含回路的特點(diǎn)，因此樹被賦予了許多特性，如下所示：

1、一棵樹中任意的兩個(gè)結(jié)點(diǎn)有且僅有唯一的一條路徑連通
2、一棵樹如果有n個(gè)結(jié)點(diǎn)，那么它一定恰好有n-1條邊
3、在一棵樹中加上一條邊，將會構(gòu)成一個(gè)回路
4、一棵樹中有且僅有一個(gè)沒有前驅(qū)的結(jié)點(diǎn)，即為根結(jié)點(diǎn)

通常情況下，我們在對樹進(jìn)行討論的時(shí)候，將一棵樹中的每個(gè)點(diǎn)稱為結(jié)點(diǎn):

根結(jié)點(diǎn)：沒有父結(jié)點(diǎn)的結(jié)點(diǎn)
葉結(jié)點(diǎn)：沒有子結(jié)點(diǎn)的結(jié)點(diǎn)
內(nèi)部結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)既不是根結(jié)點(diǎn)也不是葉結(jié)點(diǎn)

每個(gè)結(jié)點(diǎn)有一個(gè)深度的概念，例如上圖左邊的樹，4號結(jié)點(diǎn)深度是3。

二、二叉樹

1. 基本概念

二叉樹是一種非線性結(jié)構(gòu)，二叉樹是由遞歸定義的，其結(jié)點(diǎn)有左右子樹之分。

2. 二叉樹的存儲結(jié)構(gòu)

二叉樹一般采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，存儲結(jié)點(diǎn)由數(shù)據(jù)域和指針域組成，二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)也稱為二叉鏈表。

指針域：左指針域和右指針域

特點(diǎn)：

1、每個(gè)結(jié)點(diǎn)最多有兩顆子樹
2、左子樹和右子樹是有順序的，次序不能顛倒
3、即使某個(gè)結(jié)點(diǎn)只有一顆子樹，也要區(qū)分左右子樹
4、二叉樹可為空，空的二叉樹沒有結(jié)點(diǎn)，非空二叉樹有且僅有一個(gè)根節(jié)點(diǎn)

二叉樹中有兩種比較特殊的二叉樹：滿二叉樹、完全二叉樹，對于滿二叉樹和完全二叉樹可以按照層次進(jìn)行順序存儲。

滿二叉樹：二叉樹中每個(gè)內(nèi)部結(jié)點(diǎn)都存在左子樹和右子樹

滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹。

滿二叉樹的嚴(yán)格定義：一顆深度為h且具有2^h-1個(gè)結(jié)點(diǎn)的二叉樹。

完全二叉樹：

解釋一：如果一顆二叉樹除了最右邊位置上有一個(gè)或幾個(gè)葉結(jié)點(diǎn)缺少外，其他都是豐滿的，那么這樣的二叉樹就是完全二叉樹。

解釋二：除第h層外，其他各層（1到h-1）的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h層從右向左連續(xù)缺若干結(jié)點(diǎn)，則這個(gè)二叉樹就是完全二叉樹。

也就是說如果一個(gè)結(jié)點(diǎn)有右子結(jié)點(diǎn)，那么它一定也有左子結(jié)點(diǎn)。

解釋三：除了最后一層外，每一層上的節(jié)點(diǎn)數(shù)均達(dá)到最大值，在最后一層上只缺少右邊的若干結(jié)點(diǎn)。

完全二叉樹的形狀類似于下圖：

為了方便理解，請看下圖：

二叉樹相關(guān)名詞解釋：

結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹數(shù)目
葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)
分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)
樹的度：樹中結(jié)點(diǎn)的最大的度
層次：根結(jié)點(diǎn)的層次為1，其余結(jié)點(diǎn)的層次等于該結(jié)點(diǎn)的雙親結(jié)點(diǎn)的層次加1
樹的高度：樹中結(jié)點(diǎn)的最大層次

二叉樹基本性質(zhì)：

性質(zhì)1：在二叉樹的第k層上至多有2^k-1個(gè)結(jié)點(diǎn)（k>=1）
性質(zhì)2：在深度為m的二叉樹至多有2^m-1個(gè)結(jié)點(diǎn)
性質(zhì)3：對任意一顆二叉樹，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)
性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度至少為[log2n]+1，其中[log2n]表示log2n的整數(shù)部分

存儲方式

存儲方式和圖一樣，有鏈表和數(shù)組兩種，用數(shù)組存儲訪問速度快，但插入、刪除節(jié)點(diǎn)操作比較費(fèi)時(shí)。實(shí)際應(yīng)用中，更多的是采用鏈來表示二叉樹。

實(shí)現(xiàn)代碼：

#include <stdio.h>#include <stdlib.h>#define N 10typedef struct node{ char data; struct node *lchild; /* 左子樹 */ struct node *rchild; /* 右子樹 */}BiTNode, *BiTree;void CreatBiTree (BiTree *T) /* BiTree *T等價(jià)于 struct node **T */{ char ch; scanf("%c", &ch);

    if (ch == '#')    /* 當(dāng)遇到#時(shí)，令樹的結(jié)點(diǎn)為NULL，從而結(jié)束該分支的遞歸 */

{ *T = NULL; } else { *T = (BiTree)malloc(sizeof(BiTNode)); if (*T == NULL) { printf("內(nèi)存分配失敗"); exit(0); } (*T)->data = ch; /* 生成結(jié)點(diǎn) */ CreatBiTree(&(*T)->lchild); /* 構(gòu)造左子樹 */ CreatBiTree(&(*T)->rchild); /* 構(gòu)造右子樹 */ /* 這里需要注意的是->的優(yōu)先級比&高，所以&(*T)->lchild得到的是lchild的地址 */ }}int main(){ int level = 1; BiTree t = NULL; printf("以前序遍歷方式輸入二叉樹\n"); CreatBiTree(&t); /* 傳入指針的地址 */}

上面的實(shí)現(xiàn)代碼使用的是鏈表，代碼采用的是以前序遍歷方式輸入二叉樹，當(dāng)輸入“#”時(shí)，指針指向NULL，說明是該結(jié)點(diǎn)是葉結(jié)點(diǎn)。

三、二叉樹的遍歷（前序/中序/后序遍歷）

二叉樹的遍歷，是指不重復(fù)地訪問二叉樹中所有結(jié)點(diǎn)，主要指非空二叉樹，對于空二叉樹則結(jié)束返回，二叉樹的遍歷主要包括前序遍歷、中序遍歷、后序遍歷。

前序遍歷：首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹（根->左->右）

順序：訪問根節(jié)點(diǎn)->前序遍歷左子樹->前序遍歷右子樹

/* 以遞歸方式前序遍歷二叉樹 */void PreOrderTraverse(BiTree t, int level){ if (t == NULL) { return ; } printf("data = %c level = %d\n ", t->data, level); PreOrderTraverse(t->lchild, level + 1); PreOrderTraverse(t->rchild, level + 1);}

中序遍歷：首先遍歷左子樹，然后訪問根節(jié)點(diǎn)，最后遍歷右子樹（左->根->右）

順序：中序遍歷左子樹->訪問根節(jié)點(diǎn)->中序遍歷右子樹

/* 以遞歸方式中序遍歷二叉樹 */void PreOrderTraverse(BiTree t, int level){ if (t == NULL) { return ; } PreOrderTraverse(t->lchild, level + 1); printf("data = %c level = %d\n ", t->data, level); PreOrderTraverse(t->rchild, level + 1);}

后序遍歷：首先遍歷左子樹，然后遍歷右子樹，最后訪問根節(jié)點(diǎn)（左->右->根）

順序：后序遍歷左子樹->后序遍歷右子樹->訪問根節(jié)點(diǎn)

/* 以遞歸方式后序遍歷二叉樹 */void PreOrderTraverse(BiTree t, int level){ if (t == NULL) { return ; } PreOrderTraverse(t->lchild, level + 1); PreOrderTraverse(t->rchild, level + 1); printf("data = %c level = %d\n ", t->data, level);}

綜上所述，我們主要講解了樹、圖、二叉樹以及遍歷的基本知識點(diǎn)。從上面的分析中我們可以看出，樹的三種遍歷方式極其相似，只是語句 printf的位置發(fā)生了一些變化，其他語言實(shí)現(xiàn)類似，大家可自行實(shí)現(xiàn)。