新年新氣象! 祝大家兔年 財源滾滾! 萬事勝意!

---

前言

二叉樹也是筆試中?？嫉闹R點,大家要掌握及時回顧噢~

---

1. 樹的一些基礎概念

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu),它是由n個有限結(jié)點組成的一個具有層次關系的集合,像一棵倒掛的樹,根在上,葉子在下.

1.1 樹的一些基本概念

如上圖,是一顆二叉樹,因為每個結(jié)點最多有兩個孩子結(jié)點.

以下介紹節(jié)點的基本情況
1.根節(jié)點: 根節(jié)點沒有前驅(qū)節(jié)點
2.葉子節(jié)點: 沒有孩子結(jié)點的節(jié)點
3.樹中同一棵樹的子樹與子樹之間不能有交集.
4.每棵樹除了根節(jié)點都只能有一個父親節(jié)點.
5.一棵樹如果有N個節(jié)點,那么他就有N-1條邊.

如下圖

第一個,C與D同是A的子樹,C與D之間不能有交集.
第二個,E只能有一個父親節(jié)點,不能有B,C兩個父親節(jié)點.
第三個,也是G不能有A,D兩個父親節(jié)點.

1.2 樹的一些重要概念

1.節(jié)點的度: 一個節(jié)點含有子樹的個數(shù).二叉樹中,節(jié)點的度可以為0,1,2.葉子結(jié)點的度就是0.
2…樹的度: 所有節(jié)點的度的最大值為樹的度
3.結(jié)點的層次: 根節(jié)點為第一層,依次類推遞增
4.樹的高度或深度: 樹中節(jié)點的最大層次為樹的高度.
5.兄弟節(jié)點: 父親節(jié)點相同的節(jié)點互為兄弟節(jié)點.
6.節(jié)點的子孫: 以該節(jié)點為根節(jié)點的子樹中的任意節(jié)點都是該節(jié)點的子孫.樹中所有節(jié)點都是根節(jié)點的子孫.

2. 二叉樹的一些基本概念

2.1 二叉樹的結(jié)構(gòu)

二叉樹是節(jié)點的有限結(jié)合.
二叉樹可以為空,也可以只有一個根節(jié)點,每個結(jié)點最多可以有兩個孩子節(jié)點.
所以二叉樹有以下四種基本情況.

2.2 兩種特殊的二叉樹

1.滿二叉樹,如下圖,每層的節(jié)點都達到最大值.滿滿登登的.

滿二叉樹,第K層的節(jié)點數(shù)目為
2.完全二叉樹,如下圖,樹從左到右要連續(xù)的,從第一個節(jié)點到最后一個節(jié)點之間不能有為空的節(jié)點.

3. 二叉樹的性質(zhì)

1.一棵非空二叉樹,以根節(jié)點為第一層,第N層節(jié)點最大數(shù)目為2的n-1次冪.
2.一顆深度為K的非空二叉樹,總共節(jié)點最大數(shù)目為2的K次冪-1.
原理如下,一個深度為4的樹,最大節(jié)點總數(shù)計算過程如下.

3.一棵二叉樹,設其葉子節(jié)點個數(shù)為n0,度為2(有兩個孩子節(jié)點)的節(jié)點個數(shù)為n2,則n0 = n2 + 1.
4.具有N個節(jié)點的完全二叉樹的深度為log2⁽ⁿ⁺¹⁾向上取整.
5.若第一個節(jié)點從0開始編號,第i個節(jié)點(除了根節(jié)點),他的父親節(jié)點編號為(i-1)/2.
6.若第一個節(jié)點從0開始編號,第i個節(jié)點,若它有左右孩子節(jié)點,它的左孩子節(jié)點編號為2i+1,右孩子編號為2i+2.

例題

解析:
葉子節(jié)點為n0,n0 = n2 +1,n0 = 200.

解析:
完全二叉樹有如下兩種情況.

第一種,節(jié)點個數(shù)為偶數(shù),只有一個度為1的節(jié)點,其余都是度為0和度為2的節(jié)點
第二種,節(jié)點個數(shù)為奇數(shù),全都是度為2和度為0的節(jié)點.
本題節(jié)點個數(shù)為偶數(shù),是第一種情況,只有一個度為1的節(jié)點.

節(jié)點總數(shù) = n0 + n1 + n2

解析:
這道題與上道題類似,個數(shù)為奇數(shù),只有度為0和度為2的節(jié)點.

767 = n0 + n2
767 = n0 + n0 -1
n0 = 384

k = log2^(531 +1)
k = 10

4. 二叉樹的存儲

二叉樹可以有順序存儲和鏈式存儲.我們這節(jié)先介紹鏈式存儲.
二叉樹是由結(jié)點和結(jié)點與結(jié)點之間的的引用構(gòu)成.
鏈式存儲有二叉三叉表示方法.
第一種是孩子表示法.

class TreeNode{public TreeNode left;//節(jié)點左孩子public TreeNode right;//節(jié)點右孩子public int value;//節(jié)點值
}

第二種是雙親(孩子和父親)表示法.

class TreeNode{public TreeNode left;public TreeNode right;public TreeNode parent;//節(jié)點的父親節(jié)點public int value;
}

本節(jié)介紹第一種表示方式.

5. 二叉樹的基本操作

5.1 構(gòu)造一棵二叉樹

我們先用簡單的方式構(gòu)造一棵二叉樹.

	public void createTree(){TreeNode A = new TreeNode('A');TreeNode B = new TreeNode('B');TreeNode C = new TreeNode('C');TreeNode D = new TreeNode('D');TreeNode E = new TreeNode('E');TreeNode F = new TreeNode('F');TreeNode G = new TreeNode('G');root = A;A.left = B;A.right = C;B.left = D;B.right = E;C.left = F;C.right = G;}

5.2 二叉樹的遍歷

遍歷二叉樹根據(jù)遍歷順序不同有三種遍歷方式: 前序遍歷,中序遍歷,后序遍歷.

5.2.1 前序遍歷

前序遍歷的順序為: 根結(jié)點->左子樹->右子樹.
如下圖,具體操作是

1. 先遍歷整棵樹的根節(jié)點A
2. 之后遍歷根的左子樹BDE,如下圖,以BDE為一棵樹,以根->左->右的順序,先遍歷樹的根節(jié)點B,再遍歷樹的左子樹D,再遍歷樹的右子樹E.
   
3. 遍歷根節(jié)點的右子樹CFG,如下圖,先遍歷CFG的根節(jié)點C,再左子樹F,再右子樹G
   
   所以,這棵樹的前序遍歷順序為ABDECFG.

代碼實現(xiàn)

	public  void preOrder(TreeNode root){//根左右if(root == null){return;}System.out.print(root.val + " ");preOrder(root.left);preOrder(root.right);}

5.2.2 中序遍歷

中序遍歷的順序是左子樹->根節(jié)點->右子樹

1. 先找根節(jié)點A的左子樹BDE,如下圖,再根據(jù)左->根->右的順序,以B為根,先遍歷B的左子樹D,之后是B,再B的右子樹E.
   
2. 遍歷完根節(jié)點的左子樹之后遍歷根節(jié)點A.
3. 之后再以左->根->右的順序遍歷根節(jié)點A的右子樹.
   排好序如下圖,這棵樹中序遍歷為DBEAGCH
   
   代碼實現(xiàn)

	public void inOrder(TreeNode root){//左根右if(root == null){return;}inOrder(root.left);System.out.print(root.val);inOrder(root.right);}

5.2.3 后序遍歷

后序遍歷的順序是 左子樹->右子樹->根
如下圖
1.先遍歷根節(jié)點A的左子樹BDE,以B為根節(jié)點,以左右根的順序遍歷,結(jié)果是DEB.

2.左子樹遍歷完了,再遍歷根節(jié)點A的右子樹CFG,以左右根的順序,遍歷結(jié)果為FGC
3.A的左右子樹遍歷完畢,最后遍歷根節(jié)點A
如下圖,后續(xù)遍歷順序為DEBFGCA

代碼實現(xiàn)

	public void postOrder(TreeNode root){//左右根if(root == null){return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val + " ");}

5.2.4 層序遍歷

如下圖,按照從左到右,從上到下的順序遍歷.遍歷順序為ABCDEFG

5.2.# 遍歷順序相關練習題

解答:樹為完全二叉樹,中間是沒有空缺的樹的.所以A是根節(jié)點,B是A的左孩子節(jié)點,C是A的右孩子節(jié)點.
DE分別為B的左右孩子.GH分別為C的左右孩子.所以這棵樹前序遍為:ABDHECFG,選A.

解答:很簡單哈,先序遍歷的第一個節(jié)點就是根節(jié)點,選A

解答:
1.先看后續(xù)節(jié)點的倒數(shù)第一個節(jié)點A,這個節(jié)點為根節(jié)點.
2.根據(jù)中序遍歷中根節(jié)點的位置,根節(jié)點左側(cè)結(jié)點為根節(jié)點的左子樹.根節(jié)點右側(cè)結(jié)點為根節(jié)點的右子樹.
3.再看后序遍歷的倒數(shù)第二個節(jié)點C,這是右子樹的根.(因為遍歷完右子樹才會輪到根節(jié)點,所以倒數(shù)第二節(jié)點就是右子樹的根)
4.對應中序遍歷中C的位置,C的左側(cè)結(jié)點為C的左子樹,C右側(cè)節(jié)點的C的右子樹.
對應這題,后序遍歷的最后一個結(jié)點是根節(jié)點,所以,這顆樹的根節(jié)點是A.
中序遍歷根節(jié)點左側(cè)是左子樹,根節(jié)點右側(cè)是右子樹.所以,B是根節(jié)點的左子樹.
再看后序遍歷倒數(shù)第二個節(jié)點C,它是右子樹的根.
對應中序遍歷,C的左側(cè)節(jié)點是它的左子樹.C的右側(cè)節(jié)點是他的右子樹.所以,D是C的左孩子,E是C的右孩子.
綜上,畫出二叉樹,選D


解答:
根節(jié)點為后序遍歷最后一個節(jié)點F為根節(jié)點
對應中序遍歷,F左側(cè)為F的左子樹,所以,F只有左子樹,無右子樹.
因為無右子樹,后序遍歷倒數(shù)第二個節(jié)點E為左子樹的根節(jié)點
對應中序遍歷,E的左側(cè)為E的左子樹.
以此類推,畫出的樹如下
層序遍歷: FECBA,選A.

5.3 獲取二叉樹中節(jié)點個數(shù)

每次的返回值是這個節(jié)點左右孩子結(jié)點的數(shù)量再加上自己的節(jié)點,

	public int nodeCount(TreeNode root){if(root == null){return 0;}int tmp = nodeCount(root.left) + nodeCount(root.right) + 1;return tmp;}

5.4 樹中葉子節(jié)點個數(shù)

樹中葉子節(jié)點的特點是無左右孩子結(jié)點.
與上一題相似,這道題只有符合要求的節(jié)點就加1.

	public static int LeafNum(TreeNode root){//看節(jié)點的左孩子是否為空,再看右孩子是否為空.全部符合則count++.if(root == null){return 0;}int count = 0;if(root.left == null && root.right == null){return 1;}return LeafNum(root.left) + LeafNum(root.right);}

5.5 反轉(zhuǎn)二叉樹

反轉(zhuǎn)二叉樹,需要將根的左子樹與右子樹交換,再將每顆小樹的左孩子與右孩子交換.

	public TreeNode reverseTree(TreeNode root){if(root == null){return null;}TreeNode tmp = root.left;root.left = root.right;root.right = root.left;reverseTree(root.left);reverseTree(root.right);return root;}

5.6 判斷樹是不是完全二叉樹

 //判斷樹是不是完全二叉樹public static boolean completeBinaryTree(TreeNode root){if(root == null){return true;}if(root.left == null || root.right == null){return false;}boolean b1 = completeBinaryTree(root.left);boolean b2 = completeBinaryTree((root.right));return b1 && b2;}

5.7 判斷兩棵樹是否相同

//判斷兩樹相同，結(jié)構(gòu)相同，數(shù)相同。時間復雜度O( min(r, s) )public static boolean sameTree(TreeNode root1, TreeNode root2){if(root1 == null && root2 != null){return false;}if(root1 != null && root2 == null){return false;}if(root1 == null && root2 == null){return true;}if(root1.val != root2.val){return false;}boolean b = sameTree(root1.left,root2.left);boolean b2 = sameTree(root1.right,root2.right);return b && b2;}

5.8 判斷一棵樹是否為另一顆樹的子樹

只要樹2等于樹1的任意子樹就為真

//看樹是不是別的樹的子樹，時間復雜度，O(r * s)public static boolean subtreeJudge(TreeNode root1, TreeNode root2){if(root1 == null || root2 == null){return false;}if(sameTree(root1,root2)){return true;}//注意這里，當root1為空的時候，取不到root1的left，造成空指針異常if(subtreeJudge(root1.left,root2)){return true;}if(subtreeJudge(root1.right,root2)){return true;}return false;}

5.9 查找值是否存在

//查找value是否存在public TreeNode lookupValue(TreeNode root,char val){if(root == null){return null;}if(root.val == val){return root;}TreeNode ret = lookupValue(root.left,val);if(ret != null){return ret;}TreeNode ret2 = lookupValue(root.right,val);if(ret2 != null) {return ret2;}//樹的左右結(jié)點都走完了，都沒找到，返回空return null;}

---

多鞏固,多復習.祝前程似錦!