使用JavaScript完成二叉樹的一些基本操作

YPHP 發(fā)布于2019-08-23 12:48 / 1033人閱讀

摘要：另外，由于篇幅有限，本篇的重點在于二叉樹的常見算法以及實現(xiàn)。常見的二叉樹實現(xiàn)代碼之前寫過相關的文章，是關于如何創(chuàng)建及遍歷二叉樹的，這里不再贅述。同時我們注意到，在二叉樹深度比較大的時候，我們光是比較左右是不夠的。

本篇為復習過程中遇到過的總結，同時也給準備面試的同學一份參考。另外，由于篇幅有限，本篇的重點在于二叉樹的常見算法以及實現(xiàn)。

常見的二叉樹實現(xiàn)代碼

之前寫過相關的文章，是關于如何創(chuàng)建及遍歷二叉樹的，這里不再贅述。提供鏈接給各位感興趣的小伙伴，點此跳轉

翻轉二叉樹

對于一棵二叉樹，翻轉它的左右子樹，如下圖所示：

下面來分析具體的實現(xiàn)思路：

對于根結點為空的情況

這種情況需要排除，因為null不是一個對象，不可能存在左右子樹并且可以翻轉的情況

對于一棵只有一個根結點的二叉樹

emmm，這種情況也可以翻轉，因為此時根結點左右子樹為null，交換左右子樹其實也就是在交換兩個null，理論上是翻轉了，但實際上我們看到的和沒有翻轉之前的結果是一樣的

對于一棵具有兩個或兩個以上結點的二叉樹，此時二叉樹可以表示為如下的圖像：

可以看出，無論是只有左子樹還是只有右子樹都可以進行翻轉。這句話等價于，為空的子樹可以和不為空的子樹進行交換，也就是不對為空的子樹進行特殊處理

分析過程

其實這樣我們還是不知道二叉樹是如何翻轉的，我們可以用第一張圖的二叉樹為例子，看一下翻轉的具體過程。

首先我們需要對根結點進行判空處理，在根結點不為空的情況下存在左右子樹（即使左右子樹為空），然后交換左右子樹；

把根結點的左子樹當成左子樹的根結點，對當前根結點進行判空處理，不為空時交換左右子樹;

把根結的右子樹當成右子樹的根結點，對當前根結點進行判空處理，不為空時交換左右子樹;

重復步驟2、3，最后二叉樹變?yōu)樵瓉淼溺R像結構,結果可以參考文章第一張示意圖。

示例代碼

根據(jù)上面的推理過程我們可以得出如下的代碼：

function reverseTree(root){
    if( root !== null){
        [root.left, root.right] = [root.right, root.left]
        reverseTree(root.left)
        reverseTree(root.right)
    }
}

雖然推理過程比較復雜（也可能是寫的比較啰嗦。。），但是仔細觀察代碼，這和遍歷的代碼似乎也沒多大差別，只是把輸出結點變?yōu)榱私粨Q結點。

判斷二叉樹是否完全對稱

一棵左右完全對稱的二叉樹是這樣的：

那到底如何判斷呢？

根結點為空時，此時為一棵空二叉樹，滿足對稱條件（-_-||）

只有一個根結點時，左右子樹都為null，滿足左右對稱條件

只有兩個結點時，此時左右子樹必定有一個為空，不可能存在對稱的情況

結點數(shù)在三個及三個以上時，二叉樹有對稱的可能。

按照我們正常的思維，看對稱與否，首先看左邊，然后看右邊，最后比較左右是否相等。同時我們注意到，在二叉樹深度比較大的時候，我們光是比較左右是不夠的。可以觀察到，我們比較完左右以后還需要比較左的左和右的右，比較左的右和右的左

分析過程

這么看是比較繞，接下來我們來看圖分析：

先比較根結點左右孩子

將左子樹根結點的左孩子與右子樹根結點的右孩子進行比較

將左子樹根結點的右孩子與右子樹根結點的左孩子進行比較

重復以上過程...

示例代碼

function isSymmetrical(pRoot)
{
    // write code here
    if(!pRoot){
        return true
    }
    return funC(pRoot.left, pRoot.right)
}
 
function funC(left, right){
     
    if(!left){
        return right === null
    }
     
    if(!right){
        return false
    }
     
    if(left.val !== right.val){
        return false
    }
     
    return funC(left.right, right.left) && funC(left.left, right.right)
}

求二叉樹的深度 分析過程

只有一個根結點時，二叉樹深度為1

只有左子樹時，二叉樹深度為左子樹深度加1

只有右子樹時，二叉樹深度為右子樹深度加1

同時存在左右子樹時，二叉樹深度為左右子樹中深度最大者加1

示例代碼

function deep(root){
    if(!root){
        return 0
    }
    let left = deep(root.left)
    let right = deep(root.right)
    return left > right ? left + 1 : right + 1
}

求二叉樹的寬度

二叉樹的寬度是啥？我把它理解為具有最多結點數(shù)的層中包含的結點數(shù)，比如下圖所示的二叉樹，其實它的寬度就是為4：

分析過程

根據(jù)上圖，我們如何算出二叉樹的寬度呢？其實有個很簡單的思路：

算出第一層的結點數(shù)，保存

算出第二層的結點數(shù)，保存一二層中較大的結點數(shù)

重復以上過程

示例代碼

根據(jù)分析過程，我們可以利用隊列這種數(shù)據(jù)結構來實現(xiàn)這個算法，代碼如下：

function width(root){
    if(!root){
        return 0
    }
    let queue = [root], max = 1, deep = 1
    while(queue.length){
        while(deep--){
            let temp = queue.shift()
            if(temp.left){
                queue.push(temp.left)
            }
            if(temp.right){
                queue.push(temp.right)
            }
        }
        deep = queue.length
        max = max > deep ? max : deep
    }
    return max
}

重建二叉樹 常見的遍歷

前序遍歷：

前序遍歷首先訪問根結點然后遍歷左子樹，最后遍歷右子樹。

中序遍歷：

中序遍歷首先訪問左子樹然后遍歷根節(jié)點，最后遍歷右子樹。

后序遍歷：

后序遍歷首先遍歷左子樹，然后遍歷右子樹，最后訪問根結點

題目描述

根據(jù)前序遍歷產生的序列和中序遍歷產生的序列生成一顆二叉樹

思路分析

假如有這么一棵二叉樹：

可以看出它前序遍歷序列為：8 6 5 7 10 9 11，中序遍歷序列為：5 6 7 8 9 10 11
其中有個很明顯的特征，根結點的值為前序遍歷序列的第一個值，而且我們在中序遍歷序列中很容易看出，根結點左右兩邊的結點分別為構成左子樹和右子樹的結點，所以我們可以得到一種解決問題的思路：

獲取前序遍歷的第一個值，構建根結點

生成左子樹的前序遍歷序列和中序遍歷序列

生成右子樹的前序遍歷序列和中序遍歷序列

重復以上過程...

示例代碼

function reConstructBinaryTree(pre, vin)
{
    if(!pre || !vin || !pre.length || !vin.length){
        return null
    }
    let root = new TreeNode(pre[0]),
        tIndex = vin.indexOf(pre[0]),
        leftIn = [],leftPre = [],rightIn = [],rightPre = []
    
    for(let i = 0; i < tIndex; i++){
        leftIn.push(vin[i])
        leftPre.push(pre[i+1])
    }
    for(let i = tIndex+1; i < pre.length; i++){
        rightIn.push(vin[i])
        rightPre.push(pre[i])
    }
    //遞歸
    root.left = reConstructBinaryTree(leftPre, leftIn)
    root.right = reConstructBinaryTree(rightPre, rightIn)
    return root
}

以上思路、代碼有錯漏請在評論區(qū)指出！

總結

代碼部分來自牛客網--劍指offer，相應的題目也都可以在上面找到。

掃描下方的二維碼或搜索「tony老師的前端補習班」關注我的微信公眾號，那么就可以第一時間收到我的最新文章。

GPU云服務器云服務器二叉樹的遍歷二叉樹的存儲二叉樹的存儲結構 java二叉樹的構建

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/99012.html

學習javascript數(shù)據(jù)結構(四)——樹

摘要：原文博客地址學習數(shù)據(jù)結構四樹知乎專欄簡書專題前端進擊者知乎前端進擊者簡書博主博客地址的個人博客人之所能，不能兼?zhèn)洌瑮壠渌蹋∑渌L。通常子樹被稱作左子樹和右子樹。敬請期待數(shù)據(jù)結構篇最后一篇文章學習數(shù)據(jù)結構五圖參考文章樹數(shù)據(jù)結構二叉樹前言總括：本文講解了數(shù)據(jù)結構中的[樹]的概念，盡可能通俗易懂的解釋樹這種數(shù)據(jù)結構的概念，使用javascript實現(xiàn)了樹，如有紕漏，歡迎批評指正。 ...

Dean 2019-08-20 13:47 評論0 收藏0
LeetCode 之 JavaScript 解答第94題 —— 二叉樹的中序遍歷

摘要：小鹿題目二叉樹中序遍歷給定一個二叉樹，返回它的中序遍歷。通常遞歸的方法解決二叉樹的遍歷最方便不過，但是我還是喜歡增加點難度，用一般的迭代循環(huán)來實現(xiàn)。 Time：2019/4/25Title:Binary Tree Inorder TraversalDifficulty: MediumAuthor:小鹿題目：Binary Tree Inorder Traversal（二叉樹中序遍歷...

Jason 2019-08-23 17:19 評論0 收藏0
使用javascript實現(xiàn)排序二叉樹（2）

摘要：使用實現(xiàn)排序二叉樹上一篇文章我們構造了基本的一個排序二叉樹的數(shù)據(jù)結構，但是僅僅是定義了一個方法去創(chuàng)建二叉排序樹，今天我們來給我們的數(shù)據(jù)結構添加一些遍歷的功能。使用javascript實現(xiàn)排序二叉樹（2）上一篇文章我們構造了基本的一個排序二叉樹的數(shù)據(jù)結構，但是僅僅是定義了一個insert方法去創(chuàng)建二叉排序樹，今天我們來給我們的數(shù)據(jù)結構添加一些遍歷的功能。二叉樹的三種遍歷方式（以根節(jié)...

susheng 2019-08-23 11:33 評論0 收藏0
使用javascript實現(xiàn)排序二叉樹（1）

摘要：使用實現(xiàn)排序二叉樹排序二叉樹的定義二叉樹的基礎上，左節(jié)點比父節(jié)點要小，右節(jié)點比父節(jié)點要大的二叉樹，叫排序二叉樹。下期內容實現(xiàn)排序二叉樹的中序前序后續(xù)遍歷實現(xiàn)二叉樹的節(jié)點查找功能實現(xiàn)排序二叉樹的刪除節(jié)點功能應用排序二叉樹實現(xiàn)一個小游戲使用javascript實現(xiàn)排序二叉樹（1）排序二叉樹的定義：二叉樹的基礎上，左節(jié)點比父節(jié)點要小，右節(jié)點比父節(jié)點要大的二叉樹，叫排序二叉樹。 show...

Caicloud 2019-08-23 11:29 評論0 收藏0
JS遞歸與二叉樹的遍歷

摘要：貌似大部分語言中的遞歸都差不多，之所以在標題加是因為搜了下后感覺網上用來描述這概念的不多，簡單地說遞歸就是函數(shù)調用自己的過程。貌似大部分語言中的遞歸都差不多，之所以在標題加JS是因為搜了下后感覺網上用js來描述這概念的不多，簡單地說遞歸就是函數(shù)調用自己的過程。下面的栗子可以很直觀地展示遞歸的執(zhí)行過程： function rec(x){ if(x!==1){ console....

church 2019-08-21 10:48 評論0 收藏0