一篇文章徹底弄懂Java中二叉樹
一、樹形結(jié)構(gòu)
樹是一種非線性的數(shù)據(jù)結(jié)構(gòu),它是由n(n>=0)
個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做樹是因?yàn)樗雌饋硐褚豢玫箳斓臉?,也就是說它是根朝上,而葉朝下的。它具有以下的特點(diǎn):
- 有一個(gè)特殊的節(jié)點(diǎn),稱為根節(jié)點(diǎn),根節(jié)點(diǎn)沒有前驅(qū)節(jié)點(diǎn);
- 除根節(jié)點(diǎn)外,其余節(jié)點(diǎn)被分成
M(M > 0)
個(gè)互不相交的集合T1、T2、......、Tm
,其中每一個(gè)集合Ti (1 <= i<= m)
又是一棵與樹類似的子樹。每棵子樹的根節(jié)點(diǎn)有且只有一個(gè)前驅(qū),可以有0個(gè)或多個(gè)后繼; - 樹是遞歸定義的。
1.1 相關(guān)概念
- 節(jié)點(diǎn)的度:一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)的度; 如上圖:A的度為6;
- 樹的度:一棵樹中,最大的節(jié)點(diǎn)的度稱為樹的度; 如上圖:樹的度為6;
- 葉子節(jié)點(diǎn)或終端節(jié)點(diǎn):度為0的節(jié)點(diǎn)稱為葉節(jié)點(diǎn); 如上圖:B、C、H、I…等節(jié)點(diǎn)為葉節(jié)點(diǎn);
- 雙親節(jié)點(diǎn)或父節(jié)點(diǎn):若一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn),則這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn); 如上圖:A是B的父節(jié)點(diǎn);
- 孩子節(jié)點(diǎn)或子節(jié)點(diǎn):一個(gè)節(jié)點(diǎn)含有的子樹的根節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn); 如上圖:B是A的孩子節(jié)點(diǎn);
- 根結(jié)點(diǎn):一棵樹中,沒有雙親結(jié)點(diǎn)的結(jié)點(diǎn);如上圖:A
- 節(jié)點(diǎn)的層次:從根開始定義起,根為第1層,根的子節(jié)點(diǎn)為第2層,以此類推;
- 樹的高度或深度:樹中節(jié)點(diǎn)的最大層次; 如上圖:樹的高度為4
以下概念僅做了解即可:
- 非終端節(jié)點(diǎn)或分支節(jié)點(diǎn):度不為0的節(jié)點(diǎn); 如上圖:D、E、F、G...等節(jié)點(diǎn)為分支節(jié)點(diǎn);
- 兄弟節(jié)點(diǎn):具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互稱為兄弟節(jié)點(diǎn); 如上圖:B、C是兄弟節(jié)點(diǎn);
- 堂兄弟節(jié)點(diǎn):雙親在同一層的節(jié)點(diǎn)互為堂兄弟;如上圖:H、I互為兄弟節(jié)點(diǎn);
- 節(jié)點(diǎn)的祖先:從根到該節(jié)點(diǎn)所經(jīng)分支上的所有節(jié)點(diǎn);如上圖:A是所有節(jié)點(diǎn)的祖先;
- 子孫:以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。如上圖:所有節(jié)點(diǎn)都是A的子孫;
- 森林:由m(m>=0)棵互不相交的樹的集合稱為森林。
1.2樹的表示形式
樹結(jié)構(gòu)相對線性表就比較復(fù)雜了,要存儲表示起來就比較麻煩了,實(shí)際中樹有很多種表示方式,如:雙親表示法,孩子表示法、孩子兄弟表示法等等。這里簡單的了解其中最常用的孩子兄弟表示法。
孩子兄弟表示法代碼示例:
class Node { int value; // 樹中存儲的數(shù)據(jù) Node firstChild; // 第一個(gè)孩子引用 Node nextBrother; // 下一個(gè)兄弟引用 }
圖示:
1.3樹的應(yīng)用:文件系統(tǒng)管理(目錄和文件)
二、二叉樹
2.1相關(guān)概念
一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合,該集合或者為空,或者是由一個(gè)根節(jié)點(diǎn)加上兩棵別稱為左子樹和右子樹的二叉樹組成。
二叉樹的特點(diǎn):
每個(gè)結(jié)點(diǎn)最多有兩棵子樹,即二叉樹不存在度大于 2 的結(jié)點(diǎn)。
二叉樹的子樹有左右之分,其子樹的次序不能顛倒,因此二叉樹是有序樹。
2.2 二叉樹的基本形態(tài)
上圖給出了幾種特殊的二叉樹形態(tài)。
從左往右依次是:空樹、只有根節(jié)點(diǎn)的二叉樹、節(jié)點(diǎn)只有左子樹、節(jié)點(diǎn)只有右
子樹、節(jié)點(diǎn)的左右子樹均存在,一般二叉樹都是由上述基本形態(tài)結(jié)合而形成的。
2.3 兩種特殊的二叉樹
滿二叉樹: 一個(gè)二叉樹,如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值,則這個(gè)二叉樹就是滿二叉樹。也就是說,如果一個(gè)二叉樹的層數(shù)為K,且結(jié)點(diǎn)總數(shù)是2k-1 ,則它就是滿二叉樹。
完全二叉樹: 完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu),完全二叉樹是由滿二叉樹而引出來的。對于深度為K的,有n個(gè)結(jié)點(diǎn)的二叉樹,當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號從1至n的結(jié)點(diǎn)一一對應(yīng)時(shí)稱之為完全二叉樹。(另一種解釋:如果二叉樹中除去最后一層節(jié)點(diǎn)為滿二叉樹,且最后一層的結(jié)點(diǎn)依次從左到右分布,則此二叉樹被稱為完全二叉樹。 )要注意的是滿二叉樹是一種特殊的完全二叉樹。
非完全二叉樹:
2.4 二叉樹的性質(zhì)
- 若規(guī)定根節(jié)點(diǎn)的層數(shù)為1,則一棵非空二叉樹的第i層上最多有2i-1 (i>0)個(gè)結(jié)點(diǎn);
- 若規(guī)定只有根節(jié)點(diǎn)的二叉樹的深度為1,則深度為K的二叉樹的最大結(jié)點(diǎn)數(shù)是2k-1 (k>=0);
- 對任何一棵二叉樹, 如果其葉結(jié)點(diǎn)個(gè)數(shù)為 n0, 度為2的非葉結(jié)點(diǎn)個(gè)數(shù)為 n2,則有n0=n2+1;
- 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度k為log2(n+1) 上取整;
- 對于具有n個(gè)結(jié)點(diǎn)的完全二叉樹,如果按照從上至下從左至右的順序?qū)λ泄?jié)點(diǎn)從0開始編號,則對于序號為i的結(jié)點(diǎn)有:
- 若
i>0
,雙親序號:(i-1)/2;i=0,i為根節(jié)點(diǎn)編號,無雙親節(jié)點(diǎn); - 若
2i+1<n
,左孩子序號:2i+1,否則無左孩子; - 若
2i+2<n
,右孩子序號:2i+2,否則無右孩子;
如:假設(shè)一棵完全二叉樹中總共有1000個(gè)節(jié)點(diǎn),則該二叉樹中__500___個(gè)葉子節(jié)點(diǎn),__500___個(gè)非葉子節(jié)點(diǎn),__1___個(gè)節(jié)點(diǎn)只有左孩子,__0___個(gè)只有右孩子。
題解:將該二叉樹節(jié)點(diǎn)縮小100倍,變?yōu)樵撏耆鏄渲锌偣灿?0個(gè)節(jié)點(diǎn),由性質(zhì)2可得深度K為:4,前三層共有7個(gè)節(jié)點(diǎn),則最后一層有10-7=3個(gè)節(jié)點(diǎn),由性質(zhì)1的第三層有4個(gè)節(jié)點(diǎn),其中有2個(gè)節(jié)點(diǎn)上面有子節(jié)點(diǎn),剩余2個(gè)為葉子結(jié)點(diǎn),則該二叉樹共有3+2=5個(gè)葉子結(jié)點(diǎn),擴(kuò)大100倍為500個(gè)葉子結(jié)點(diǎn),則剩余的就位非葉子結(jié)點(diǎn)。有相關(guān)分析可知該二叉樹有1個(gè)節(jié)點(diǎn)只有左孩子,0個(gè)節(jié)點(diǎn)只有右孩子。
2.5 二叉樹的存儲
二叉樹的存儲結(jié)構(gòu)分為:順序存儲和類似于鏈表的鏈?zhǔn)酱鎯?/strong>。
二叉樹的鏈?zhǔn)酱鎯?/strong>是通過一個(gè)一個(gè)的節(jié)點(diǎn)引用起來的,常見的表示方式有二叉和三叉表示方式,具體如下:
// 孩子表示法 class Node { int val; // 數(shù)據(jù)域 Node left; // 左孩子的引用,常常代表左孩子為根的整棵左子樹 Node right; // 右孩子的引用,常常代表右孩子為根的整棵右子樹 } // 孩子雙親表示法 class Node { int val; // 數(shù)據(jù)域 Node left; // 左孩子的引用,常常代表左孩子為根的整棵左子樹 Node right; // 右孩子的引用,常常代表右孩子為根的整棵右子樹 Node parent; // 當(dāng)前節(jié)點(diǎn)的根節(jié)點(diǎn) }
2.6 二叉樹的基本操作
2.6.1二叉樹的遍歷
遍歷(Traversal)
是指沿著某條搜索路線,依次對樹中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問。訪問結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問題(比如:打印節(jié)點(diǎn)內(nèi)容、節(jié)點(diǎn)內(nèi)容加1)。 遍歷是二叉樹上最重要的操作之一,是二叉樹上進(jìn)行其它運(yùn)算之基礎(chǔ)。
在遍歷二叉樹時(shí),如果沒有進(jìn)行某種約定,每個(gè)人都按照自己的方式遍歷,得出的結(jié)果就比較混亂,如果按照某種規(guī)則進(jìn)行約定,則每個(gè)人對于同一棵樹的遍歷結(jié)果肯定是相同的。如果N代表根節(jié)點(diǎn),L代表根節(jié)點(diǎn)的左子樹,R代表根節(jié)點(diǎn)的右子樹,則根據(jù)遍歷根節(jié)點(diǎn)的先后次序有以下遍歷方式:
- NLR:前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點(diǎn)—>根的左子樹—>根的右子樹。
- LNR:中序遍歷(Inorder Traversal)——根的左子樹—>根節(jié)點(diǎn)—>根的右子樹。
- LRN:后序遍歷(Postorder Traversal)——根的左子樹—>根的右子樹—>根節(jié)點(diǎn)。
由于被訪問的結(jié)點(diǎn)必是某子樹的根,所以N(Node)、L(Left subtree)
和R(Right subtree)
又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN
分別又稱為先根遍歷、中根遍歷和后根遍歷。
如上面這張圖,
其前序遍歷:ABDEHCFG
;
中序遍歷:DBEHAFCG
;
后序遍歷:DHEBFGCA
。
2.6.2 二叉樹的基本操作
構(gòu)建一顆二叉樹:
代碼示例:
class TreeNode{ public char val; public TreeNode left; public TreeNode right; public TreeNode(char val){ this.val = val; } } public class BinaryTree { //創(chuàng)建一個(gè)二叉樹 public TreeNode 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'); TreeNode H = new TreeNode('h'); A.left = B; A.right = C; B.left = D; B.right = E; E.right = H; C.left = F; C.right = G; return A; }
1. 前序遍歷
根–》左–》右
void preOrderTraversal(TreeNode root){ if(root == null){ return; } System.out.print(root.val + " "); preOrderTraversal(root.left); preOrderTraversal(root.right); }
測試代碼:
public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); TreeNode root = binaryTree.createTree(); binaryTree.preOrderTraversal(root);//前序遍歷 }
輸出結(jié)果:
2. 中序遍歷
左–》根–》右
// 中序遍歷 void inOrderTraversal(TreeNode root){ if(root == null){ return; } inOrderTraversal(root.left); System.out.print(root.val + " "); inOrderTraversal(root.right); }
測試代碼:
public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); TreeNode root = binaryTree.createTree(); binaryTree.inOrderTraversal(root);//中序遍歷 }
輸出結(jié)果:
3. 后序遍歷
左–》右–》根
// 后序遍歷 void postOrderTraversal(TreeNode root){ if(root == null){ return; } postOrderTraversal(root.left); postOrderTraversal(root.right); System.out.print(root.val + " "); }
測試代碼:
public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); TreeNode root = binaryTree.createTree(); binaryTree.postOrderTraversal(root);//后序遍歷 }
輸出結(jié)果:
4. 遍歷思路-求結(jié)點(diǎn)個(gè)數(shù)
static int size = 0;//靜態(tài)變量 void getSize1(TreeNode root){ if(root == null){ return; } size++; getSize1(root.left); getSize1(root.right); }
5. 子問題思路-求結(jié)點(diǎn)個(gè)數(shù)
int getSize2(TreeNode root){ if(root == null){ return 0; } return getSize2(root.left) + getSize2(root.right)+1; }
測試代碼:
public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); TreeNode root = binaryTree.createTree(); binaryTree.getSize1(root); System.out.println(BinaryTree.size); System.out.println("============"); System.out.println(binaryTree.getSize2(root)); }
輸出結(jié)果:
6. 遍歷思路-求葉子結(jié)點(diǎn)個(gè)數(shù)
//遍歷這顆二叉樹,只要節(jié)點(diǎn)的左子樹和右子樹都是空的,那么就是葉子 static int leafSize = 0; void getLeafSize1(TreeNode root){ if(root == null){ return; } if(root.left == null && root.right == null){ leafSize++; } getLeafSize1(root.left); getLeafSize1(root.right); }
7. 子問題思路-求葉子結(jié)點(diǎn)個(gè)數(shù)
//整棵樹的葉子結(jié)點(diǎn) = 左子樹葉子 + 右子樹葉子 int getLeafSize2(TreeNode root){ if(root == null){ return 0; } if(root.left == null && root.right == null){ return 1; } return getLeafSize2(root.left) + getLeafSize2(root.right); }
測試代碼:
public class test01 { public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); TreeNode root = binaryTree.createTree(); binaryTree.getLeafSize1(root); System.out.println(BinaryTree.leafSize);//遍歷思路-求葉子結(jié)點(diǎn)個(gè)數(shù) System.out.println("+++++++++++++"); //binaryTree.getLeafSize2(root); //System.out.println(BinaryTree.leafSize);//子問題思路-求葉子結(jié)點(diǎn)個(gè)數(shù) System.out.println(binaryTree.getLeafSize2(root)); }
輸出結(jié)果:
8. 子問題思路-求第 k 層結(jié)點(diǎn)個(gè)數(shù)
// 子問題思路-求第 k 層結(jié)點(diǎn)個(gè)數(shù) int getKLevelSize(TreeNode root,int k){ if(root == null){ return 0; } if(k == 1){ return 1; } return getKLevelSize(root.left,k-1) + getKLevelSize(root.right,k - 1); }
測試代碼:
public class test01 { public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); TreeNode root = binaryTree.createTree(); System.out.println(binaryTree.getKLevelSize(root,3)); }
輸出結(jié)果:
9. 獲取二叉樹的高度
int getHeight(TreeNode root){ if(root == null){ return 0; } int leftTree = getHeight(root.left); int rightTree = getHeight(root.right); return ((leftTree > rightTree) ? leftTree + 1 : rightTree + 1); }
測試代碼:
public class test01 { public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); TreeNode root = binaryTree.createTree(); int hight = binaryTree.getHeight(root); System.out.println(hight); }
輸出結(jié)果:
10. 查找val所在的節(jié)點(diǎn)
查找 val 所在結(jié)點(diǎn),沒有找到返回 null;
按照 根 -> 左子樹 -> 右子樹的順序進(jìn)行查找;
一旦找到,立即返回,不需要繼續(xù)在其他位置查找。
TreeNode find(TreeNode root, char val){ if(root == null){ return null; } if(root.val == val){ return root; } TreeNode ret = find(root.left,val); if(ret != null){ return ret; } ret = find(root.right,val ); if(ret != null){ return ret; } return null; }
測試代碼:
public class test01 { public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); TreeNode root = binaryTree.createTree(); //查找樹中得指定val值 TreeNode ret = binaryTree.find(root,'f');//如果沒有找到則顯示空指針異常 System.out.println(ret.val); }
輸出結(jié)果:
11.二叉樹的層序遍歷
// 層序遍歷 void levelOrderTraversal(TreeNode root){ if(root == null){ return; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()){ TreeNode top = queue.poll(); System.out.print(top.val+" "); if(top.left != null){ queue.offer(top.left); } if (top.right != null){ queue.offer(top.right); } } System.out.println(); }
測試代碼:
public class test01 { public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); TreeNode root = binaryTree.createTree(); binaryTree.levelOrderTraversal(root);//層序遍歷 }
輸出結(jié)果:
12.判斷一棵樹是不是完全二叉樹
// 判斷一棵樹是不是完全二叉樹 boolean isCompleteTree(TreeNode root){ if(root == null){ return true; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()){ TreeNode top = queue.poll();//彈出一個(gè)元素 if(top != null){ queue.offer(top.left); queue.offer(top.right); }else{ break; } } while (!queue.isEmpty()){ TreeNode cur = queue.peek(); if (cur == null){ queue.poll(); }else { //說明不是完全二叉樹 return false; } } return true; }
測試代碼:
public class test01 { public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); TreeNode root = binaryTree.createTree(); //判斷一棵樹是不是完全二叉樹 System.out.println(binaryTree.isCompleteTree(root)); }
輸出結(jié)果:
13.非遞歸實(shí)現(xiàn)前序遍歷
//非遞歸實(shí)現(xiàn) // 前序遍歷 void preOrderTraversalNor(TreeNode root) { if (root == null) { return; } TreeNode cur = root; Stack<TreeNode> stack = new Stack<>(); while (cur != null || !stack.empty()) { while (cur != null) { stack.push(cur); System.out.print(cur.val + " "); cur = cur.left; } TreeNode top = stack.pop(); cur = top.right; } }
14.非遞歸實(shí)現(xiàn)中序遍歷
// 中序遍歷 void inOrderTraversalNor(TreeNode root){ if (root == null) { return; } TreeNode cur = root; Stack<TreeNode> stack = new Stack<>(); while (cur != null || !stack.empty()){ while (cur != null){ stack.push(cur); cur = cur.left; } TreeNode top = stack.pop(); System.out.print(top.val + " "); cur = top.right; } }
15.非遞歸實(shí)現(xiàn)后序遍歷
// 后序遍歷非遞歸 void postOrderTraversalNor(TreeNode root){ if (root == null) { return; } TreeNode cur = root; Stack<TreeNode> stack = new Stack<>(); TreeNode pre = null;//用來指定上一個(gè)被打印過的元素 while (cur != null || !stack.empty()){ while (cur != null){ stack.push(cur); cur = cur.left; } cur = stack.peek(); if(cur.right == null || cur.right == pre ){ TreeNode popNode = stack.pop(); System.out.print(popNode.val + " "); pre = cur; cur = null; }else { cur = cur.right; } } }
測試代碼:
public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); TreeNode root = binaryTree.createTree(); // binaryTree.preOrderTraversal(root);//前序遍歷 //System.out.println(); binaryTree.preOrderTraversalNor(root);//前序遍歷非遞歸 System.out.println(); //binaryTree.postOrderTraversal(root);//后序遍歷 //System.out.println(); binaryTree.postOrderTraversalNor(root);//后序遍歷非遞歸 System.out.println(); //binaryTree.inOrderTraversal(root);//中序遍歷 //System.out.println(); binaryTree.inOrderTraversalNor(root);//中序遍歷非遞歸 System.out.println(); }
輸出結(jié)果:前、后、中
以上。
總結(jié)
到此這篇關(guān)于Java中二叉樹的文章就介紹到這了,更多相關(guān)Java中二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Java實(shí)現(xiàn)雙鏈表互相交換任意兩個(gè)節(jié)點(diǎn)的方法示例
這篇文章主要介紹了Java實(shí)現(xiàn)雙鏈表互相交換任意兩個(gè)節(jié)點(diǎn)的方法,簡單講述了雙鏈表的概念,并結(jié)合實(shí)例形式給出了java雙鏈表實(shí)現(xiàn)任意兩個(gè)節(jié)點(diǎn)交換的操作技巧,需要的朋友可以參考下2017-11-11SpringBoot中Bean拷貝及工具類封裝的實(shí)現(xiàn)
本文主要介紹了SpringBoot中Bean拷貝及工具類封裝的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-05-05SpringBoot實(shí)現(xiàn)圖片識別文字的四種方式小結(jié)
本文主要介紹了SpringBoot實(shí)現(xiàn)圖片識別文字的四種方式,包括Tess4J,百度智能云,阿里云,騰訊云這四種,具有一定的參考價(jià)值,感興趣的可以了解一下2024-02-02使用SpringBoot簡單了解Druid的監(jiān)控系統(tǒng)的配置方法
這篇文章主要介紹了使用SpringBoot簡單了解Druid的監(jiān)控系統(tǒng)的配置,本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-06-06