與樹有關(guān)的一系列知識: 樹,二叉樹,滿二叉樹,完全二叉樹,文章還沒完,我會后序補充的

• 一: 樹(了解就行)
• • 1.1 概念
  • 1.2 一些與樹相關(guān)的重要概念
  • 1.3 樹的表示形式
• 二: 二叉樹(非常重要,重點掌握)
• • 2.1 概念
  • 2.2 兩種特殊的二叉樹
  • • 2.2.1 滿二叉樹
    • 2.2.2 完全二叉樹
  • 2.3 二叉樹的性質(zhì)
  • 2.4 二叉樹的基本操作
  • • 2.4.1手動快速創(chuàng)建一棵簡單的二叉樹
    • 2.4.2 二叉樹的遍歷
    • • a. 前中后序遍歷(遞歸操作)
      • b. 前中后序遍歷(非遞歸)
      • c. 層次遍歷
    • 2.4.3 還原二叉樹
    • • a.通過前序和中序的結(jié)果還原二叉樹
      • b.通過中序和后序的結(jié)果還原二叉樹
      • c.通過層次遍歷的結(jié)果還原二叉樹.
    • 2.4.4 二叉樹的基本操作方法

有些圖是網(wǎng)上找的,沒有自己畫

一: 樹(了解就行)

1.1 概念

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu),它是由n(n>=0)個有限節(jié)點組成的一個具有層次關(guān)系的集合.
叫成樹的原因: 看起來像是一棵倒著的樹,它的根朝上,而葉子是朝下的.
樹的一些特點:
a. 有一個特殊的節(jié)點,稱為根節(jié)點,根節(jié)點沒有前驅(qū)節(jié)點.
b. 除根節(jié)點外,其余的節(jié)點被分成M(M>0)個互不相交的集合T,T2,T3…Tm,其中每一個集合又是一棵與樹類似的子樹.
c. 一棵n個節(jié)點的樹有n-1條邊.
d. 除根節(jié)點外,每個節(jié)點有且僅有一個父節(jié)點
e. 子樹是不能相交的.
f. 樹是遞歸定義的.

1.2 一些與樹相關(guān)的重要概念

節(jié)點的度: 一個節(jié)點含有子樹的個數(shù)稱為該節(jié)點的度
比如:上圖中節(jié)點A的度為2,節(jié)點D的度為3.

樹的度: 一顆樹中,所有節(jié)點度的最大值稱為樹的度
比如:上圖中樹的度為3

葉子節(jié)點或終端節(jié)點: 度為0的節(jié)點稱為葉子節(jié)點或者終端節(jié)點
比如:上圖中的葉子節(jié)點有:F,G,H,I,J.

雙親節(jié)點或父節(jié)點: 如果一個節(jié)點含有子節(jié)點,這個節(jié)點就稱為子節(jié)點的父節(jié)點或者雙親節(jié)點.
比如:上圖中的A是B,C的父節(jié)點.

孩子節(jié)點或子節(jié)點: 一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點.
比如:上圖中的B,C是A的孩子節(jié)點.

根節(jié)點: 樹種沒有雙親的節(jié)點.(位于食物鏈頂端的節(jié)點)
比如:上圖中的A節(jié)點.

節(jié)點的層次: 從根開始定義起,根為第一層,根的子節(jié)點為第二層,依次類推

樹的高度或深度: 樹中節(jié)點的最大層次.
比如:上圖中樹的深度為4

非終端節(jié)點或分支節(jié)點: 度不為0的節(jié)點
比如:上圖中的B,D節(jié)點

兄弟節(jié)點: 具有相同父節(jié)點的節(jié)點稱為兄弟節(jié)點
比如:上圖中的G,H,I節(jié)點

堂兄弟節(jié)點: 雙親在同一層的節(jié)點互為堂兄弟
比如:上圖中的D,E節(jié)點

節(jié)點的祖先: 從根節(jié)點到該節(jié)點所經(jīng)分支上的所有節(jié)點
比如:G節(jié)點的祖先節(jié)點是A,B,D節(jié)點.而A節(jié)點是所有節(jié)點的祖先節(jié)點.

子孫節(jié)點: 以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫.
比如:上圖中D節(jié)點的子孫節(jié)點是G,H,I.而所有節(jié)點都是A的子孫節(jié)點.

森林: 有m(m>0)棵互不相交的樹組成的集合稱為森林.

1.3 樹的表示形式

樹有很多種表現(xiàn)形式,但是最常用的是這里的孩子兄弟表示法
a.雙親表示法

節(jié)點既要存儲值域,還必須表示其雙親的位置.
優(yōu)點: 快速知道該節(jié)點的雙親.
缺點: 無法快速知道該節(jié)點的孩子.

class Node{int value; //存儲的數(shù)據(jù)Node parent; //指向父節(jié)點 }

b.孩子表示法

節(jié)點既要存儲值域,還要表示與孩子之間的關(guān)系.
優(yōu)點: 快速知道該節(jié)點的孩子.
缺點: 無法快速知道該節(jié)點的雙親

class Node{int value; //存儲的數(shù)據(jù)Node left; //指向左孩子,常常代表左孩子為根的整棵左子樹Node right; //指向右孩子,常常代表右孩子為根的整棵右子樹 }

c.孩子雙親表示法

將孩子表示法和雙親表示法結(jié)合起來了.

class Node{int value; //存儲的數(shù)據(jù)Node left; //指向左孩子,常常代表左孩子為根的整棵左子樹Node right; //指向右孩子,常常代表右孩子為根的整棵右子樹Node parent; //當前節(jié)點的父節(jié)點. }

d.孩子兄弟表示法

在這個節(jié)點中,既要保存值域,還要保存下一個兄弟在哪一個位置.

class Node{int value; //樹中存儲的數(shù)據(jù)Node firstChild; //第一個孩子的引用Node nextBrother; //下一個兄弟的引用 }

二: 二叉樹(非常重要,重點掌握)

2.1 概念

滿足: 1.為空樹時,是二叉樹 2.由根節(jié)點+左子樹+右子樹組成.

一棵二叉樹是節(jié)點的一個有限集合:
a.集合可以為空: 表示這是一棵空樹
b.不為空: 由一個根節(jié)點加上兩棵分別稱為左子樹和右子樹的二叉樹組成
c.二叉樹不存在度大于2的節(jié)點(此節(jié)點的孩子子節(jié)點個數(shù)只能<=2)
d.二叉樹的子樹有左右之分,次序不能顛倒,依次二叉樹是有序樹.

注意: 對于任意的二叉樹都是由以下集中情況復(fù)合而成的.

2.2 兩種特殊的二叉樹

2.2.1 滿二叉樹

一棵二叉樹,如果每層的節(jié)點數(shù)都能達到最大值,則這棵二叉樹就是滿二叉樹.
如果一棵二叉樹的層數(shù)為k,且它的節(jié)點數(shù)是(2^k)-1,則它也是滿二叉樹.

2.2.2 完全二叉樹

完全二叉樹是由滿二叉樹引出來的.滿二叉樹是一種特殊的完全二叉樹.

設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點數(shù)都達到飽和(即1~h-1層為一個滿二叉樹)，第 h 層所有的結(jié)點都從左往右依次排列，這樣的樹就是完全二叉樹。

完全二叉樹

我們來舉一個例子:看下面這張圖,就不是完全二叉樹,因為E節(jié)點只有F一個子節(jié)點，但是F子節(jié)點沒有排在E節(jié)點的左邊

2.3 二叉樹的性質(zhì)

1.若規(guī)定根節(jié)點的層數(shù)為1,則一棵非空二叉樹的第i層上最多有 2^(i-1) 個節(jié)點(i>0).
2.若規(guī)定只有根節(jié)點的二叉樹的深度為1,則深度為k的文二叉樹的最大節(jié)點數(shù)是 (2^k)-1(k>=0).
3.對任何一棵二叉樹,如果其葉子幾點個數(shù)為n0,度為2的非葉子節(jié)點個數(shù)為n2,則有n0=n2+1.
4.具有n個結(jié)點的完全二叉樹的深度k為

向上取整
5.對于具有n個結(jié)點的完全二叉樹，如果按照 從上至下從左至右 的順序?qū)λ泄?jié)點從0開始編號，則對于序號為i的結(jié)點有：

• 若i>0，雙親序號：(i-1)/2；i=0，i為根結(jié)點編號，無雙親結(jié)點
• 若2i+1<n，左孩子序號：2i+1，否則無左孩子
• 若2i+2<n，右孩子序號：2i+2，否則無右孩子

2.4 二叉樹的基本操作

2.4.1手動快速創(chuàng)建一棵簡單的二叉樹

這段代碼并不是創(chuàng)建二叉樹的方式,真正創(chuàng)建二叉樹方法后序會重點講解.

//孩子表示法來表示二叉樹. public class BinaryTree{public static class BTNode{BTNode left; //引用當前孩子的左孩子BTNode right; //引用當前孩子的右孩子int value; //值域//有參構(gòu)造方法BTNode(int value){this.value = value;}}private BTNode root; //二叉樹的根節(jié)點public void createBinaryTree(){BTNode node1 = new BTNode(1); //創(chuàng)建節(jié)點node1,它的值為1BTNode node1 = new BTNode(2);BTNode node1 = new BTNode(3);BTNode node1 = new BTNode(4);BTNode node1 = new BTNode(5);BTNode node1 = new BTNode(6);root = node1; //根節(jié)點就是node1節(jié)點node1.left = node2; //node1的左孩子是node2node1.right = node4; //node1的右孩子是node4node2.left = node3; //node2的左孩子是node3node4.left = node5; //node4的左孩子是node5node4.right = node6; //node5的右孩子是node6} }

由以上代碼創(chuàng)建出來的二叉樹為下圖所示:

2.4.2 二叉樹的遍歷

例圖:

a. 前中后序遍歷(遞歸操作)

學(xué)習(xí)二叉樹結(jié)構(gòu),最簡單的方式就是遍歷.

遍歷: 所謂遍歷是指沿著某條路徑搜索路線,依次對樹中每個節(jié)點均做一次且僅做一次訪問.
用N代表根節(jié)點,L代表根的左子樹,R代表根的右子樹.則有以下遍歷方式 (用上圖演示)

指的是對節(jié)點中的值域進行打印.
NLR:前序遍歷----------------根節(jié)點---->根的左子樹---->根的右子樹
1–>2–>3–>4–>5–>6

public void preOrder(BtNode reeRoot){//先判斷是否為空if(treeRoot==null){return;}//1.先遍歷根節(jié)點System.out.print(treeRoot.value+" ");//2.再遍歷根節(jié)點的左子樹----->根節(jié)點的左子樹也是二叉樹(遍歷根的左子樹與遍歷原樹的規(guī)則相同)preOrder(treeRoot.left); //遞歸遍歷根的左子樹//3.最后遍歷根節(jié)點的右子樹----->根的右子樹也是二叉樹(遍歷根的右子樹與遍歷原樹的規(guī)則相同)preOrder(treeRoot.right); //遞歸遍歷根的右子樹 }

LNR:中序遍歷----------------根的左子樹---->根節(jié)點---->根的右子樹
3–>2–>1–>5–>4–>6

public void inOrder(BtNode reeRoot){if(treeRoot==null){return;}inOrder(treeRoot.left); System.out.print(treeRoot.value+" ");inOrder(treeRoot.right); }

LRN:后序遍歷----------------根的左子樹---->根的右子樹---->根節(jié)點
3–>2–>5–>6–>4–>1

public void postOrder(BtNode reeRoot){if(treeRoot==null){return;}postOrder(treeRoot.left); postOrder(treeRoot.right); System.out.print(treeRoot.value+" "); }

b. 前中后序遍歷(非遞歸)

非遞歸采用的是List和棧的數(shù)據(jù)結(jié)構(gòu)來進行實現(xiàn)的.
利用棧先進后出的特點來實現(xiàn)前中后序的遍歷,再用list來接收節(jié)點的值,最后list中的數(shù)據(jù)就是遍歷的結(jié)果.

注意：在下面我只給了前序遍歷的講解圖，中序和后序遍歷大家自己根據(jù)對前序遍歷的理解，對應(yīng)代碼畫一下，剛好作為一個思考和練習(xí)題。

前序遍歷:

a.創(chuàng)建對象List和棧的對象為list,s.
b.用cur標記root節(jié)點,然后將cur進行入棧操作.
c.當棧不為空時,節(jié)點出棧然后用cur接收.
d.當cur不為空時,將此時cur節(jié)點的值add到list中.
e.然后判斷此時的cur有沒有右孩子,有的話就將右孩子進行入棧操作.然后cur指向左孩子
最后重復(fù)d過程,當cur為空時再從c過程開始執(zhí)行.
最后list中存儲的數(shù)據(jù)就是前序遍歷的結(jié)果.文字可能看起來不怎么清楚,我們直接上圖形.
大家一定要對照著下面的代碼去看圖,然后根據(jù)代碼自己在紙上畫一遍,才能更好的理解和掌握

當s不為空時,進入whlie循環(huán):



因為此時的cur為null了,所以得從c步驟重新開始再走一遍.s不為null.

public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list=new ArrayList<>();Stack<TreeNode> s=new Stack<>();TreeNode cur=root;s.push(cur);while(!s.empty()){cur=s.pop();while(cur!=null){list.add(cur.val);if(cur.right!=null){s.push(cur.right);}cur=cur.left;}}return list; }

中序遍歷

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list=new ArrayList<>();if(root==null){//說明是空樹，直接返回一個空的list就行。return list;}TreeNode cur=root;Stack<TreeNode> s=new Stack<>();while(!s.empty()||cur!=null){while(cur!=null){s.push(cur);cur=cur.left;}cur=s.pop();list.add(cur.val);cur=cur.right;}return list; }

后序遍歷

public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list=new ArrayList<>();if(root==null){return list;}TreeNode cur=root;TreeNode prev=null;Stack<TreeNode> s=new Stack<>();while(!s.empty()||cur!=null){while(cur!=null){s.push(cur);cur=cur.left;}TreeNode top=s.peek();if(top.right==null || top.right==prev){list.add(top.val);prev=top;s.pop();}else{cur=top.right;}}return list;}

c. 層次遍歷

從所在二叉樹的根節(jié)點出發(fā),首先訪問第一層的樹根節(jié)點,然后從左往右訪問第二層的節(jié)點,接著是第三層,以此類推,自上而下,自作向右逐層訪問樹的節(jié)點的過程就是層序遍歷.

比如上圖經(jīng)過層次遍歷的結(jié)果就是:1--->2--->4--->3--->5--->6.

2.4.3 還原二叉樹

a.通過前序和中序的結(jié)果還原二叉樹

還原思想:

前序: 根 左子樹 右子樹—通過前序遍歷結(jié)果可以找到二叉樹或者其子樹的根節(jié)點
中序: 右子樹 根 左子樹—在中序結(jié)果中找到根的位置,根左邊的是左子樹的節(jié)點,右邊是右子樹的節(jié)點.

來看個例題:

前序遍歷結(jié)果: EFHIGJK,中序遍歷結(jié)果: HFIEJKG,請還原二叉樹

題解:

我們通過前序遍歷的結(jié)果可以得出二叉樹的根節(jié)點為E,通過中序遍歷結(jié)果可知HFI是根的左子樹,JKG是根的右子樹.

再通過前序遍歷可知左子樹的根節(jié)點為F,所以H是F的左節(jié)點,I是F的右節(jié)點.

從前序結(jié)果當中可知,G是右子樹的根節(jié)點,J是G的左子樹,然后從中序遍歷可知,K是J的右子樹.
最后還原后的圖形為:

b.通過中序和后序的結(jié)果還原二叉樹

還原思想:

后序: 左子樹 右子樹 根----在后序結(jié)果中確定二叉樹的根節(jié)點.
中序: 右子樹 根 左子樹----在中序結(jié)果中找到根的位置,根左邊的是左子樹的節(jié)點,右邊是右子樹的節(jié)點.

來看個例題:

中序遍歷結(jié)果為:badce,后序遍歷結(jié)果為:bdeca

題解:

先從后序遍歷結(jié)果中確定二叉樹的根節(jié)點為a,再從中序結(jié)果中得知a的左子樹是b,a的右子樹是dce

從后序結(jié)果可知c是右子樹的根節(jié)點.從中序結(jié)果可知,d是c的左子樹,e是c的右子樹.

注意:通過前序遍歷結(jié)果和后序遍歷結(jié)果不能還原出二叉樹.
前序:根 左子樹 右子樹
后序:左子樹 右子樹 根
只能找到根節(jié)點,不能確定根節(jié)點的左右子樹.

c.通過層次遍歷的結(jié)果還原二叉樹.

這個相對來說就很簡單了,自上而下,自左向右進行還原就行.
比如層次遍歷結(jié)果是abcde,還原二叉樹.
我們直接給出圖形就行:

2.4.4 二叉樹的基本操作方法

方法名作用

int size(Node root)	獲取樹中節(jié)點的個數(shù)
int getLeafNodeCount(Node root)	獲取葉子節(jié)點的個數(shù)
int getLevelNodeCount(Node root)	獲取第k層節(jié)點的個數(shù)
int getHeight(Node root)	獲取二叉樹的高度
Node find(Node root,int value)	檢測值為value的元素是否存在
boolean is CompleteTree(Node root)	判斷一棵樹是不是完全二叉樹

總結(jié)

以上是生活随笔為你收集整理的数据结构---与树相关的知识的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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