樹的概念及結構

樹的概念

樹是一種非線性的資料結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合，把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根在上，而葉在下的，

有一個特殊的結點，稱為根結點，根節點沒有前驅結點，除根節點外，其余結點被分成m(m > 0)個互不相交的集合T1、T2、…… 、Tm，其中每一個集合Ti(1 <= i <= m)又是一棵結構與樹類似的子樹，每棵子樹的根結點有且只有一個前驅，但可以有0個或多個后繼，

由此可知，樹是遞回定義的，

下面是一個簡單的樹，

圖中根節點就是沒有父結點的結點，葉子結點就是沒有子節點的結點，

還要注意：樹的子樹是不相交的；除了根節點外，每個結點有且僅有一個父結點，

下面介紹一些與樹相關的概念（以上面的樹為例）：

（1）結點的度：一個節點含有的子樹的個數稱為該節點的度；如上圖：A的為6，即B、C、D、E、F、G，

（2）葉結點：度為0的節點稱為葉結點；如上圖：B、C、H、I…等為葉結點，

（3）雙親結點或父結點：若一個節點含有子結點，則這個結點稱為其子結點的父結點；如上圖：A是B的父結點，

（4）孩子結點或子結點：一個結點含有的子樹的根結點稱為該結點的子結點；如上圖：B是A的孩子節點，

（5）兄弟結點：具有相同父結點的結點互稱為兄弟結點； 如上圖：B、C是兄弟結點，

（6）樹的度：一棵樹中，最大的節點的度稱為樹的度； 如上圖：樹的度為6，

（7）結點的層次：從根開始定義起，根為第1層，根的子結點為第2層，以此類推，

（8）樹的高度或深度：樹中結點的最大層次； 如上圖：樹的高度為4，

（9）節點的祖先：從根到某一結點所經分支上的所有結點；如上圖：D、A是H的祖先；A是所有結點的公共祖先，

（10）子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫，如上圖：所有節點都是A的子孫，

（11）森林：多棵互不相交的樹的集合稱為森林，

二叉樹

二叉樹的概念及結構

概念

一棵二叉樹是結點的一個有限集合，該集合為空，或者是由一個根節點加上兩棵稱為左子樹和右子樹的二叉樹組成，

二叉樹的特點：

（1）每個結點最多有兩棵子樹，即二叉樹不存在度大于2的結點，
（2）二叉樹的子樹有左右之分，其子樹的次序不能顛倒，

結構

特殊的二叉樹

 

（1）滿二叉樹

每一層的結點數都達到最大值，則這個二叉樹就是滿二叉樹，
也就是說，如果一個二叉樹的層數為K（根節點是第1層），且結點總數是(2^k) -1 ，則它就是滿二叉樹，

 

 

（2）完全二叉樹

完全二叉樹是由滿二叉樹而引出來的，對于深度為K的、有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹， 滿二叉樹是一種特殊的完全二叉樹，
也就是說：完全二叉樹的葉子結點只能出現在最下層和次下層，且最下層的葉子結點從左到右連續；前K-1層是滿的二叉樹，

 

 

非完全二叉樹

Java實作二叉樹以及遍歷代碼

  1 package com.mm.BinaryTree;
  2 
  3 public class BinaryTree {
  4     Node root;   // 首先定義一個根節點
  5     // 定義一個往二叉樹添加節點的方法
  6     // 利用遞回實作
  7     public Node addNode(Node temp,int value){
  8         Node newNode = new Node(value);
  9         if(temp == null){       // 如果二叉樹是空的 就將傳進來的引數作為根節點創建一個根節點
 10             temp = newNode;
 11             return temp;
 12         }
 13         else if (value < temp.data){    // 如果傳進來的引數小于根節點的值 就用這個值去和左子節點去比較 添加到左子節點
 14             temp.left = addNode(temp.left,value);
 15         }
 16         else {
 17             temp.right = addNode(temp.right,value);     // 如果傳進來的引數大于根節點的值，就用這個值去和右子節點去比較，添加到右子節點
 18         }   // 遞回呼叫添加方法 直到子節點的值為空把數添加進去位置
 19         return temp;
 20     }
 21 
 22     // 定義前序遍歷的方法    先根再左再右
 23     public void qianXuPrint(Node root){
 24         // 依然使用遞回實作
 25         if(root != null){
 26             System.out.print(root.data+" ");  // 先把根節點列印出來
 27             qianXuPrint(root.left);     // 遍歷左子節點 列印最左子節點的值然后逐層上移列印左子節點 也就是最左子節點的二叉樹的根
 28             qianXuPrint(root.right);    // 遍歷右子節點
 29         }
 30     }
 31 
 32     // 定義中序遍歷的方法    先左再根再右
 33     public void zhongXuPrint(Node root){
 34         if(root != null){
 35             zhongXuPrint(root.left);    // 遍歷左子節點 列印最左子節點的值然后逐層上移列印左子節點 也就是最左子節點的二叉樹的根
 36             System.out.print(root.data+" ");  // 列印最左子節點
 37             zhongXuPrint(root.right);   // 遍歷右子節點
 38         }
 39     }
 40 
 41     // 定義后序遍歷的方法    先左再右再根
 42     public void houXuPrint(Node root){
 43         if(root != null){
 44             houXuPrint(root.left);  // 遍歷左子節點 列印最左子節點的值然后逐層上移列印左子節點 也就是最左子節點的二叉樹的根
 45             houXuPrint(root.right); // 遍歷右子節點 列印最右子節點的值然后逐層上移列印右子節點 也就是最右子節點的二叉樹的根
 46             System.out.print(root.data+" ");  // 列印根節點
 47         }
 48     }
 49 }
 50 
 51 class Node{
 52     // 定義一個節點類
 53     int data;       // 根節點
 54     Node left;      // 定義左節點
 55     Node right;     // 定義右節點
 56 
 57     public Node(int data) {
 58         this.data =https://www.cnblogs.com/MMarshall/p/ data;
 59         this.left = null;
 60         this.right = null;
 61     }
 62 
 63     public int getData() {
 64         return data;
 65     }
 66 
 67     public void setData(int data) {
 68         this.data =https://www.cnblogs.com/MMarshall/p/ data;
 69     }
 70 
 71     public Node getLeft() {
 72         return left;
 73     }
 74 
 75     public void setLeft(Node left) {
 76         this.left = left;
 77     }
 78 
 79     public Node getRight() {
 80         return right;
 81     }
 82 
 83     public void setRight(Node right) {
 84         this.right = right;
 85     }
 86 
 87     @Override
 88     public String toString() {
 89         return "Node{" +
 90                 "data="https://www.cnblogs.com/MMarshall/p/+ data +
 91                 ", left=" + left +
 92                 ", right=" + right +
 93                 '}';
 94     }
 95 }
 96 // 測驗用例
 97 package com.mm.BinaryTree;
 98 
 99 public class BinaryTreeTest {
100     public static void main(String[] args) {
101         // 將一個陣列中的數構成一個二叉樹
102         int [] arr = {5,8,2,3,1};
103         BinaryTree bt = new BinaryTree();
104         Node root = null;   // 定義一個根節點
105 
106         for(int i=0;i<arr.length;i++){
107             root = bt.addNode(root,arr[i]);
108         }
109 
110         // 呼叫前序遍歷
111         System.out.print("前序遍歷: ");
112         bt.qianXuPrint(root);
113         System.out.println();
114         System.out.print("中序遍歷: ");
115         bt.zhongXuPrint(root);
116         System.out.println();
117         System.out.print("后序遍歷: ");
118         bt.houXuPrint(root);
119 
120     }
121 }

本文部分概念內容參考自：https://blog.csdn.net/weixin_51983604/article/details/116451530

標籤：其他

上一篇：HDFS原理

下一篇：ClickHouse副本機制簡介