數據結構--二叉樹(Java)

来源:https://www.cnblogs.com/guizimo/archive/2020/07/29/13401192.html
-Advertisement-
Play Games

數據結構--二叉樹(Java) 博客說明 文章所涉及的資料來自互聯網整理和個人總結,意在於個人學習和經驗彙總,如有什麼地方侵權,請聯繫本人刪除,謝謝! 樹的常用術語(結合示意圖理解) 節點 根節點 父節點 子節點 葉子節點 (沒有子節點的節點) 節點的權(節點值) 路徑(從root節點找到該節點的路 ...


數據結構--二叉樹(Java)

博客說明

文章所涉及的資料來自互聯網整理和個人總結,意在於個人學習和經驗彙總,如有什麼地方侵權,請聯繫本人刪除,謝謝!

樹的常用術語(結合示意圖理解)

image-20200729224821077

  • 節點
  • 根節點
  • 父節點
  • 子節點
  • 葉子節點 (沒有子節點的節點)
  • 節點的權(節點值)
  • 路徑(從root節點找到該節點的路線)
  • 子樹
  • 樹的高度(最大層數)
  • 森林 :多顆子樹構成森林

樹存儲方式優勢

能提高數據存儲,讀取的效率, 比如利用 二叉排序樹(Binary Sort Tree),既可以保證數據的檢索速度,同時也可以保證數據的插入,刪除,修改的速度

二叉樹的概念

  • 每個節點最多只能有兩個子節點的一種形式稱為二叉樹

    image-20200729224615068

  • 二叉樹的子節點分為左節點和右節點

  • 如果該二叉樹的所有葉子節點都在最後一層,並且結點總數= 2^n -1 , n 為層數,則我們稱為滿二叉樹。

    image-20200729224725059

  • 如果該二叉樹的所有葉子節點都在最後一層或者倒數第二層,而且最後一層的葉子節點在左邊連續,倒數第二層的葉子節點在右邊連續,我們稱為完全二叉樹

    image-20200729224756637

遍歷

  • 前序遍歷: 先輸出父節點,再遍歷左子樹和右子樹
  • 中序遍歷: 先遍歷左子樹,再輸出父節點,再遍歷右子樹
  • 後序遍歷: 先遍歷左子樹,再遍歷右子樹,最後輸出父節點

代碼

package cn.guizimo.tree;

/**
 * @author guizimo
 * @date 2020/7/29 8:03 下午
 */
public class TreeDemo {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        HeroNode root = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "李逵");
        HeroNode node3 = new HeroNode(3, "盧俊義");
        HeroNode node4 = new HeroNode(4, "吳用");
        HeroNode node5 = new HeroNode(5, "林沖");
        HeroNode node6 = new HeroNode(6, "魯智深");

        //創建二叉樹
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node3.setLeft(node5);
        node3.setRight(node6);
        binaryTree.setRoot(root);

        //前序遍歷
//        HeroNode heroNode = binaryTree.preOrderSearch(5);
//        System.out.println(heroNode);
    }


}


/**
 * 二叉樹
 */
class BinaryTree {
    //根節點
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    //刪除二叉樹的節點
    public void delNode(int no) {
        if (root != null) {
            if (root.getNo() == no) {
                root = null;
            } else {
                root.delNode(no);
            }
        } else {
            System.out.println("二叉樹為空");
        }
    }

    //前序
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉樹為空");
        }
    }

    //中序
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉樹為空");
        }
    }

    //後序
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉樹為空");
        }
    }

    //前序查找
    public HeroNode preOrderSearch(int no) {
        if (root != null) {
            return root.preOrderSearch(no);
        } else {
            return null;
        }
    }

    //中序查找
    public HeroNode infixOrderSearch(int no) {
        if (root != null) {
            return root.infixOrderSearch(no);
        } else {
            return null;
        }
    }

    //後序查找
    public HeroNode postOrderSearch(int no) {
        if (root != null) {
            return this.root.postOrderSearch(no);
        } else {
            return null;
        }
    }
}


/**
 * 節點
 */
class HeroNode {
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

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

    public HeroNode getRight() {
        return right;
    }

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

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    //刪除節點
    public void delNode(int no) {
        //判讀左節點是否為空,找到
        if (this.left != null && this.left.no == no) {
            this.left = null;
            return;
        }
        //判斷右節點,找到
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }
        //判斷左節點,未找到,遞歸
        if (this.left != null) {
            this.left.delNode(no);
        }
        //判斷右節點,未找到,遞歸
        if (this.right != null) {
            this.right.delNode(no);
        }
    }

    //前序
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    //中序
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    //後序
    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }

    //前序遍歷查找
    public HeroNode preOrderSearch(int no) {
        if (this.no == no) {
            return this;
        }
        HeroNode resNode = null;
        //判斷左子樹
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //判斷右子樹
        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }

    //中序遍歷查找
    public HeroNode infixOrderSearch(int no) {
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        if (this.no == no) {
            return this;
        }
        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }
        return resNode;
    }

    //後序遍歷查找
    public HeroNode postOrderSearch(int no) {
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        if (this.right != null) {
            resNode = this.right.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        if (this.no == no) {
            return this;
        }
        return resNode;
    }
}

感謝

尚矽谷

萬能的網路

以及勤勞的自己

關註公眾號: 歸子莫,獲取更多的資料,還有更長的學習計劃


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 1.html 亂碼 1 <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> 2.jsp 亂碼頁面開頭加入 <%@ page language="java" import="java.util.*" content ...
  • 輸入成績(0-100),不同的分數段獎勵不同while(true){var a=prompt('請輸入成績');if (a>=0&&a<=100){ break;}}if (a==100){ alert('獎勵一輛汽車')}else if (a>=80&&a<99){ alert('獎勵一本筆記本' ...
  • 在vue中,使用watch來響應數據的變化。watch的用法大致有三種。 1. 常用用法 <input type="text" v-model="name"/> new Vue({ el: '#app', data: { name: '鹹魚' }, watch: { name(newVal,oldV ...
  • 必須使用英文開頭,並且開頭字母一律小寫 所有的命名最好都小寫 儘量不要用縮寫英,除非可以一目瞭然的 如果遇到相差不大 class或者id,主功能識別字母在前,位置識別字母在後,位置識別字母;第一個可大寫(如: navTop, menuLeft) 遵循駝峰命名法:第一個單詞的首字母小寫,其餘每一個有意 ...
  • 行為型模式 行為型模式關註於應用運行過程中演算法的提供和通信關係的梳理。 相比於創建型模式和結構型模式,行為型模式包含了最多的設計模式種類,包括: 職責鏈模式 模板方法模式 解釋器模式 命令模式 迭代器模式 中介者模式 備忘錄模式 觀察者模式 狀態模式 策略模式 訪問者模式 職責鏈模式 職責鏈模式為了 ...
  • 做項目時我們一直在說框架、架構,那它到底是什麼呢? 什麼是架構 從 dubbo 官網我們可以看到架構設計的發展演變史。 這裡把架構分成四類: 單一應用架構 垂直應用架構 分散式服務架構 流動計算架構 剛開始時 PHP + MySQL 就可以形成網站了。 這種模式支持中小型網站是沒有問題的,但是一旦形 ...
  • 事務處理 Spring Boot事務機制實質上就是Spring的事務處理機制。 1 事務的4大特性 原子性(Atomicity) 一個事務要麼全部提交成功,要麼全部失敗回滾,不能只執行其中的一部分操作。 一致性(Consistency) 一旦事務完成(不管成功還是失敗),系統必須確保涉及的數據處於一 ...
  • 一、printf()函數 常用的轉換說明 轉換說明 輸出 %a 浮點數,十六進位數和p計數法 %A 浮點數,十六進位數和p計數法 %c 單個字元 %d 有符號的十進位數 %e 浮點數,e計數法 %E 浮點數,e計數法 %f 浮點數,十進位計數法 %g 根據值的不同,自動選擇%f或者%e,%e格式用於 ...
一周排行
    -Advertisement-
    Play Games
  • 什麼是工廠模式 工廠模式是最常用的設計模式之一,屬於創建型模式。 有點: 解耦,可以把對象的創建和過程分開 減少代碼量,易於維護 什麼時候用? 當一個抽象類有多個實現的時候,需要多次實例化的時候,就要考慮使用工廠模式。 比如:登錄的抽象類ILoginBusiness,它有2個實現,一個用用戶名密碼登 ...
  • 這次iNeuOS升級主要升級圖形渲染引擎和增加豐富的圖元信息,可以很快的方案應用。總共增加41個通用和行業領域的圖元應用,增加2154個圖元信息,現在iNeuOS視圖建模功能模塊總共包括5894個行業圖元信息。現在完全支持製作高保真的工藝流程和大屏展示效果。 ...
  • 效果圖先附上: 首先 這是我是參考 教程:使用 SignalR 2 和 MVC 5 實時聊天 | Microsoft Docs 先附上教程: 在“添加新項 - SignalRChat”中,選擇 InstalledVisual> C#>WebSignalR>,然後選擇 SignalR Hub 類 (v ...
  • 一、前言 項目中之前涉及到胎兒心率圖曲線的繪製,最近項目中還需要添加心電曲線和血樣曲線的繪製功能。今天就來分享一下心電曲線的繪製方式; 二、正文 1、胎兒心率曲線的繪製是通過DrawingVisual來實現的,這裡的心電曲線我也是採用差不多相同的方式來實現的,只是兩者曲線的數據有所區別。心電圖的數據 ...
  • 安裝 Redis # 首先安裝依賴gcc, 後面需要使用make編譯redis yum install gcc -y # 進入 /usr/local/src 目錄, 把源碼下載到這裡 cd /usr/local/src # 下載 redis 7.0.2 的源碼,github被牆,可以使用國內的地址 ...
  • Redis 的定義? 百度百科: Redis(Remote Dictionary Server ),即遠程字典服務,是一個開源的使用ANSI C語言編寫、支持網路、可基於記憶體亦可持久化的日誌型、Key-Value資料庫,並提供多種語言的API。 中文官網: Redis是一個開源(BSD許可),記憶體存 ...
  • 事情的起因是收到了一位網友的請求,他的java課設需要設計實現迷宮相關的程式——如標題概括。 我這邊不方便透露相關信息,就只把任務要求寫出來。 演示視頻指路👉: 基於JavaFX圖形界面的迷宮程式演示_嗶哩嗶哩_bilibili 完整代碼鏈接🔎: 網盤:https://pan.baidu.com ...
  • Python中的字典 Python中的字典是另一種可變容器模型,且可存儲任意類型對象。鍵值使用冒號分割,你可以看成是一串json。 常用方法 獲取字典中的值 dict[key] 如果key不存在會報錯,建議使用dict.get(key),不存在返回None 修改和新建字典值 dict[key]=va ...
  • 迎面走來了你的面試官,身穿格子衫,挺著啤酒肚,髮際線嚴重後移的中年男子。 手拿泡著枸杞的保溫杯,胳膊夾著MacBook,MacBook上還貼著公司標語:“加班使我快樂”。 面試官: 看你簡歷上用過MySQL,問你幾個簡單的問題吧。什麼是聚簇索引和非聚簇索引? 這個問題難不住我啊。來之前我看一下一燈M ...
  • tunm二進位協議在python上的實現 tunm是一種對標JSON的二進位協議, 支持JSON的所有類型的動態組合 支持的數據類型 基本支持的類型 "u8", "i8", "u16", "i16", "u32", "i32", "u64", "i64", "varint", "float", "s ...