天天看點
傳回

資料結構與算法二叉樹的算法_資料結構c語言二叉樹的深度

大家好，又見面了，我是你們的朋友全棧君。

一、什麼是二叉樹

1.概述

首先，需要了解樹這種資料結構的定義：

樹：是一類重要的非線性資料結構，是以分支關系定義的層次結構。每個結點有零個或多個子結點；沒有父結點的結點稱為根結點；每一個非根結點有且隻有一個父結點；除了根結點外，每個子結點可以分為多個不相交的子樹
資料結構與算法二叉樹的算法_資料結構c語言二叉樹的深度

樹的結構類似現實中的樹，一個父節點有若幹子節點，而一個子節點又有若幹子節點，以此類推。

2.名詞解釋

名稱 含義
根節點 樹的頂端結點
父節點 若一個節點含有子節點，則這個節點稱為其子節點的父節點
子節點 具有相同父節點的節點
兄弟節點 彼此都擁有同一個父節點的節點
葉子節點 即沒有子節點的節點
節點的權 即節點值
路節點的度 一個節點含有的子樹的個數
樹的度 一棵樹中，最大的節點的度稱為樹的度
深度 根結點到這個結點所經曆的邊的個數
層數 該節點的深度+1
高度 結點到葉子結點的最長路徑所經曆的邊的個數
樹高度 即根節點的高度
森林 由m（m>=0）棵互不相交的樹的集合稱為森林

3.二叉樹

二叉樹就是每個節點最多隻有兩顆子樹的樹：

資料結構與算法二叉樹的算法_資料結構c語言二叉樹的深度

對于二叉樹有：

  • 滿二叉樹：所有的子節點都在最後一層，且節點總數與層數有

    節點總數=2^n-1
資料結構與算法二叉樹的算法_資料結構c語言二叉樹的深度
  • 完全二叉樹：從根節點到倒數第二層都符合滿二叉樹，但是最後一層節點不完全充填，葉子結點都靠左對齊
資料結構與算法二叉樹的算法_資料結構c語言二叉樹的深度

二、二叉樹的周遊

二叉樹周遊分為三種：

  • 前序周遊: 先輸出父節點，再周遊左子樹和右子樹
  • 中序周遊: 先周遊左子樹，再輸出父節點，再周遊右子樹
  • 後序周遊: 先周遊左子樹，再周遊右子樹，最後輸出父節點

可見，根據父節點輸出順序即可以判斷是哪一種周遊。

1.簡單代碼實作

先建立節點類：

/**
 * @Author：黃成興
 * @Date：2020-07-11 17:30
 * @Description：二叉樹
 */
public class BinaryTreeNode {

    private int nodeNum;

    /**
     * 右子節點
     */
    private BinaryTreeNode right;

    /**
     * 左子節點
     */
    private BinaryTreeNode left;

    public BinaryTreeNode(int nodeNum) {
        this.nodeNum = nodeNum;
    }

    @Override
    public String toString() {
        return "BinaryTreeNode{" +
                "nodeNum=" + nodeNum +
                '}';
    }

    public int getNodeNum() {
        return nodeNum;
    }

    public void setNodeNum(int nodeNum) {
        this.nodeNum = nodeNum;
    }

    public BinaryTreeNode getRight() {
        return right;
    }

    public void setRight(BinaryTreeNode right) {
        this.right = right;
    }

    public BinaryTreeNode getLeft() {
        return left;
    }

    public void setLeft(BinaryTreeNode left) {
        this.left = left;
    }
}

複制

實作周遊方法：

/**
 * @Author：黃成興
 * @Date：2020-07-11 17:44
 * @Description：二叉樹
 */
public class BinaryTree {

    private BinaryTreeNode root;

    public BinaryTree(BinaryTreeNode root) {
        if (root == null) {
            throw new RuntimeException("根節點不允許為空！");
        }
        this.root = root;
    }

    public void preOrder(){
        preOrder(root);
    }
    /**
     * 前序周遊
     */
    public void preOrder(BinaryTreeNode node){
        //列印節點
        System.out.println(node);
        //向左子樹前序周遊
        if (node.getLeft() != null) {
            preOrder(node.getLeft());
        }
        //向右子樹前序周遊
        if (node.getRight() != null) {
            preOrder(node.getRight());
        }
    }

    public void inOrder(){
        inOrder(root);
    }
    /**
     * 中序周遊
     */
    public void inOrder(BinaryTreeNode node){
        //向左子樹中序周遊
        if (node.getLeft() != null) {
            inOrder(node.getLeft());
        }
        //列印節點
        System.out.println(node);
        //向右子樹中序周遊
        if (node.getRight() != null) {
            inOrder(node.getRight());
        }
    }

    public void postOrder(){
        postOrder(root);
    }
    /**
     * 後序周遊
     */
    public void postOrder(BinaryTreeNode node){
        //向左子樹中序周遊
        if (node.getLeft() != null) {
            postOrder(node.getLeft());
        }
        //向右子樹中序周遊
        if (node.getRight() != null) {
            postOrder(node.getRight());
        }
        //列印節點
        System.out.println(node);
    }
}

複制

2.測試

對含有7個簡單的滿二叉樹進行周遊的結果：

資料結構與算法二叉樹的算法_資料結構c語言二叉樹的深度
前序周遊：
BinaryTreeNode{nodeNum=1}
BinaryTreeNode{nodeNum=2}
BinaryTreeNode{nodeNum=4}
BinaryTreeNode{nodeNum=5}
BinaryTreeNode{nodeNum=3}
BinaryTreeNode{nodeNum=6}
BinaryTreeNode{nodeNum=7}
中序周遊：
BinaryTreeNode{nodeNum=4}
BinaryTreeNode{nodeNum=2}
BinaryTreeNode{nodeNum=5}
BinaryTreeNode{nodeNum=1}
BinaryTreeNode{nodeNum=6}
BinaryTreeNode{nodeNum=3}
BinaryTreeNode{nodeNum=7}
後序周遊：
BinaryTreeNode{nodeNum=4}
BinaryTreeNode{nodeNum=5}
BinaryTreeNode{nodeNum=2}
BinaryTreeNode{nodeNum=6}
BinaryTreeNode{nodeNum=7}
BinaryTreeNode{nodeNum=3}
BinaryTreeNode{nodeNum=1}

複制

三、二叉樹的查找

大體邏輯同周遊，這裡就不在贅述了，直接放代碼：

/**
 * 前序查找
 * @param num
 * @param node
 * @return
 */
public BinaryTreeNode preSearch(int num,BinaryTreeNode node){
    BinaryTreeNode result = null;

    //判斷目前節點是否為查找節點
    if (node.getNodeNum() == num) {
        result = node;
    }
    //判斷左節點是否為空，不為空就前序查找節點
    if (node.getLeft() != null) {
        result = preSearch(num, node.getLeft());
    }
    //如果左樹找到就傳回
    if (result != null){
        return result;
    }
    //否則就判斷并遞歸前序查找右樹
    if (node.getRight() != null) {
        result = preSearch(num, node.getRight());
    }
    return result;
}

/**
 * 中序查找
 * @param num
 * @param node
 * @return
 */
public BinaryTreeNode inSearch(int num,BinaryTreeNode node){
    BinaryTreeNode result = null;

    //判斷左節點是否為空，不為空就中序查找節點
    if (node.getLeft() != null) {
        result = inSearch(num, node.getLeft());
    }
    //如果左樹找到就傳回
    if (result != null){
        return result;
    }
    //如果左樹未找到就判斷目前節點是不是
    if (node.getNodeNum() == num) {
        result = node;
    }
    //否則就判斷并遞歸前序查找右樹
    if (node.getRight() != null) {
        result = inSearch(num, node.getRight());
    }
    return result;
}

/**
 * 後序查找
 * @param num
 * @param node
 * @return
 */
public BinaryTreeNode postSearch(int num,BinaryTreeNode node){
    BinaryTreeNode result = null;

    //判斷左節點是否為空，不為空就後序查找節點
    if (node.getLeft() != null) {
        result = postSearch(num, node.getLeft());
    }
    //如果左樹找到就傳回
    if (result != null){
        return result;
    }

    //否則就判斷并遞歸後序查找右樹
    if (node.getRight() != null) {
        result = postSearch(num, node.getRight());
    }
    //判斷右樹是否找到
    if (result != null){
        return result;
    }

    //如果右樹仍未找到就判斷目前節點是不是
    if (node.getNodeNum() == num) {
        result = node;
    }
    return result;
}

複制

四、二叉樹的删除

對于二叉樹的删除，有以下邏輯：

  • 由于樹的節點和節點之間的聯系是單向的，對于要删除的節點，需要找到他的父節點進行删除
  • 從根節點開始周遊節點，判斷節點的左右子節點是否為目标節點
  • 如果是就删除并傳回
  • 否則就持續向右或左遞歸，直到找到目标節點，或者将樹周遊完為止 
/**
 * 删除節點
 * @param num
 * @param node
 * @return
 */
public void delete(int num, BinaryTreeNode node) {
    //判斷删除的是否為根節點
    if (root.getNodeNum() == num) {
        throw new RuntimeException("不允許删除根節點！");
    }
    //如果子節點就是要删除的節點
    if (node.getLeft() != null && node.getLeft().getNodeNum() == num) {
        node.setLeft(null);
        return;
    }
    if (node.getRight() != null && node.getRight().getNodeNum() == num) {
        node.setRight(null);
        return;
    }
    //否則就往左樹或右樹周遊直到找到或周遊完為止
    if (node.getLeft() != null) {
        delete(num, node.getLeft());
    }
    if (node.getRight() != null) {
        delete(num,node.getRight());
    }
}

複制

五、順序存儲二叉樹

一般想到二叉樹都會先想到較為形象的鍊式存儲，即用含有左右指針的節點來組成樹，實際上，通過計算，也可以使用數組來表示二叉樹。

可以簡單的了解：順序存儲二叉樹是邏輯的上一棵樹，而鍊式存儲二叉樹是實體上的一棵樹。

以下圖的樹為例：

資料結構與算法二叉樹的算法_資料結構c語言二叉樹的深度

假設數組為{1,2,3,4,5,6,7,}，我們可以知道：

  • 下标為n的元素的左節點為：

    2*n+1
  • 下标為n的元素的右節點為：

    2*n+2
  • 下标為n的元素的父節點為：

    (n-1)/2

如果給順序存儲二叉樹寫一個前序周遊急就是這樣：

/**
 * 前序周遊
 * @param index
 */
public void preOrder(int index) {
    //輸出數組
    System.out.println(arr[index]);
    //向左遞歸
    if ((index * 2 + 1) < arr.length) {
        preOrder(index * 2 + 1);
    }
    //向右遞歸
    if ((index * 2 + 2) < arr.length) {
        preOrder(index * 2 + 2);
    }
}

複制

在代碼的實作上和鍊式二叉樹是差不多的，這裡就不再一一列舉了。

當然，由于順序存儲二叉樹的性質，當樹需要排序的情況下，順序存儲二叉樹就會出現空間浪費的情況：

資料結構與算法二叉樹的算法_資料結構c語言二叉樹的深度

釋出者：全棧程式員棧長，轉載請注明出處：https://javaforall.cn/170808.html原文連結：https://javaforall.cn

上一篇: 技術硬實力，一個P8進階技術專家應該具備的技術修養
下一篇: Win10系統安裝ISE14.7後出現軟體閃退及驅動不能正常安裝問題