“人生如夢，一樽還酹江月”

猛戳訂閱🍁🍁 👉 純C詳解數(shù)據(jù)結(jié)構(gòu)專欄 👈 🍁🍁

這里是目錄

• 普通樹的概念
• • 樹的特點
  • 樹的術(shù)語
  • 普通樹的表示
• 二叉樹概念
• • 二叉樹的性質(zhì)
• 數(shù)組二叉樹
• 鏈?zhǔn)蕉鏄?/li>
• • 學(xué)鏈?zhǔn)蕉鏄涞氖裁磧?nèi)容？
  • 二叉樹的遍歷
  • 前序遍歷
  • 中序遍歷
  • 后序遍歷
  • 層序遍歷

普通樹的概念

樹由 根 和 n 棵子樹組成，樹是非線性數(shù)據(jù)結(jié)構(gòu)。樹是遞歸定義的，這點很重要。

樹的特點

1.樹的子樹是不相交的。
2.除了根節(jié)點外，每個結(jié)點有且僅有一個父節(jié)點。
3.一棵N個節(jié)點的樹有N-1條邊。

樹的術(shù)語

以下加粗的為重點

樹的度：一棵樹中，最大的節(jié)點的度稱為樹的度

節(jié)點的層次：從根開始定義起，根為第一層，根的子節(jié)點為第二層。

數(shù)的高度或深度：樹中節(jié)點的最大層次。

節(jié)點的度：一個節(jié)點含有的子樹的個數(shù)成為該節(jié)點的度。

葉節(jié)點或終端節(jié)點：度為0的節(jié)點稱為葉節(jié)點；

雙親節(jié)點或父節(jié)點：若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點。

孩子節(jié)點或子節(jié)點：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點。

兄弟節(jié)點：具有相同父節(jié)點點節(jié)點稱為兄弟節(jié)點。親兄弟才是兄弟節(jié)點。

堂兄弟節(jié)點：雙親在同一層的節(jié)點護衛(wèi)堂兄弟。

節(jié)點的祖先：從根到該節(jié)點所經(jīng)分支上的所有節(jié)點。

子孫：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫。

森林：有m（m > 0）棵互不相交的數(shù)的集合稱為森林。

普通樹的表示

來看看先輩們創(chuàng)造的優(yōu)秀智慧。
存儲樹最優(yōu)秀的結(jié)構(gòu)：孩子兄弟表示法。
即：一個節(jié)點有多少個孩子都無所謂。父親指向第一個孩子，剩下的孩子，用孩子的兄弟指針連接起來。

typedef int DataType; struct Node {struct Node* _firstChild1; // 第一個孩子結(jié)點struct Node* _pNextBrother; // 指向其下一個兄弟結(jié)點DataType _data; // 結(jié)點中的數(shù)據(jù)域 };

二叉樹概念

二叉樹是我們要研究的重點。

二叉樹：一棵二叉樹是結(jié)點的一個有限集合。
該集合有兩種情況。
1.為空樹
2.由一個根節(jié)點加上兩棵別稱為左子樹和右子樹的二叉樹組成

二叉樹的特點：
1.二叉樹的度最大為2，即最多只有兩顆子樹。
2.二叉樹的子樹有有左右之分，次序不能顛倒，因此二叉樹是有序樹。
注意：因為二叉樹是遞歸定義的。
對于任意的二叉樹都是由以下幾種情況復(fù)合而成的

二叉樹的性質(zhì)

二叉樹的性質(zhì)是建立在兩種特殊的二叉樹上研究的。

1.滿二叉樹：每一層的結(jié)點數(shù)都達到了最大值。
2.完全二叉樹：前k-1層都是滿的，最后一層不滿，但是最后一層從左往右是連續(xù)的。

性質(zhì)1：若規(guī)定根節(jié)點的層數(shù)為1，則一棵非空二叉樹的第h層上最多有 2^h-1個結(jié)點.

性質(zhì)2：若規(guī)定根節(jié)點的層數(shù)為1，則深度為h的二叉樹的最大結(jié)點數(shù)是 2^h-1 .
解釋：根據(jù)等比數(shù)列前n項的和來看，n層相加得到2^h-1 。

性質(zhì)3：對任何一棵二叉樹, 如果度為0其葉結(jié)點個數(shù)為n₀ , 度為2的分支結(jié)點個數(shù)為n₂ ,則有 n₀＝n₂ ＋1

性質(zhì)4：若規(guī)定根節(jié)點的層數(shù)為1，具有n個結(jié)點的滿二叉樹的深度，h= log₂(n+1).
解釋：這是對2^h-1 = n公式的轉(zhuǎn)換。

性質(zhì)5：對于具有n個結(jié)點的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序對所有節(jié)點從0開始編號，則對
于下標(biāo)為i的結(jié)點有以下解釋：

1.i位置節(jié)點的雙親下標(biāo)：(i-1)/2
2.左孩子下標(biāo)：2i+1
3.右孩子下標(biāo)：2i+2

如圖。

數(shù)組二叉樹

上一章的堆，已經(jīng)敘述。

順序存儲
順序結(jié)構(gòu)存儲就是使用數(shù)組來存儲，一般使用數(shù)組只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費。而現(xiàn)實中使用中只有堆才會使用數(shù)組來存儲。二叉樹順序存儲在物理上是一個數(shù)組，在邏輯上是一顆二叉樹。

鏈?zhǔn)蕉鏄?/h1>

學(xué)鏈?zhǔn)蕉鏄涞氖裁磧?nèi)容？

普通二叉樹增刪查改沒有價值，如果是為了單純存放數(shù)據(jù)，不如用線性表。我們現(xiàn)在學(xué)習(xí)二叉樹，1.是為了更好的控制他的結(jié)構(gòu)，為后續(xù)學(xué)習(xí)復(fù)雜的搜索二叉樹打基礎(chǔ)
包括平衡搜索二叉樹：AVL數(shù)、紅黑樹。學(xué)習(xí)搜索二叉樹的意義在于可以用于搜索.
2.很多二叉樹OJ算法題，都出在普通二叉樹上。

二叉樹的遍歷

二叉樹是遞歸實現(xiàn)的
思想：

• 當(dāng)你看到一棵樹就要有一個思想，要把樹看成遞歸的，這點很重要。
• 任何一棵樹都要分為根，左子樹，右子樹。并且左右子樹到空才算結(jié)束。
• 遞歸就是大問題分成小問題，一直分解，直到不可分割后，就結(jié)束遞歸了。

前序遍歷

也叫先根遍歷，遍歷方式是， 根，左子樹，右子樹，根可以直接遍歷，左子樹和右子樹不可以直接遍歷，左子樹還會繼續(xù)分為根， 左子樹， 右子樹。

1 2 3 null null null 4 5 null null 6 null null

中序遍歷

也叫中根遍歷，遍歷方式是：左子樹， 根， 右子樹

null 3 null 2 null 1 null 5 null 4 null 6 null

后序遍歷

遍歷方式為：左子樹， 右子樹， 根

null null 3 null 2 null null 5 null null 6 4 1

層序遍歷

最簡單的遍歷，就是一層一層的遍歷。

1 2 4 3 5 6

總結(jié)

以上是生活随笔為你收集整理的植物大战 二叉树 概念——C的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。