二叉樹的基本知識

来源:https://www.cnblogs.com/fengtingxin/archive/2022/06/13/16369406.html
-Advertisement-
Play Games

title: 二叉樹的基本知識 date: 2022-06-12 15:37:23 tags: 二叉樹 演算法 待補充 二叉樹的四種遍歷方式 不要較真,其實也可以分為兩種:廣度優先(層級)和深度優先(前序、中序、後序) 基本概念不再贅述。**複雜度:**設二叉樹中元素數目為n。這四種遍歷演算法的空間複雜 ...



title: 二叉樹的基本知識
date: 2022-06-12 15:37:23
tags:

  • 二叉樹
  • 演算法
  • 待補充

二叉樹的四種遍歷方式

不要較真,其實也可以分為兩種:廣度優先(層級)和深度優先(前序、中序、後序)

基本概念不再贅述。複雜度:設二叉樹中元素數目為n。這四種遍歷演算法的空間複雜性均為O (n),時間複雜性為O(n)。

二叉樹數據結構

class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
      1
     / \
    2   5
   / \     
  3   4   

前序遍歷

遍歷順序:根節點-> 左節點-> 右節點

代碼實現:

/**
     * 前序遍歷  根 -> 左 -> 右
     */
    public void preOrder(TreeNode tree){
        if (tree == null){
            return;
        }
        System.out.print(tree.val);
        preOrder(tree.left);
        preOrder(tree.right);
    }

非遞歸方式

//java 中使用 Deque, Stack已經棄用。
    //Deque 的使用用法:push、pop。
    public void perOrderIter(TreeNode root){
        if (root == null){
            return;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        StringBuilder result = new StringBuilder();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode treeNode = stack.pop();
            result.append(treeNode.val);
            if (treeNode.right != null){
                stack.push(treeNode.right);
            }
            if (treeNode.left != null){
                stack.push(treeNode.left);
            }
        }
        System.out.println(result.toString());
    }

中序遍歷

遍歷順序:左節點-> 根節點-> 右節點

代碼實現

/**
 * 中序遍歷  左 -> 根 -> 右
 * 結果:32415
 */
public void midOrder(TreeNode tree){
    if (tree == null){
        return;
    }
    midOrder(tree.left);
    System.out.print(tree.val);
    midOrder(tree.right);
}
/**
     * 迭代式中序遍歷  左 -> 根 -> 右
     * 這個比較難,重點關註一下。
     */
    public void minOrderIter(TreeNode root){
        if (root == null){
            return;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        StringBuilder result = new StringBuilder();
        while(root != null || !stack.isEmpty()){

            //此處的目的是放入將根節點放入,然後將根節點的左節點壓在根節點上面。
            while (root != null){
                stack.push(root);
                root = root.left;
            }
            //調出棧
            root = stack.pop();
            result.append(root.val);
            root = root.right;
        }
        System.out.println(result.toString());
    }

後序遍歷

遍歷順序:左節點-> 右節點-> 根節點

/**
     * 後序遍歷  左 -> 右 -> 根
     * 結果:34251
     */
    public void postOrder(TreeNode tree){
        if (tree == null){
            return;
        }
        postOrder(tree.left);
        postOrder(tree.right);
        System.out.print(tree.val);
    }
/**
     * 迭代式後序遍歷
     * 後序遍歷更複雜!!!!
     * 先遍歷左節點 -> 右節點 -> 根節點
     *      1
     *      / \
     *     2   5
     *    / \
     *   3   4
     *      / \
     *     7   8
     */
    public void postOrderIter(TreeNode root){
        if (root == null){
            return;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        StringBuilder result = new StringBuilder();
        TreeNode pre = null; //記錄前置節點
        while(root != null || !stack.isEmpty()){
            //把所有的左子樹節點都放入棧中
            while(root != null){
                stack.push(root);
                root = root.left;
            }

            //找到當前節點
            root = stack.pop();
            //如果當前節點的右節點為空
            //這裡為什麼會有對pre的判斷,是為了避免重覆處理。
            //拿例子:當8已經處理完了之後,應該處理4節點,當時發現4也是有右子樹的,但是8已經處理過了,通過pre達標,那麼8也不用處理。
            if (root.right == null || pre == root.right){
                result.append(root.val);
                //設置前置節點
                pre = root;
                //置為空的目的是處理棧中堆積的父節點。
                root = null;
            } else{
                //右節點非空,說明當前節點這個時候不能夠處理,就把當前節點再放回去。
                stack.push(root);
                //把當前節點的右節點作為root進行處理。
                root = root.right;
            }
        }
        System.out.println(result.toString());
    }

層級遍歷

/**
 * 層級遍歷
 * 遞歸的方式
 * 遞歸需要存儲每個的層級 對應的數據都有什麼,藉助額外的數據結構
 */
public List<StringBuilder> result = new ArrayList<>();

public void levelOrder(TreeNode root, int level) {
    if (root == null) {
        return;
    }
    //當數組大小等於層級時,初始化該層級需要的存儲空間
    if (result.size() == level) {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(root.val);
        result.add(level, stringBuilder);
    } else {
        result.get(level).append(root.val);
    }
    levelOrder(root.left, level + 1);
    levelOrder(root.right, level + 1);
}
/**
 * 迭代式層級遍歷
 * 藉助額外的數據結構:隊列,特性:先進先出
 * queue 的基本用法:add(offer),remove(poll)
 */
public void levelOrderIter(TreeNode root) {
    if (root == null) {
        return;
    }
    StringBuilder result = new StringBuilder();
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while(!queue.isEmpty()){
        TreeNode current = queue.poll();
        result.append(current.val);
        if (current.left != null){
            queue.add(current.left);
        }
        if (current.right != null){
            queue.add(current.right);
        }
    }
    System.out.println(result.toString());
}

額外:

/**
 * 獲取二叉樹的最大深度
 */
public int getMaxDepth(TreeNode root){
    if (root == null){
        return 0;
    }
    return Math.max(getMaxDepth(root.left)+1,getMaxDepth(root.right)+1);
}

文章作者: 馮廷鑫
文章鏈接: http://fengtingxin.github.io/2022/06/12/二叉樹的基本知識/

一個入行不久的Java開發,越學習越感覺知識太多,自身瞭解太少,只能不斷追尋
您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Redis常見使用場景,緩存、數據共用分散式、分散式鎖、全局 ID、計數器、限流、位統計、購物車、時間線 Timeline、消息隊列、抽獎、點贊、簽到、打卡、商品標簽、商品篩選、用戶關註、推薦模型、排行榜. ...
  • **導讀:**本文是OPPO商業數據研發負責人&技術專家邱盛昌老師帶來的“OPPO商業化數據體系建設實踐”的分享。整體內容圍繞著下圖中垂直劃分的六個部分展開,分別為:數據平臺、數據接入、數據開發、數據治理、數據應用和數據分析,這個圖也概括了典型的數據體系的所有內容。 -- 01 數據平臺 數據平臺由 ...
  • 第一步:下載資料庫 通過shell工具,採用xftp功能 第二步:解壓數據包 mkdir mysql (在解壓之前創建文件夾) tar -xvf mysql-8.0.28-1.el8.x86_64.rpm-bundle.tar -C mysql 可以將解壓的文件放入到mysql文件夾中 第三步:安裝 ...
  • 1.下載安裝包 1.1 下載elasticsearch 7.13.3 curl -L -O https://artifacts.elastic.co/downloads/elasticsearch/elasticsearch-7.13.3-linux-x86_64.tar.gz 1.2 解壓文件 t ...
  • 開始我們後臺篇的內容,前面處理了一些事情,去學校完成授位儀式,由校長授位合影,青春不留遺憾,然後還換了一個電腦,征戰了四年的神船終於退役了,各種各樣的小毛病是真的煩人。 現在正式開始後臺篇的內容,做了今天總體的感覺後臺部分大難度沒有,但是要考慮一點就是對於elementUI的熟練程度,要把這個練得比 ...
  • theme: mk-cute highlight: arduino-light 一、開發背景 產品出設計稿要求做一個仿原生app簡訊驗證碼組件,花了兩小時搞出來一個還可以的組件,支持屏幕自適應,可以用於彈出框,或自己封裝的vue組件里,希望可以幫助那些被產品壓榨的同學,哈哈。😄 其核心思想就是利用 ...
  • ​網址:https://parcel.passerma.com/ GitHub:GitHub - passerma/parcel-doc: 🌎 Parcel 中文文檔 本文檔持續翻譯中,有想幫忙(希望有人)翻譯的小伙伴也可參與哦 使用 Parcel 構建 Web 應用程式 安裝 在開始之前,您需要 ...
  • 本章是系列文章的第六章,介紹了迴圈的分析方法。迴圈優化的邏輯相對簡單,但對性能提升的效果卻非常明顯。迴圈優化的分析還產生了一個圖靈獎。 本文中的所有內容來自學習DCC888的學習筆記或者自己理解的整理,如需轉載請註明出處。周榮華@燧原科技 6.1 迴圈的重要性 90/10定律,90%的算力消耗在10 ...
一周排行
    -Advertisement-
    Play Games
  • 1.部署歷史 猿友們好,作為初來實習的我,已經遭受社會的“毒打”,所以請容許我在下麵環節適當吐槽,3Q! 傳統部署 ​ 回顧以往在伺服器部署webapi項目(非獨立發佈),dotnet環境、守護進程兩個逃都逃不掉,正常情況下還得來個nginx代理。不僅僅這仨,可能牽扯到yum或npm。node等都要 ...
  • 隨著技術的進步,跨平臺開發已經成為了標配,在此大背景下,ASP.NET Core也應運而生。本文主要基於ASP.NET Core+Element+Sql Server開發一個校園圖書管理系統為例,簡述基於MVC三層架構開發的常見知識點,前一篇文章,已經簡單介紹瞭如何搭建開發框架,和登錄功能實現,本篇... ...
  • 這道題只要會自定義cmp恰當地進行排序,其他部分沒有什麼大問題。 上代碼: 1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,s,h1,h2,cnt; 4 struct apple{ 5 int height,ns;//height為蘋 ...
  • 這篇文章主要描述RPC的路由策略,包括為什麼需要請求隔離,為什麼不在註冊中心中實現請求隔離以及不同粒度的路由策略。 ...
  • 簡介: 中介者模式,屬於行為型的設計模式。用一個中介對象來封裝一系列的對象交互。中介者是各對象不需要顯式地相互引用,從而使其耦合鬆散,而且可以獨立地改變他們之間的交互。 適用場景: 如果平行對象間的依賴複雜,可以使用中介者解耦。 優點: 符合迪米特法則,減少成員間的依賴。 缺點: 不適用於系統出現對 ...
  • 【前置內容】Spring 學習筆記全系列傳送門: Spring學習筆記 - 第一章 - IoC(控制反轉)、IoC容器、Bean的實例化與生命周期、DI(依賴註入) Spring學習筆記 - 第二章 - 註解開發、配置管理第三方Bean、註解管理第三方Bean、Spring 整合 MyBatis 和 ...
  • 簡介: 享元模式,屬於結構型的設計模式。運用共用技術有效地支持大量細粒度的對象。 適用場景: 具有相同抽象但是細節不同的場景中。 優點: 把公共的部分分離為抽象,細節依賴於抽象,符合依賴倒轉原則。 缺點: 增加複雜性。 代碼: //用戶類 class User { private $name; fu ...
  • 這次設計一個通用的多位元組SPI介面模塊,特點如下: 可以設置為1-128位元組的SPI通信模塊 可以修改CPOL、CPHA來進行不同的通信模式 可以設置輸出的時鐘 狀態轉移圖和思路與多位元組串口發送模塊一樣,這裡就不給出了,具體可看該隨筆。 一、模塊代碼 1、需要的模塊 通用8位SPI介面模塊 `tim ...
  • AOP-03 7.AOP-切入表達式 7.1切入表達式的具體使用 1.切入表達式的作用: 通過表達式的方式定義一個或多個具體的連接點。 2.語法細節: (1)切入表達式的語法格式: execution([許可權修飾符] [返回值類型] [簡單類名/全類名] [方法名]([參數列表]) 若目標類、介面與 ...
  • 測試一、虛繼承與繼承的區別 1.1 單個繼承,不帶虛函數 1>class B size(8): 1> + 1> 0 | + (base class A) 1> 0 | | _ia //4B 1> | + 1> 4 | _ib //4B 有兩個int類型數據成員,占8B,基類邏輯存在前面 1.2、單個 ...