JavaScript實作排序二叉樹的基本操作

記得一開始學習資料結構用的是c語言實作，學了這麼久前端就想用JavaScript來實作一下，順便複習下資料結構。

先來了解下什麼是

排序二叉樹，排序二叉樹 是具有以下特點的二叉樹

1. 若左子樹不空，則左子樹上所有結點的值均小于或等于它的 根結 點的值，
2. 若右子樹不空，則右子樹上所有結點的值均大于或等于它的根結點的值，
3.  左、右子樹也分别為二叉排序樹

比如下面這圖，左邊的值永遠小于右邊的值

下面我們用代碼實作一波

首先是樹的結構和根節點

var Node = function(key){//節點結構        this.left = null         this.right = null        this.key = key    }
     var root = null //根節點
           

二叉樹的插入，基本過程是比較要插入的數和目前節點的值大小，按照排序二叉樹的特點，左邊的值永遠小于右邊

var insertNode = function(node,newNode){        if(node.key > newNode.key){//要插入的值小于目前節點，左子樹周遊            if(node.left === null){                node.left = newNode                return             }else{                insertNode(node.left,newNode)            }        }else if(node.key <= newNode.key){//要插入的值小于目前節點，右子樹周遊            if(node.right === null){                node.right = newNode            }else{                insertNode(node.right,newNode)            }        }    }
           

插入成功後我們分别來實作排序二叉樹的前序，中序和後序周遊

前序周遊是先通路根節點，而後是左右節點

中序周遊先通路左節點，而後是根節點和右節點

後序周遊則先通路左右節點，最後是根節點

代碼如下

var inOrderTraverseNode = function(node,callback){//中序周遊        if(node !== null){            inOrderTraverseNode(node.left)            console.log(node.key)            inOrderTraverseNode(node.right)        }    }
   
    var preOrderTraverseNode = function(node,callback){//前序周遊        if(node !== null){            console.log(node.key)            preOrderTraverseNode(node.left)            preOrderTraverseNode(node.right)        }    }
   
    var afterOrderTraversNode = function(node,callback){//後序周遊        if(node !== null){            afterOrderTraversNode(node.left)            afterOrderTraversNode(node.right)            console.log(node.key)        }    }

           

尋找二叉樹的最大值和最小值，這一部分根據排序二叉樹的特點很快就能知道，最大值在最右邊的葉子節點，最小值處于最左邊的葉子節點

var Max = function(node){//最大值        if(node.right !== null){            maxNum = Max(node.right)        }else{            return node.key        }        return maxNum    }
    var Min = function(node){//最小值        if(node.left !== null){            minNum = Min(node.left)        }else{            return node.key        }        return minNum    }
           

尋找排序二叉樹中的指定值，也很簡單，以根節點為界，比左邊小到左邊找，比右邊小去右邊

var Search = function(node,key){//尋找指定值                    if(node.key === key){                return true            }else{                if(key < node.key && node.left !=null){                    return Search(node.left,key)                }else if(key > node.key && node.left !=null){                    return Search(node.right,key)                }else{                    return false                }            }        }
           

最麻煩的是删除節點的操作，這裡需要分三種情況，删除節點無子樹，删除節點為單子樹，删除節點有兩個子樹，

無子樹最簡單，直接删

if(node.left === null && node.right === null){                node = null                return node            }           

有單子樹的：比如下圖（畫的有點醜。。。），現在我要删掉3，

代碼實作如下

else if(node.left !== null && node.right === null){                node = node.left                return node            }else if(node.left === null && node.right !== null){                node = node.right                return node            }
           

最後是删除有兩個子樹的節點，為了維持我們排序二叉樹的性質，首先我們找到要删除節點的右字樹的最小值，根據

排序二叉樹

的特點，找到的最小值必定大于要删除節點的左子樹的所有值，因為找到的值為右節點的最小值，是以小于要删除節點的右子樹的所有值，我們将找到的最小值代替要删除的值，最後删掉一開始找到的最小值的節點，基本過程就相當于替換了要删除節點的值。

下圖，我要删掉3

。

按照上面的思想，找到4代替3，然後删掉一開始找到的4所在的節點

依舊滿足排序二叉樹的特點

else if(node.left !== null && node.right !== null){                var minNode = finMinNode(node.right)                node.key = minNode.key                node.right = Remove(node.right,minNode.key)                return node            }
           

到這裡排序二叉樹的基本功能都實作了

完整代碼在

GitHub

（求GitHub小星星）上，我把

雙向連結清單

也用JavaScript實作了下，需要的也可以看看

原文釋出時間為：2018年06月23日

原文作者：笑佛彌勒

本文來源： 

掘金 https://juejin.im/entry/5b3a29f95188256228041f46

如需轉載請聯系原作者