認識二叉樹
樹的概念?
? 樹是一種非線性資料結構，它是由n（n>=0）個有限節點組成的一個具有層次關系的集合，之所以叫做樹，是因為從外觀上來看這個結構，其很像一棵樹，并且根還在最上面，
關于樹的一些基本概念??
- 節點的度：一個幾點向下連了幾條邊，那這個節點的度就是幾
- 樹的度：一棵樹中具有最大度的節點的度數就是整棵樹的度
- 葉子節點或終端節點：如果一個節點沒有孩子，或者說度為0，那這個節點就是葉子
- 雙親節點：剛才說的度是一個節點往下連接別的節點，這里的雙親結點就是一個節點往上的第一個節點，就是此節點的雙親節點
- 孩子節點：與雙親節點相反唄
- 根節點：顧名思義：樹根，樹根只能生孩子，沒有雙親
- 節點的層次：根所在層為第1層，根的孩子節點為第二層，一次類推
- 樹的高度或者深度：一棵樹的最大層次就是整棵樹的高度
- 非終端節點或分支節點：度不為零的節點
- 兄弟節點：同一個雙親生下來的節點間叫兄弟節點
- 堂兄弟節點：爺爺生了倆孩子，這倆孩子再生倆孫子，這倆孫子就是堂兄弟
- 節點的祖先：整棵樹的根
- 子孫：一個節點只要有孩子甚至孫子，，，那這個節點的后代都是它的子孫
- 森林：有m（m>=0）棵互不相交的樹的集合，一片森林里可以有很多樹，也可有0棵樹
樹的表示方法🥚
-
常見的如孩子兄弟表示法
class Node{ int val; Node firstChild; Node nextBrother; }![[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-uBbcX8lX-1645867245859)(C:\Users\LebronHarden\AppData\Roaming\Typora\typora-user-images\image-20220226122644542.png)]](https://img.uj5u.com/2022/02/27/302096271057091.png)
二叉樹🤜
概念🚡
? 一顆二叉樹是節點的一個有限集合，該集合或者為空，或者是由一個根節點加上兩棵分別稱為左子樹和右子樹的二叉樹組成，
特點😋
- 每個節點最多有兩顆子樹，即二叉樹中的每個節點的度最大為2
- 二叉樹的子樹有左右之分，其子樹的次序不能顛倒，因此二叉樹是有序樹
特殊的二叉樹💛
- 滿二叉樹：一個二叉樹，只不過每一層的節點都達到最大值，如果層次為k，則這一層的最大節點數：2（k-1），很簡單的明白：層數為k的滿二叉樹的總結點數：2k-1個
- 完全二叉樹：滿二叉樹缺了右下角若干個節點就是完全二叉樹，若干可以為0，即滿二叉樹是一種特殊的完全二叉樹
二叉樹的性質🗂
-
整棵樹的根若層次為1，則二叉樹的第k層的最大節點數：2^(k-1)個
-
由1可以推匯出，一棵k層的二叉樹的總的最大節點數為2^k-1個
-
任何一棵二叉樹，度為2的節點數總是比葉子節點數多1個
-
具有n個節點的二叉樹的深度為log2（n+1）往上取整
-
重要(該性質常用于堆內)👹
按層序遍歷的順序從0開始給二叉樹的節點依次標記序號，對于序號為i的節點：
- 若這個節點有雙親，則雙親的標號為：（i-1）/2
- 若這個節點有左孩子，則左孩子的序號為：2*i+1
- 若這個節點有右孩子，則右孩子的序號為：2*i+2
對3推導：
二叉樹的總結點數為n，度為0的節點數為N0,度為1的節點數為N1,度為2的節點數為N2
則：n=N0+N1+N2
因為n個節點的二叉樹，具有n-1條邊(因為根上面沒有邊)
則：n-1=N1+2*N2
對上述兩個式子計算可得：N2=N0+1,證畢
對4的推導：
層數定死了的話，完全二叉樹可以添加若干個節點使自身變成一棵滿二叉樹，但此時的整棵樹的深度并沒有發生變化，之所以往滿二叉樹作改變，是因為滿二叉樹的總結點數量有現成的公式：2^k-1（k就是整棵樹的深度）
∴2^k-1=n
∴k=log2(n+1),證畢
練習:
具有2n個節點的完全二叉樹的葉子有多少個？
解：設度為0的節點個數為n0,度為1的節點個數為n1，度為2的節點個數為n2
∴2n=n0+n1+n2
此處n1恒等于1，因為1要和第一層的根加起來組成偶數才能滿足整個樹的節點個數為偶數
即：2n=n0+n2+1
由∵n0=n2+1
∴2n=n0+n0-1+1=2n0 故：n0=n
自己實作一個簡單的二叉樹（用最常見的孩子表示法）🥇
class BTNode{
public int val;
public BTNode left;
public BTNode right;
public BTNode(int val) {
this.val = val;
}
}
public class MyBinaryTree {
public BTNode root;
public BTNode createTree(){
BTNode node1=new BTNode(1);
BTNode node2=new BTNode(2);
BTNode node3=new BTNode(3);
BTNode node4=new BTNode(4);
BTNode node5=new BTNode(5);
//連接
node1.left=node2;
node1.right=node3;
node2.left=node4;
node2.right=node5;
root=node1;
return root;
}
}
二叉樹的遍歷🉑
所有二叉樹相關的題目都是需要通過某種遍歷來實作
- 遍歷方式：前序、中序、后序遍歷
- 前序遍歷（Preorder Traversal）：根左右為序
- 中序遍歷（Inorder Traversal）：左根右為序
- 后序遍歷（Postorder Traversal）：左右根為序
前序遍歷🛰
如上圖：前序遍歷列印：123456
代碼：
public void preOrder(BTNode root){
if(root==null){
return;
}
System.out.print(root.val+" ");
preOrder(root.left);
preOrder(root.right);
}
中序遍歷🗡
上圖中序遍歷結果：321546
代碼：
public void inOrder(BTNode root){
if(root==null){
return;
}
inOrder(root.left);
System.out.print(root.val+" ");
inOrder(root.right);
}
后序遍歷🚅
上圖后序遍歷結果：325641
代碼：
public void postOrder(BTNode root){
if(root==null){
return;
}
inOrder(root.left);
inOrder(root.right);
System.out.print(root.val+" ");
}
力扣有前中后序遍歷相關的例題，見我的力扣博客
層序遍歷🥂
從第一層往下，從左往右，依次遍歷的方式就叫層序遍歷
代碼實作的時候，我們可以借助于佇列，先將root入隊，佇列不為空時：出隊一個元素，對該元素的左右孩子進行檢查，若不為空則入隊，為空則不如隊，并且每次彈出的元素都用另外一個線性結構存一下，最后按順序把線性結構里的元素注意列印就是層序遍歷的結果
代碼：
public void levelOrder(BTNode root){
if(root==null) return;
Queue<BTNode> queue=new LinkedList<>();
Queue<BTNode> ans=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
BTNode front=queue.poll();//記錄好，等下還要入隊到ans里頭呢
if(front.left!=null) queue.offer(front.left);
if(front.right!=null) queue.offer(front.left);
ans.offer(front);
}
//列印ans
while(!ans.isEmpty()){
BTNode front=ans.poll();
System.out.print(front.val+" ");
}
}
只知道前中后序的其中兩個不可以得到唯一的二叉樹
二叉樹的一些基本操作🎠
-
獲取樹的節點個數
public int size(BTNode root){ if(root==null){ return 0; } return 1+size(root.left)+size(root.right); } -
獲取葉子的個數
public int leafCount(BTNode root){ if(root==null){ return 0; } //root!=null if(root.left==null&&root.right==null){ return 1; } return leafCount(root.left)+leafCount(root.right); } -
第k層節點個數
public int getKLevelNodeCount(BTNode root,int k){ if(root==null||k<=0) return 0; if(k==1) return 1; return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1); } -
獲取一棵二叉樹的高度
public int height(BTNode root){ if(root==null){ return 0; } //當前的root不為null，至少至少能為當前這棵樹的高度貢獻1 return Math.max(height(root.left),height(root.right))+1; } -
查找二叉樹中是否包含關鍵字key
public BTNode find(BTNode root,int key){ if(root==null) return null; if(root.val==key) return root; BTNode left=find(root.left,key); if(left!=null) return left; BTNode right=find(root.right,key); if(right!=null) return right; return null; }//根左右為序進行遍歷的 -
判斷一棵樹是不是完全二叉樹
? 可以借助佇列，把root入隊，再彈出，只要彈出的元素不為null,我們就將root.left和root.right都入隊，只要某一次出隊的元素是null,我們就停止迭代，檢查佇列中是否都是null,只要存在不是null的元素，就說明這棵樹不是完全二叉樹，可以畫個圖理解一下這背后的邏輯，（是不是發現了入進去的元素恰好就是層序遍歷的順序將節點逐一入隊的？那如果都彈出null了，佇列里還有不是null的元素，是不是就說明這棵樹不是完全二叉樹了呢？）
代碼：
public boolean isCompleteTree(BTNode root){ if(root==null) return true;//空樹默認是吧，這個不是最重要的 Queue<BTNode> queue=new LinkedList<>(); queue.offer(root); while(queue.peek()!=null){ BTNode front=queue.poll(); queue.offer(front.left); queue.offer(front.right); } while(!queue.isEmpty()){ BTNode front=queue.poll(); if(front!=null){ return false; } } return true; } -
檢查兩棵樹是否相同（力扣100）
遞回最重要的就是看終止條件：本題的話兩棵樹要想相同，首先結構得相同，其次節點的值相同才算完成一個節點之間的比較，最后，遍歷到葉子往后了，可不敢影響我們的結果，
class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if((p==null&&q!=null)||(p!=null&&q==null)) return false;//結構都不一樣，肯定不對 //要么都為空，要么都不為空 if(p==null&&q==null){ return true;//葉子往后可不敢影響結果 } //都不為空的情況 if(p.val!=q.val) return false; //上面這么多終止條件都沒攔住，那就繼續往下遍歷唄 return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right); } } -
另一棵樹的子樹(力扣572)
因為剛才已經學會了如何判斷兩棵樹是不是相同的，我們就可以基于此，寫這道題
class Solution { private boolean isSameTree(TreeNode p,TreeNode q){ if((p==null&&q!=null)||(p!=null&&q==null)){ return false; } if(p==null&q==null) return true; if(p.val!=q.val) return false; return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right); } public boolean isSubtree(TreeNode root, TreeNode subRoot) { if(root==null) return false; if(isSameTree(root,subRoot)) return true; return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot); }//本質還是根左右為序進行遍歷 } -
平衡二叉樹（力扣110）
class Solution { private int height(TreeNode root){ if(root==null) return 0; return Math.max(height(root.left),height(root.right))+1; } public boolean isBalanced(TreeNode root) { if(root==null) return true; if(height(root.left)-height(root.right)>1) return false; if(height(root.right)-height(root.left)>1) return false; return isBalanced(root.left)&&isBalanced(root.right); } }對本題提供一個巧妙的解法：在算樹高的時候就可以判斷這棵樹是不是平衡二叉樹了,思想就是，當前樹根的左右子樹只有平衡的時候我才正常的去求當前樹的高度，否則我就回傳一個-1，一旦某個區域子樹不平衡了，將會導致整棵樹的高度都是負數，那我們就可以很輕松的知道一棵樹是不是平衡二叉樹了呀，
class Solution { private int height(TreeNode root){ if(root==null) return 0; int leftHeght=height(root.left); int rightHeight=height(root.right); if(leftHeght>=0&&rightHeight>=0&&Math.abs(leftHeght-rightHeight)<=1){ return Math.max(leftHeght,rightHeight)+1; }else{ return -1; } } public boolean isBalanced(TreeNode root) { if(height(root)<0){ return false; } return true; } } -
對稱二叉樹（力扣101）
可以假想是兩棵一模一樣的樹進行比較，只不過比較位置有所講究
class Solution { private boolean isSymmetricChild(TreeNode p,TreeNode q){ if((p==null&&q!=null)||(p!=null&&q==null)) return false;//結構都不一樣還比較個毛線 //能到這說明要么都為空，要么都不為空 if(p==null&&q==null) return true;//這種情況不需進一步進行節點值的判斷 //都不為空 if(p.val!=q.val) return false; //上述是就一個節點的判斷 return isSymmetricChild(p.left,q.right)&&isSymmetricChild(p.right,q.left); } public boolean isSymmetric(TreeNode root) { if(root==null) return true; return isSymmetricChild(root.left,root.right); } }
前面提到了層序遍歷，要知道層序遍歷可以干很多事，比如阿里巴巴考過的一道題：給出一棵二叉樹的左視圖，左視圖的意思是：將每一層的第一個節點作存盤；又如求一棵樹的寬度，意思就是說一棵樹的某一層具有的節點數比這棵樹的其他層的節點數都要多，那這一層的節點數量就是這棵樹的寬度
二叉樹的繼續學習🔐
見我的力扣專欄關于二叉樹的題目，
?
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/433329.html
標籤：AI
上一篇：python_DataFrame的loc和iloc取資料 基本方法總結
下一篇：pandas使用groupby函式和agg函式獲取每個分組特定變數獨特值的個數（number of distinct values in each group in dataframe）