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

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

數據結構--二叉樹(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;
    }
}

感謝

尚矽谷

萬能的網路

以及勤勞的自己

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


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

更多相關文章
  • 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格式用於 ...
一周排行
  • 比如要拆分“呵呵呵90909086676喝喝999”,下麵當type=0返回的是中文字元串“呵呵呵,喝喝”,type=1返回的是數字字元串“90909086676,999”, private string GetStrings(string str,int type=0) { IList<strin ...
  • Swagger一個優秀的Api介面文檔生成工具。Swagger可以可以動態生成Api介面文檔,有效的降低前後端人員關於Api介面的溝通成本,促進項目高效開發。 1、使用NuGet安裝最新的包:Swashbuckle.AspNetCore。 2、編輯項目文件(NetCoreTemplate.Web.c ...
  • 2020 年 7 月 30 日, 由.NET基金會和微軟 將舉辦一個線上和為期一天的活動,包括 微軟 .NET 團隊的演講者以及社區的演講者。本次線上大會 專註.NET框架構建微服務,演講者分享構建和部署雲原生應用程式的最佳實踐、模式、提示和技巧。有關更多信息和隨時瞭解情況:https://focu... ...
  • #abp框架Excel導出——基於vue #1.技術棧 ##1.1 前端採用vue,官方提供 UI套件用的是iview ##1.2 後臺是abp——aspnetboilerplate 即abp v1,https://github.com/aspnetboilerplate/aspnetboilerp ...
  • 前言 本文的文字及圖片來源於網路,僅供學習、交流使用,不具有任何商業用途,版權歸原作者所有,如有問題請及時聯繫我們以作處理。 作者:碧茂大數據 PS:如有需要Python學習資料的小伙伴可以加下方的群去找免費管理員領取 input()輸入 Python提供了 input() 內置函數從標準輸入讀入一 ...
  • 從12年到20年,python以肉眼可見的趨勢超過了java,成為了當今It界人人皆知的編程語言。 python為什麼這麼火? 網路編程語言搜索指數 適合初學者 Python具有語法簡單、語句清晰的特點,這就讓初學者在學習階段可以把精力集中在編程對象和思維方法上。 大佬都在用 Google,YouT ...
  • 在社會上存在一種普遍的對培訓機構的學生一種歧視的現象,具體表現在,比如:當你去公司面試的時候,一旦你說了你是培訓機構出來的,那麼基本上你就涼了,那麼你瞞著不說,然後又通過了面試成功入職,但是以後一旦在公司被髮現有培訓經歷,可能會面臨被降薪,甚至被辭退,培訓機構出來的學生,在用人單位眼裡就是能力低下的 ...
  • from typing import List# 這道題看了大佬寫的代碼,經過自己的理解寫出來了。# 從最外圍的四周找有沒有為O的,如果有的話就進入深搜函數,然後深搜遍歷# 判斷上下左右的位置是否為Oclass Solution: def solve(self, board: List[List[s ...
  • import requests; import re; import os; # 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537.36 (KHTML, li ...
  • import requests; import re; import os; import parsel; 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537. ...