首頁 >web前端 >js教程 >js_前中後序二元樹遍歷的三種演算法_簡單二元樹的實現

js_前中後序二元樹遍歷的三種演算法_簡單二元樹的實現

php是最好的语言
php是最好的语言原創
2018-08-03 15:44:194685瀏覽

關於二元樹的建立和遍歷,本文中做出了詳細的介紹,以及前序二叉樹遍歷、中序二叉樹遍歷、後序二叉樹遍歷的演算法也做出了解釋,並引用了程式碼,是為了讓大家看的更清晰。本文的介紹還是先從二元樹和二元查找樹開始吧,方便理解。 apache php mysql

二元樹and二叉查找樹

js_前中後序二元樹遍歷的三種演算法_簡單二元樹的實現

#關於樹的相關術語:

#節點:樹中的每個元素稱為一個節點,

根節點: 位於整棵樹頂點的節點,它沒有父節點, 如上圖5#​​

#子節點: 其他節點的後代

葉子節點: 沒有子節點的元素稱為葉子節點, 如上圖3 8 24

二元樹:二元樹就是一種資料結構, 它的組織關係就像是自然界中的樹一樣。官方語言的定義是:是一個有限元素的集合,該集合或者為空、或者由一個稱為根的元素及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成。

二元查找樹:

二元查找樹也叫二元搜尋樹(BST),它只允許我們在左節點儲存比父節點更小的值,右節點儲存比父節點更大的數值,上圖展示的就是一顆二元查找樹。

程式碼實作

先建立一個類別來表示二元查找樹,它的內部應該有一個Node類,用來建立節點

    function BinarySearchTree () {
        var Node = function(key) {
            this.key = key,
            this.left = null,
            this.right = null
        }
        var root = null
    }

它還應該有一些方法:

  • insert(key) 插入一個新的按鍵

  • inOrderTraverse() 對樹進行中序遍歷,並列印結果

  • preOrderTraverse() 對樹進行先序遍歷,並列印結果

  • postOrderTraverse() 對樹進行後序遍歷,並列印結果

  • search(key) 尋找樹中的鍵,如果存在回傳true,不存在回傳fasle

  • findMin() 傳回樹中的最小值

  • findMax() 傳回樹中的最大值

  • #remove(key) 刪除樹中的某個鍵

在樹中插入一個鍵

在樹中插入新的鍵,首頁應該會建立一個用來表示新節點的Node類別實例,因此需要new一下Node類別並傳入需要插入的key值,它會自動初始化為左右節點為null的一個新節點

然後,需要做一些判斷,先判斷樹是否為空,若為空,新插入的節點就作為根節點,如不為空,呼叫一個輔助方法insertNode()方法,將根節點和新節點傳入

    this.insert = function(key) {
        var newNode = new Node(key)
        if(root === null) {
            root = newNode
        } else {
            insertNode(root, newNode)
        }
    }

定義一下insertNode() 方法,這個方法會透過遞歸得呼叫自身,來找到新新增節點的適當位置

    var insertNode = function(node, newNode) {
        if (newNode.key <= node.key) {
            if (node.left === null) {
                node.left = newNode
            }else {
                insertNode(node.left, newNode)
            }
        }else {
            if (node.right === null) {
                node.right = newNode
            }else {
                insertNode(node.right, newNode)
            }
        }
    }

完成中序遍歷方法

要實作中序遍歷,我們需要一個inOrderTraverseNode(node)方法,它可以遞歸呼叫自身來遍歷每個節點

    this.inOrderTraverse = function() {
        inOrderTraverseNode(root)
    }

這個方法會印出每個節點的key值,它需要一個遞歸終止條件--檢查傳入的node是否為null,如果不為空,就繼續遞歸呼叫自身檢查node的left、 right節點

實作起來也很簡單:

    var inOrderTraverseNode = function(node) {
        if (node !== null) {
            inOrderTraverseNode(node.left)
            console.log(node.key)
            inOrderTraverseNode(node.right)
        }
    }

先序遍歷、後序遍歷

有了中序遍歷的方法,只要稍作改動,就可以實現先序遍歷與後序遍歷了

上程式碼:

這樣就可以對整棵樹進行中序遍歷了

    // 实现先序遍历
    this.preOrderTraverse = function() {
        preOrderTraverseNode(root)
    }
    var preOrderTraverseNode = function(node) {
        if (node !== null) {
            console.log(node.key)
            preOrderTraverseNode(node.left)
            preOrderTraverseNode(node.right)
        }
    }

    // 实现后序遍历
    this.postOrderTraverse = function() {
        postOrderTraverseNode(root)
    }
    var postOrderTraverseNode = function(node) {
        if (node !== null) {
            postOrderTraverseNode(node.left)
            postOrderTraverseNode(node.right)
            console.log(node.key)
        }
    }

發現了吧,其實就是內部語句更換了前後位置,這也剛好符合三種遍歷規則:先序遍歷(根-左-右)、中序遍歷(左-根-右)、中序遍歷(左-右-根)

先來做個測試吧

現在的完整程式碼如下:

    function BinarySearchTree () {
        var Node = function(key) {
            this.key = key,
            this.left = null,
            this.right = null
        }
        var root = null
        
        //插入节点
        this.insert = function(key) {
            var newNode = new Node(key)
            if(root === null) {
                root = newNode
            } else {
                insertNode(root, newNode)
            }
        }
        var insertNode = function(node, newNode) {
            if (newNode.key <= node.key) {
                if (node.left === null) {
                    node.left = newNode
                }else {
                    insertNode(node.left, newNode)
                }
            }else {
                if (node.right === null) {
                    node.right = newNode
                }else {
                    insertNode(node.right, newNode)
                }
            }
        } 
        
        //实现中序遍历
        this.inOrderTraverse = function() {
            inOrderTraverseNode(root)
        }
        var inOrderTraverseNode = function(node) {
            if (node !== null) {
                inOrderTraverseNode(node.left)
                console.log(node.key)
                inOrderTraverseNode(node.right)
            }
        }
        // 实现先序遍历
        this.preOrderTraverse = function() {
            preOrderTraverseNode(root)
        }
        var preOrderTraverseNode = function(node) {
            if (node !== null) {
                console.log(node.key)
                preOrderTraverseNode(node.left)
                preOrderTraverseNode(node.right)
            }
        }

        // 实现后序遍历
        this.postOrderTraverse = function() {
            postOrderTraverseNode(root)
        }
        var postOrderTraverseNode = function(node) {
            if (node !== null) {
                postOrderTraverseNode(node.left)
                postOrderTraverseNode(node.right)
                console.log(node.key)
            }
        }
    }

竟然已經完成了新增節點和遍歷的方式,我們來測試一下:

#定義一個陣列,裡面有一些元素

var arr = [9,6,3,8,12,15]

我們將arr中的每個元素依此插入到二元搜尋樹中,然後列印結果

    var tree = new BinarySearchTree()
    arr.map(item => {
        tree.insert(item)
    })
    tree.inOrderTraverse()
    tree.preOrderTraverse()
    tree.postOrderTraverse()

運行程式碼後,我們先來看看插入節點後整顆樹的情況:

js_前中後序二元樹遍歷的三種演算法_簡單二元樹的實現

輸出結果

中序遍歷:

3<br>6<br>#8<br>9<br>12<br>15<br><br>

先序遍歷:

9<br>6<br>3<br>8<br>12 <br>15<br><br>

後序遍歷:

3<br>8<br>6<br>15<br>12<br>9<br> <br>

很明顯,結果是符合預期的,所以,我們用上面的JavaScript程式碼,實作了對樹的節點插入,和三種遍歷方法,同時,很明顯可以看到,在二元尋找樹樹種,最左側的節點的值是最小的,而最右側的節點的值是最大的,所以二元查找樹可以很方便的拿到其中的最大值和最小值

找出最小、最大值

怎麼做呢?其實只需要將根節點傳入minNode/或maxNode方法,然後透過循環判斷node為左側(minNode)/右側(maxNode)的節點為null

##實作程式碼:

    // 查找最小值
    this.findMin = function() {
        return minNode(root)
    }
    var minNode = function(node) {
        if (node) {
            while (node && node.left !== null) {
                node = node.left
            }
            return node.key
        }
        return null
    }
    
    // 查找最大值
    this.findMax = function() {
        return maxNode(root)
    }
    var maxNode = function (node) {
        if(node) {
            while (node && node.right !== null) {
                node =node.right
            }
            return node.key
        }
        return null
    }

所搜特定值

this.search = function(key) {
    return searchNode(root, key)
}

同样,实现它需要定义一个辅助方法,这个方法首先会检验node的合法性,如果为null,直接退出,并返回fasle。如果传入的key比当前传入node的key值小,它会继续递归查找node的左侧节点,反之,查找右侧节点。如果找到相等节点,直接退出,并返回true

    var searchNode = function(node, key) {
        if (node === null) {
            return false
        }
        if (key < node.key) {
            return searchNode(node.left, key)
        }else if (key > node.key) {
            return searchNode(node.right, key)
        }else {
            return true
        }
    }

移除节点

移除节点的实现情况比较复杂,它会有三种不同的情况:


    • 需要移除的节点是一个叶子节点

    • 需要移除的节点包含一个子节点

    • 需要移除的节点包含两个子节点

    和实现搜索指定节点一元,要移除某个节点,必须先找到它所在的位置,因此移除方法的实现中部分代码和上面相同:

        // 移除节点
        this.remove = function(key) {
            removeNode(root,key)
        }
        var removeNode = function(node, key) {
            if (node === null) {
                return null
            }
            if (key < node.key) {
                node.left = removeNode(node.left, key)
                return node
            }else if(key > node.key) {
                node.right = removeNode(node.right,key)
                return node
            }else{
                //需要移除的节点是一个叶子节点
                if (node.left === null && node.right === null) {
                    node = null
                    return node
                }
                //需要移除的节点包含一个子节点
                if (node.letf === null) {
                    node = node.right
                    return node
                }else if (node.right === null) {
                    node = node.left
                    return node
                }
                //需要移除的节点包含两个子节点
                var aux = findMinNode(node.right)
                node.key = aux.key
                node.right = removeNode(node.right, axu.key)
                return node
            }
        }
        var findMinNode = function(node) {
            if (node) {
                while (node && node.left !== null) {
                    node = node.left
                }
                return node
            }
            return null
        }

    其中,移除包含两个子节点的节点是最复杂的情况,它包含左侧节点和右侧节点,对它进行移除主要需要三个步骤:

  1. 需要找到它右侧子树中的最小节点来代替它的位置

  2. 将它右侧子树中的最小节点移除

  3. 将更新后的节点的引用指向原节点的父节点

有点绕儿,但必须这样,因为删除元素后的二叉搜索树必须保持它的排序性质

测试删除节点

tree.remove(8)
tree.inOrderTraverse()

打印结果:

3<br>6<br>9<br>12<br>15<br>

8 这个节点被成功删除了,但是对二叉查找树进行中序遍历依然是保持排序性质的

到这里,一个简单的二叉查找树就基本上完成了,我们为它实现了,添加、查找、删除以及先中后三种遍历方法

存在的问题

但是实际上这样的二叉查找树是存在一些问题的,当我们不断的添加更大/更小的元素的时候,会出现如下情况:

tree.insert(16)
tree.insert(17)
tree.insert(18)

来看看现在整颗树的情况:

js_前中後序二元樹遍歷的三種演算法_簡單二元樹的實現

看图片容易得出它是不平衡的,这又会引出平衡树的概念,要解决这个问题,还需要更复杂的实现,例如:AVL树,红黑树 哎,之后再慢慢去学习吧

相关文章:

二叉树遍历算法-php的示例

二叉树的中序遍历,该怎么解决

以上是js_前中後序二元樹遍歷的三種演算法_簡單二元樹的實現的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn