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

知識分享家 2021-04-19

展開全文

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

二叉樹的遍歷

一、樹

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

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

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

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

通常情況下，我們在對樹進行討論的時候，將一棵樹中的每個點稱為結(jié)點:

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

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

二、二叉樹

1. 基本概念

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

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

二叉樹一般采用鏈式存儲結(jié)構(gòu)，存儲結(jié)點由數(shù)據(jù)域和指針域組成，二叉樹的鏈式存儲結(jié)構(gòu)也稱為二叉鏈表。

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

特點：

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

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

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

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

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

完全二叉樹：

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

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

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

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

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

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

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

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

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

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

存儲方式

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

實現(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等價于 struct node **T */{ char ch; scanf("%c", &ch); if (ch == '#') /* 當遇到#時，令樹的結(jié)點為NULL，從而結(jié)束該分支的遞歸 */ { *T = NULL; } else { *T = (BiTree)malloc(sizeof(BiTNode)); if (*T == NULL) { printf("內(nèi)存分配失敗"); exit(0); } (*T)->data = ch; /* 生成結(jié)點 */ 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); /* 傳入指針的地址 */}

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

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

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

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

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

/* 以遞歸方式前序遍歷二叉樹 */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é)點，最后遍歷右子樹（左->根->右）

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

/* 以遞歸方式中序遍歷二叉樹 */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é)點（左->右->根）

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

/* 以遞歸方式后序遍歷二叉樹 */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);}

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