一篇文章徹底弄懂Java中二叉樹

更新時間：2022年01月11日 10:56:11 作者：來學習的小張

二叉樹是有限個節(jié)點的集合,這個集合可以是空集,也可以是一個根節(jié)點和兩顆不相交的子二叉樹組成的集合,其中一顆樹叫根的左子樹,另一顆樹叫右子樹,這篇文章主要給大家介紹了一篇文章如何徹底弄懂Java中二叉樹的相關資料,需要的朋友可以參考下

一、樹形結構

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

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

1.1 相關概念

節(jié)點的度：一個節(jié)點含有的子樹的個數稱為該節(jié)點的度；如上圖：A的度為6；
樹的度：一棵樹中，最大的節(jié)點的度稱為樹的度；如上圖：樹的度為6；
葉子節(jié)點或終端節(jié)點：度為0的節(jié)點稱為葉節(jié)點；如上圖：B、C、H、I…等節(jié)點為葉節(jié)點；
雙親節(jié)點或父節(jié)點：若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點；如上圖：A是B的父節(jié)點；
孩子節(jié)點或子節(jié)點：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點；如上圖：B是A的孩子節(jié)點；
根結點：一棵樹中，沒有雙親結點的結點；如上圖：A
節(jié)點的層次：從根開始定義起，根為第1層，根的子節(jié)點為第2層，以此類推；
樹的高度或深度：樹中節(jié)點的最大層次；如上圖：樹的高度為4

以下概念僅做了解即可：

非終端節(jié)點或分支節(jié)點：度不為0的節(jié)點；如上圖：D、E、F、G...等節(jié)點為分支節(jié)點；
兄弟節(jié)點：具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點；如上圖：B、C是兄弟節(jié)點；
堂兄弟節(jié)點：雙親在同一層的節(jié)點互為堂兄弟；如上圖：H、I互為兄弟節(jié)點；
節(jié)點的祖先：從根到該節(jié)點所經分支上的所有節(jié)點；如上圖：A是所有節(jié)點的祖先；
子孫：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫。如上圖：所有節(jié)點都是A的子孫；
森林：由m（m>=0）棵互不相交的樹的集合稱為森林。

1.2樹的表示形式

樹結構相對線性表就比較復雜了，要存儲表示起來就比較麻煩了，實際中樹有很多種表示方式，如：雙親表示法，孩子表示法、孩子兄弟表示法等等。這里簡單的了解其中最常用的孩子兄弟表示法。

孩子兄弟表示法代碼示例：

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

圖示：

1.3樹的應用：文件系統(tǒng)管理（目錄和文件）

二、二叉樹

2.1相關概念

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

二叉樹的特點：

每個結點最多有兩棵子樹，即二叉樹不存在度大于 2 的結點。

二叉樹的子樹有左右之分，其子樹的次序不能顛倒，因此二叉樹是有序樹。

2.2 二叉樹的基本形態(tài)

上圖給出了幾種特殊的二叉樹形態(tài)。

從左往右依次是：空樹、只有根節(jié)點的二叉樹、節(jié)點只有左子樹、節(jié)點只有右

子樹、節(jié)點的左右子樹均存在，一般二叉樹都是由上述基本形態(tài)結合而形成的。

2.3 兩種特殊的二叉樹

滿二叉樹: 一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數為K，且結點總數是2k-1 ，則它就是滿二叉樹。

完全二叉樹: 完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹。（另一種解釋：如果二叉樹中除去最后一層節(jié)點為滿二叉樹，且最后一層的結點依次從左到右分布，則此二叉樹被稱為完全二叉樹。）要注意的是滿二叉樹是一種特殊的完全二叉樹。

完全二叉樹

非完全二叉樹：

非完全二叉樹

2.4 二叉樹的性質

若規(guī)定根節(jié)點的層數為1，則一棵非空二叉樹的第i層上最多有2i-1 (i>0)個結點；
若規(guī)定只有根節(jié)點的二叉樹的深度為1，則深度為K的二叉樹的最大結點數是2k-1 (k>=0)；
對任何一棵二叉樹, 如果其葉結點個數為 n0, 度為2的非葉結點個數為 n2,則有n0＝n2＋1；
具有n個結點的完全二叉樹的深度k為log2(n+1) 上取整；
對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的順序對所有節(jié)點從0開始編號，則對于序號為i的結點有：

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

如：假設一棵完全二叉樹中總共有1000個節(jié)點，則該二叉樹中__500___個葉子節(jié)點，__500___個非葉子節(jié)點，__1___個節(jié)點只有左孩子，__0___個只有右孩子。

題解：將該二叉樹節(jié)點縮小100倍，變?yōu)樵撏耆鏄渲锌偣灿?0個節(jié)點，由性質2可得深度K為：4，前三層共有7個節(jié)點，則最后一層有10-7=3個節(jié)點，由性質1的第三層有4個節(jié)點，其中有2個節(jié)點上面有子節(jié)點，剩余2個為葉子結點，則該二叉樹共有3+2=5個葉子結點，擴大100倍為500個葉子結點，則剩余的就位非葉子結點。有相關分析可知該二叉樹有1個節(jié)點只有左孩子，0個節(jié)點只有右孩子。

2.5 二叉樹的存儲

二叉樹的存儲結構分為：順序存儲和類似于鏈表的鏈式存儲。

二叉樹的鏈式存儲是通過一個一個的節(jié)點引用起來的，常見的表示方式有二叉和三叉表示方式，具體如下：

// 孩子表示法
class Node {
int val; // 數據域
Node left; // 左孩子的引用，常常代表左孩子為根的整棵左子樹
Node right; // 右孩子的引用，常常代表右孩子為根的整棵右子樹
}

// 孩子雙親表示法
class Node {
int val; // 數據域
Node left; // 左孩子的引用，常常代表左孩子為根的整棵左子樹
Node right; // 右孩子的引用，常常代表右孩子為根的整棵右子樹
Node parent; // 當前節(jié)點的根節(jié)點
}

2.6 二叉樹的基本操作

2.6.1二叉樹的遍歷

遍歷(Traversal)是指沿著某條搜索路線，依次對樹中每個結點均做一次且僅做一次訪問。訪問結點所做的操作依賴于具體的應用問題(比如：打印節(jié)點內容、節(jié)點內容加1)。遍歷是二叉樹上最重要的操作之一，是二叉樹上進行其它運算之基礎。

在遍歷二叉樹時，如果沒有進行某種約定，每個人都按照自己的方式遍歷，得出的結果就比較混亂，如果按照某種規(guī)則進行約定，則每個人對于同一棵樹的遍歷結果肯定是相同的。如果N代表根節(jié)點，L代表根節(jié)點的左子樹，R代表根節(jié)點的右子樹，則根據遍歷根節(jié)點的先后次序有以下遍歷方式：

NLR：前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問根結點—>根的左子樹—>根的右子樹。
LNR：中序遍歷(Inorder Traversal)——根的左子樹—>根節(jié)點—>根的右子樹。
LRN：后序遍歷(Postorder Traversal)——根的左子樹—>根的右子樹—>根節(jié)點。

由于被訪問的結點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。

如上面這張圖,

其前序遍歷：ABDEHCFG;

中序遍歷：DBEHAFCG；

后序遍歷：DHEBFGCA。

2.6.2 二叉樹的基本操作

構建一顆二叉樹：

代碼示例：

class TreeNode{
    public char val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(char val){
        this.val = val;
    }
 }
public class BinaryTree {
	//創(chuàng)建一個二叉樹
    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);//前序遍歷
        }

輸出結果：

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);//中序遍歷
        }

輸出結果：

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);//后序遍歷
        }

輸出結果：

4. 遍歷思路-求結點個數

 static int size = 0;//靜態(tài)變量
    void getSize1(TreeNode root){
        if(root == null){
            return;
        }
        size++;
        getSize1(root.left);
        getSize1(root.right);
    }

5. 子問題思路-求結點個數

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));
   }

輸出結果：

6. 遍歷思路-求葉子結點個數

//遍歷這顆二叉樹，只要節(jié)點的左子樹和右子樹都是空的，那么就是葉子
    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. 子問題思路-求葉子結點個數

//整棵樹的葉子結點 = 左子樹葉子 + 右子樹葉子
    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);//遍歷思路-求葉子結點個數
        System.out.println("+++++++++++++");
        //binaryTree.getLeafSize2(root);
        //System.out.println(BinaryTree.leafSize);//子問題思路-求葉子結點個數
        System.out.println(binaryTree.getLeafSize2(root));
  }

輸出結果：

8. 子問題思路-求第 k 層結點個數

// 子問題思路-求第 k 層結點個數
    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));
 }

輸出結果：

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);
 }

輸出結果：

10. 查找val所在的節(jié)點

查找 val 所在結點，沒有找到返回 null；

按照根 -> 左子樹 -> 右子樹的順序進行查找；

一旦找到，立即返回，不需要繼續(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);
 }

輸出結果：

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);//層序遍歷
 }

輸出結果：

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();//彈出一個元素
            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)); 
 }

輸出結果：

13.非遞歸實現前序遍歷

 //非遞歸實現
    // 前序遍歷
    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.非遞歸實現中序遍歷

 // 中序遍歷
    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.非遞歸實現后序遍歷

// 后序遍歷非遞歸
    void postOrderTraversalNor(TreeNode root){
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;//用來指定上一個被打印過的元素
        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();
}

輸出結果：前、后、中

以上。

總結

到此這篇關于Java中二叉樹的文章就介紹到這了,更多相關Java中二叉樹內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

Java實現雙鏈表互相交換任意兩個節(jié)點的方法示例
這篇文章主要介紹了Java實現雙鏈表互相交換任意兩個節(jié)點的方法,簡單講述了雙鏈表的概念,并結合實例形式給出了java雙鏈表實現任意兩個節(jié)點交換的操作技巧,需要的朋友可以參考下
2017-11-11
Spring中的Aware接口詳細解析
這篇文章主要介紹了Spring中的Aware接口詳細解析,Aware是一個具有標識作用的超級接口,具體實現是有子接口去決定的,但是子接口至少要有一個帶一個參數的且返回是空的方法,需要的朋友可以參考下
2023-12-12
SpringBoot中Bean拷貝及工具類封裝的實現
本文主要介紹了SpringBoot中Bean拷貝及工具類封裝的實現，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2023-05-05
Java數組操作的10大方法
下面是精心整理的Java數組操作的10大方法，大部分代碼都來自Stack Overflow,需要的朋友可以參考下
2014-09-09
使用SpringAOP獲取用戶操作日志入庫
這篇文章主要介紹了使用SpringAOP獲取用戶操作日志入庫，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2021-11-11
SpringBoot實現圖片識別文字的四種方式小結
本文主要介紹了SpringBoot實現圖片識別文字的四種方式，包括Tess4J，百度智能云，阿里云，騰訊云這四種，具有一定的參考價值，感興趣的可以了解一下
2024-02-02
一篇文章帶你復習java知識點
以下簡單介紹了下我對于這些java基本知識點和技術點的一些看法和心得，這些內容都源自于我這些年來使用java的一些總結,希望能夠給你帶來幫助
2021-06-06
使用SpringBoot簡單了解Druid的監(jiān)控系統(tǒng)的配置方法
這篇文章主要介紹了使用SpringBoot簡單了解Druid的監(jiān)控系統(tǒng)的配置，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
2020-06-06
Java maven詳細介紹
今天給大家復習一下Java基礎知識,簡單介紹Maven,文中有非常詳細的解釋,對Java初學者很有幫助喲,需要的朋友可以參考下，希望能夠給你帶來幫助
2021-09-09
快速入門HarmonyOS的Java UI框架的教程
這篇文章主要介紹了快速入門HarmonyOS的Java UI框架,本文給大家介紹的非常詳細對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下
2020-09-09

欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

軟件下載

源碼下載

軟件編程

網絡編程

在線工具

數據庫

CMS

常用工具

一篇文章徹底弄懂Java中二叉樹

目錄

一、樹形結構

1.1 相關概念

1.2樹的表示形式

1.3樹的應用：文件系統(tǒng)管理（目錄和文件）

二、二叉樹

2.1相關概念

2.2 二叉樹的基本形態(tài)

2.3 兩種特殊的二叉樹

2.4 二叉樹的性質

2.5 二叉樹的存儲

2.6 二叉樹的基本操作

2.6.1二叉樹的遍歷

2.6.2 二叉樹的基本操作

總結

相關文章

最新評論

大家感興趣的內容

最近更新的內容

常用在線小工具

一篇文章徹底弄懂Java中二叉樹

目錄

一、樹形結構

1.1 相關概念

1.2樹的表示形式

1.3樹的應用：文件系統(tǒng)管理（目錄和文件）

二、二叉樹

2.1相關概念

2.2 二叉樹的基本形態(tài)

2.3 兩種特殊的二叉樹

2.4 二叉樹的性質

2.5 二叉樹的存儲

2.6 二叉樹的基本操作

2.6.1二叉樹的遍歷

2.6.2 二叉樹的基本操作

總結

相關文章

最新評論

大家感興趣的內容

最近更新的內容

常用在線小工具

一、樹形結構

二、二叉樹