作者 | 小鹿
來源 | 小鹿動(dòng)畫學(xué)編程
前邊幾篇文章的講了數(shù)組、鏈表、隊(duì)列等，今天和大家主要分享的是樹這種數(shù)據(jù)結(jié)構(gòu)。
樹這種數(shù)據(jù)結(jié)構(gòu)不像數(shù)組、鏈表一樣，它是一種非線性結(jié)構(gòu)，學(xué)起來可能比其他數(shù)據(jù)結(jié)構(gòu)比較吃力，但是它在數(shù)據(jù)結(jié)構(gòu)中占有很重要的地位，也是面試中的頻繁考點(diǎn)，尤其是二叉樹，一定注重起來。
由題目拋出的問題，樹到底怎么存儲(chǔ)呢？二叉樹有幾種存儲(chǔ)方式呢？如果帶著好奇心學(xué)習(xí)，學(xué)習(xí)更加的高效，一顆樹橫七豎八的，咋表示？下邊小鹿帶你一起來探索。
顧名思義，第一想到的就是路邊的樹，有樹干、樹根、樹葉，數(shù)據(jù)結(jié)構(gòu)中的樹也是這樣延伸過來的，只不過專用名詞不一樣，直接上圖。
有一些樹的專屬名詞我們總結(jié)下，A 是 B 的父節(jié)點(diǎn)，B 是 A 的子節(jié)點(diǎn)，D 是 B 的兄弟節(jié)點(diǎn)，C 和 D 稱為葉子節(jié)點(diǎn)，A 為根節(jié)點(diǎn)。
是樹它就有高度，數(shù)據(jù)結(jié)構(gòu)中的樹不僅有高度的概念，還有樹的深度、層，節(jié)點(diǎn)的高度、深度等，一些最基本的知識(shí)點(diǎn)。
高度
樹的高度就是根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長(zhǎng)路徑。節(jié)點(diǎn)的高度就是節(jié)點(diǎn)到葉子節(jié)點(diǎn)的高度。
節(jié)點(diǎn)的深度就是該節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑，也就是邊的數(shù)量。
根節(jié)點(diǎn)為第一層，依次往下遞增。
我們知道什么是樹了，二叉樹的概念，就是給樹做了一個(gè)限制，除了葉子結(jié)點(diǎn)，其余每個(gè)節(jié)點(diǎn)僅且只有兩個(gè)子節(jié)點(diǎn)（也就是只有兩個(gè)叉）。
二叉樹有兩個(gè)很重要的形態(tài)就是滿二叉樹和完全二叉樹。
滿二叉樹：葉子節(jié)點(diǎn)全都在最底層，除了葉子節(jié)點(diǎn)之外，每個(gè)節(jié)點(diǎn)都有左右兩個(gè)子節(jié)點(diǎn)，這種二叉樹就叫作滿二叉樹。
完全二叉樹：葉子節(jié)點(diǎn)都在最底下兩層 ，最后一層的葉子節(jié)點(diǎn)都靠左排列，并且除了最后一層，其他層的節(jié)點(diǎn)個(gè)數(shù)都要達(dá)到最大。
既然我們都基本了解了二叉樹的概念和基本常識(shí)，那我們要用，就要進(jìn)行存儲(chǔ)，如何存儲(chǔ)一顆二叉樹呢？
還記不記得小鹿之前的幾篇文章一直強(qiáng)調(diào)說過，所有基本常見的數(shù)據(jù)結(jié)構(gòu)都是由數(shù)組和鏈表演變而來，棧有順序棧和鏈?zhǔn)綏?、?duì)列有順序隊(duì)列和鏈?zhǔn)疥?duì)列，那么樹可以用數(shù)組存儲(chǔ)也可以用鏈表存儲(chǔ)呀。
鏈?zhǔn)酱鎯?chǔ)法
基于指針的鏈?zhǔn)酱鎯?chǔ)，每個(gè)樹的節(jié)點(diǎn)都是由數(shù)據(jù)域和兩個(gè)指針域組成的。數(shù)據(jù)域用來存儲(chǔ)數(shù)據(jù)，指針域用來存儲(chǔ)左右兩個(gè)子節(jié)點(diǎn)。
順序存儲(chǔ)法
順序存儲(chǔ)就是用數(shù)組來存儲(chǔ)的，雖然不如指針域那么直觀，但是存儲(chǔ)的方法挺好理解的。根節(jié)點(diǎn)存儲(chǔ)在下標(biāo) i = 1 的位置；左子節(jié)點(diǎn)存儲(chǔ)在下標(biāo)i * 2 = 2的位置，右子節(jié)點(diǎn)存儲(chǔ)在i * 2 + 1 =3的位置。
你會(huì)問，兩種方式有什么區(qū)別，這個(gè)問題其實(shí)你早就知道了，如果你看到過小鹿之前寫的文章，就知道區(qū)別就是數(shù)組和鏈表的區(qū)別。
數(shù)組的方式存儲(chǔ)不需要開辟額外的指針空間，但是數(shù)組需要的內(nèi)存空間是連續(xù)的，如果連續(xù)的內(nèi)存空間不足，就無法進(jìn)行存儲(chǔ)。
既然存儲(chǔ)方式你也學(xué)會(huì)了，那么我們看看二叉樹存儲(chǔ)的數(shù)據(jù)，我們?nèi)绾伪闅v出來呢？
共有四種遍歷的方式，分別為前序遍歷、中序遍歷、后序遍歷、按層遍歷。
這個(gè)前、中、后遍歷，初學(xué)者最不容易理解，當(dāng)初小鹿學(xué)習(xí)的時(shí)候也是這樣，那我用最簡(jiǎn)單的步驟和圖來講述一下。
我們以前序遍歷為例子，首先我要告訴你前序遍歷的規(guī)則，就是先遍歷根節(jié)點(diǎn)、然后遍歷左子節(jié)點(diǎn)最后遍歷右子節(jié)點(diǎn)，上圖：
這個(gè)圖，你很快就能知道前序遍歷的順序，答案為：A->B->C
但是我換一張圖，你來前序遍歷下。
你可能就懵逼了，咋和剛才的不一樣？我就是按照剛才那樣遍歷的？無論你是否成功遍歷，小鹿來講一下自己的思路。
我們還是看根節(jié)點(diǎn)的三個(gè)節(jié)點(diǎn)，按照根、左、右，我們知道先輸出根節(jié)點(diǎn) A、然后輸出左子節(jié)點(diǎn)，因?yàn)?B 作為 D 和 E 的根節(jié)點(diǎn)先輸出，然后 B 的左子節(jié)點(diǎn)是 D，D 作為 F 的根節(jié)點(diǎn)也要輸出 D。
然后開始遍歷左子節(jié)點(diǎn)，D 根節(jié)點(diǎn)的左子節(jié)點(diǎn)為 F，所以輸出 F, B 的左子節(jié)點(diǎn)已經(jīng)輸出完畢，所以遍歷右子節(jié)點(diǎn) E。那么整個(gè) A 的左子節(jié)點(diǎn)已經(jīng)全部輸出完畢，開始遍歷 A 額右子節(jié)點(diǎn)。
還是按照左、根、右的遍歷方法，依次輸出去 C、H。整體的前序遍歷為：A->B->D->F->E->C->H。動(dòng)畫如下：
前序遍歷小鹿講的很詳細(xì)了，剩下的中序遍歷和后續(xù)遍歷的規(guī)則不一樣。中序遍歷先遍歷左子節(jié)點(diǎn)，然后是根節(jié)點(diǎn)，最后是右子節(jié)點(diǎn)。而后序遍歷的順序是先遍歷左子結(jié)點(diǎn)，然后遍歷右子節(jié)點(diǎn)，最后遍歷根節(jié)點(diǎn)。
其實(shí)和前序遍歷道理都是一樣的，只不過是換湯不換藥，我把動(dòng)圖放到下放了，自己可以對(duì)照著遍歷一下。
1//遍歷二叉查找樹
2//前序遍歷
3preorderTraversal = (tree) =>{
4 //判斷樹是否為空
5 if(tree == null) return false;
6 //根節(jié)點(diǎn)
7 console.log(tree.data)
8 //左子樹
9 this.preorderTraversal(tree.left)
10 //右子樹
11 this.preorderTraversal(tree.right)
12}
13
14//中序遍歷
15inorderTraversal = (tree) =>{
16 //判斷樹是否為空
17 if(tree == null) return false;
18 //左子樹
19 this.inorderTraversal(tree.left);
20 //根節(jié)點(diǎn)
21 console.log(tree.data)
22 //右節(jié)點(diǎn)
23 this.inorderTraversal(tree.right);
24}
25
26//后序遍歷
27postorderTraversal = (tree) =>{
28 //判斷樹是否為空
29 if(tree == null) return false;
30 //左子樹
31 this.postorderTraversal(tree.left);
32 //右子樹
33 this.postorderTraversal(tree.right);
34 //根節(jié)點(diǎn)
35 console.log(tree.data)
36}
Java 版本
1 /**
2 * 時(shí)間:2019/2/24
3 * 功能:前序遍歷
4 * @param root 樹的根節(jié)點(diǎn)
5 */
6 public void preorderTraversal(Node root) {
7 //如果樹為空
8 if(root == null) return;
9 //根節(jié)點(diǎn)
10 System.out.print(root.data + ' ');
11 //左子樹
12 inorderTraversal(root.left);
13 //右子樹
14 inorderTraversal(root.right);
15
16 }
17
18 /**
19 * 時(shí)間:2019/2/24
20 * 功能:中序遍歷
21 * @param root 樹的根節(jié)點(diǎn)
22 */
23 public void inorderTraversal(Node root) {
24 //如果樹為空
25 if(root == null) return;
26 //左子樹
27 inorderTraversal(root.left);
28 //根節(jié)點(diǎn)
29 System.out.print(root.data + ' ');
30 //右子樹
31 inorderTraversal(root.right);
32
33 }
34
35 /**
36 * 時(shí)間:2019/2/24
37 * 功能:后序遍歷
38 * @param root 樹的根節(jié)點(diǎn)
39 */
40 public void postorderTraversal(Node root) {
41 //如果樹為空
42 if(root == null) return;
43 //左子樹
44 inorderTraversal(root.left);
45 //右子樹
46 inorderTraversal(root.right);
47 //根節(jié)點(diǎn)
48 System.out.print(root.data + ' ');
49
50 }
Python 版本
1class BTree(object):
2 def __init__(self):
3 self._root = None
4 self._size = 0
5
6 def preOrder(self):
7 '''
8 先遍歷順序：前序遍歷
9 1，根節(jié)點(diǎn)
10 2，遍歷左子樹
11 3，遍歷右子樹
12 '''
13 btree = []
14
15 def recurse(node):
16 if node != None:
17 btree.append(node.data)
18 recurse(node.lft)
19 recurse(node.rgt)
20
21 recurse(self._root)
22 return btree
23
24class BTree(object):
25 def __init__(self):
26 self._root = None
27 self._size = 0
28
29 def preOrder(self):
30 '''
31 先遍歷順序：中序遍歷
32 1，根節(jié)點(diǎn)
33 2，遍歷左子樹
34 3，遍歷右子樹
35 '''
36 btree = []
37
38 def recurse(node):
39 if node != None:
40 btree.append(node.data)
41 recurse(node.lft)
42 recurse(node.rgt)
43
44 recurse(self._root)
45 return btree
46
47class BTree(object):
48 def __init__(self):
49 self._root = None
50 self._size = 0
51
52 # 后序遍歷
53 def postOrder(self):
54 '''
55 后序遍歷順序：后續(xù)遍歷
56 1，遍歷左子樹
57 2，遍歷右子樹
58 3，根節(jié)點(diǎn)
59 '''
60 btree = []
61
62 def recurse(node):
63 if node != None:
64 recurse(node.lft)
65 recurse(node.rgt)
66 btree.append(node.data)
67
68 recurse(self._root)
69 return btree
C 語(yǔ)言版本
1#include <stdio.h>
2#include <stdlib.h>
3
4/* 定義數(shù)據(jù)類型 */
5typedef char TypeData ;
6
7/* 定義二叉樹 */
8typedef struct stBiTreeNode
9{
10 TypeData data;
11 struct stBiTreeNode *lchild, *rchild;
12}BITREENODE;
13
14/* 初始化二叉樹 */
15BITREENODE* createBiTree()
16{
17 char chTempData = 0;
18
19 BITREENODE *pstNewNode = NULL;
20
21 scanf('%c',&chTempData);
22 if(chTempData == '#')
23 {
24 pstNewNode = NULL;
25 }
26 else
27 {
28 /* 分配內(nèi)存 */
29 pstNewNode = (BITREENODE*)malloc(sizeof(BITREENODE) + 1);
30 pstNewNode->data = chTempData;
31
32 /* 遞歸調(diào)用產(chǎn)生二叉樹 */
33 pstNewNode->lchild = createBiTree();
34 pstNewNode->rchild = createBiTree();
35 }
36
37 return pstNewNode;
38}
39
40/* 前序遍歷二叉樹 */
41int preVisitBiTree(BITREENODE* InRoot)
42{
43 if(InRoot)
44 {
45 /* 先遍歷根節(jié)點(diǎn) */
46 printf('%c ',InRoot->data);
47
48 /* 遍歷左子樹 */
49 preVisitBiTree(InRoot->lchild);
50
51 /* 遍歷右子樹 */
52 preVisitBiTree(InRoot->rchild);
53
54 }
55 return 0;
56}
57
58
59/* 中序遍歷二叉樹 */
60int inVisitBiTree(BITREENODE* InRoot)
61{
62 if(InRoot)
63 {
64 /* 遍歷左子樹 */
65 preVisitBiTree(InRoot->lchild);
66
67
68 /* 先遍歷根節(jié)點(diǎn) */
69 printf('%c ',InRoot->data);
70
71 /* 遍歷右子樹 */
72 preVisitBiTree(InRoot->rchild);
73
74 }
75 return 0;
76}
77
78/* 后序遍歷二叉樹 */
79int postVisitBiTree(BITREENODE* InRoot)
80{
81 if(InRoot)
82 {
83 /* 遍歷左子樹 */
84 preVisitBiTree(InRoot->lchild);
85
86
87 /* 遍歷右子樹 */
88 preVisitBiTree(InRoot->rchild);
89
90
91 /* 先遍歷根節(jié)點(diǎn) */
92 printf('%c ',InRoot->data);
93
94 }
95 return 0;
96}
今天小鹿分享了二叉樹的基礎(chǔ)部分，二叉樹的基本概念以及二叉樹的存儲(chǔ)方式，還有二叉樹的前中后遍歷，最后留一個(gè)問題就是，二叉樹除了前中后序遍歷外，還有按層遍歷，可以自己去探索一下二叉樹按層是怎么遍歷的？
