二叉樹遍歷

aboutU 發(fā)布于2019-08-26 13:54 / 3672人閱讀

摘要：前言本篇文章是在二叉排序樹的基礎(chǔ)上進行遍歷查找與刪除結(jié)點。接下來我們根據(jù)構(gòu)造的這顆二叉樹進行相應(yīng)遍歷查找與刪除操作。遍歷二叉樹二叉樹的遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷。中序遍歷二叉排序樹，得到的數(shù)組是有序的且是升序的。

前言

本篇文章是在二叉排序樹的基礎(chǔ)上進行遍歷、查找、與刪除結(jié)點。

那么首先來看一下什么是二叉排序樹？

二叉排序樹

定義

二叉排序樹，又稱二叉查找樹、二叉搜索樹。

若左子樹不為空，左子樹上所有結(jié)點均小于它的根結(jié)點的值；

若右子樹不為空，右子樹上所有結(jié)點均大于它的根結(jié)點的值；

左右子樹也分別為二叉排序樹。

插入算法

我們知道了什么是二叉排序樹，現(xiàn)在來看下它的具體算法實現(xiàn)。

// 構(gòu)建二叉樹
function BinaryTree() {
    // 定義結(jié)點
    let Node = function(key) {
        this.key = key
        this.left = left
        this.right = right
    }
    
    // 定義根結(jié)點
    let root = null
    
    // 獲得整棵樹
    this.getRoot = function() {
        return this.root
    }
    // 定義插入結(jié)點算法
    let insertNode = function(node, newNode) {
        // 比較要插入結(jié)點與當(dāng)前結(jié)點值的大小，若大于當(dāng)前結(jié)點，插入左子樹，反之，插入右子樹
        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.insert = function(key) {
        let newNode = new Node(key)
        if(root === null) {
            root = newNode
        } else {
            insertNode(root, newNode)
        }
    }
}

let nodes = [8,3,30,1,6,14,4,7,13]
// 創(chuàng)建樹實例
let tree = new BinaryTree()
nodes.forEach(function(key) {
    tree.insert(key)
})
console.log("創(chuàng)建的二叉樹是：", tree.getRoot())

至此，一棵二叉排序樹就構(gòu)造完啦。接下來我們根據(jù)構(gòu)造的這顆二叉樹進行相應(yīng)遍歷、查找與刪除操作。

遍歷二叉樹

二叉樹的遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷。

深度優(yōu)先遍歷

深度優(yōu)先遍歷（Depth First Search）是指沿著樹的深度進行遍歷樹的結(jié)點。其中深度優(yōu)先遍歷又分為三種：前序遍歷、中序遍歷、后序遍歷。

這里前序、中序、后序是根據(jù)根結(jié)點的順序命名的。

1、前序遍歷

定義

前序遍歷也叫做先根遍歷、先序遍歷、前序周游，記做 根左右。

先訪問根結(jié)點；

前序遍歷左子樹；

前序遍歷右子樹。

前序遍歷的作用是可以復(fù)制已有的二叉樹，且比重新構(gòu)造的二叉樹的效率高。

下面我們來看它的算法實現(xiàn)。分為遞歸與非遞歸兩種。

方法一遞歸實現(xiàn)

function BinaryTree() {
    // 這里省略了二叉排序樹的構(gòu)建方法
    
    // 定義前序遍歷算法
    let preOrderTraverseNode = function(node, callback) {
        if(node !== null) {
            callback(node.key) // 先訪問當(dāng)前根結(jié)點
            preOrderTraverseNode(node.left, callback) // 訪問左子樹
            preOrderTraverseNode(node.right, callback) // 訪問右子樹
        }
    }
    
    // 定義前序遍歷方法
    this.preOrderTraverse = function(callback) {
       preOrderTraverseNode(root, callback) 
    }
}

let nodes = [8,3,10,1,6,14,4,7,13]
let tree = new BinaryTree()
nodes.forEach(function(key) {
    tree.insert(key) // 構(gòu)造二叉樹
})

// 定義回調(diào)函數(shù)
let callback = function(key) {
    console.log(key)
}
tree.preOrderTraverse(callback) // 8 3 1 6  4 7 10 14 13

方法二非遞歸實現(xiàn)

function BinaryTree() {
    // ...
    
    // 定義前序遍歷算法
    let preOrderTraverseNode = function(node, callback) {
        let stack = []
        if(node !== null) {
            stack.push(node)
        }
        while(stack.length) {
            let temp = stack.pop()
            callback(temp.key)
            // 這里先放右邊再放左邊是因為取出來的順序相反
            if(temp.right !== null) {
                stack.push(temp.right)
            }
            if(temp.left !== null) {
                stack.push(temp.left)
            }
        }
    }
    
    // 定義前序遍歷方法
    this.preOrderTraverse = function(callback) {
        preOrderTraverseNode(root, callback)
    }
}

let nodes = [8,3,10,1,6,14,4,7,13]
let tree = new BinaryTree()
nodes.forEach(function(key) {
    tree.insert(key) // 構(gòu)造二叉樹
})

// 定義回調(diào)函數(shù)
let callback = function(key) {
    console.log(key)
}
tree.preOrderTraverse(callback) //8 3 1 6  4 7 10 14 13

2、中序遍歷

定義

中序遍歷也叫做中根遍歷、中序周游，記做 左根右。

若左子樹不為空，則先中序遍歷左子樹；

訪問根結(jié)點；

若右子樹不為空，則中序遍歷右子樹。

中序遍歷二叉排序樹，得到的數(shù)組是有序的且是升序的。

下面我們來看中序遍歷算法的實現(xiàn)。分為遞歸和非遞歸兩種。

方法一遞歸實現(xiàn)

function BinaryTree() {
    // 省略二叉排序樹的創(chuàng)建
    
    // 定義中序遍歷算法
    let inOrderTraverseNode = function(node, callback) {
        if(node !== null) {
            inOrderTraverseNode(node.left, callback) // 先訪問左子樹
            callback(node.key) // 再訪問當(dāng)前根結(jié)點
            inOrderTraverseNode(node.right, callback) // 訪問右子樹
        }
    }
    
    // 定義中序遍歷方法
    this.inOrderTraverse = function(callback) {
       inOrderTraverseNode(root, callback) 
    }
}

let nodes = [8,3,10,1,6,14,4,7,13]
let tree = new BinaryTree()
nodes.forEach(function(key) {
    tree.insert(key) // 構(gòu)造二叉樹
})

// 定義回調(diào)函數(shù)
let callback = function(key) {
    console.log(key)
}
tree.inOrderTraverse(callback) // 1 3 4 6 7 8 10 13 14

方法二非遞歸實現(xiàn)

借助于棧，先將左子樹全部放進棧中，之后輸出，最后處理右子樹。

function BinaryTree() {
    // 省略二叉排序樹的構(gòu)建方法
    
     // 定義中序遍歷算法
    let inOrderTraverseNode = function(node, callback) {
        let stack = []
        while(true) {
            // 將當(dāng)前結(jié)點的左子樹推入棧
            while(node !== null) {
                stack.push(node)
                node = node.left
            }

            // 定義終止條件
            if(stack.length === 0) {
                break
            }
            let temp = stack.pop()
            callback(temp.key)
            node = temp.right
        }
    }
    this.inOrderTraverse = function(callback) {
        inOrderTraverseNode(root, callback) 
    }
}

let nodes = [8,3,10,1,6,14,4,7,13]
let tree = new BinaryTree()
nodes.forEach(function(key) {
    tree.insert(key) // 構(gòu)造二叉樹
})

// 定義回調(diào)函數(shù)
let callback = function(key) {
    console.log(key)
}
tree.inOrderTraverse(callback) // 1 3 4 6 7 8 10 13 14

3、后序遍歷

定義

后序遍歷也叫做后根遍歷、后序周游，記做 左右根。

若左子樹不為空，后序遍歷左子樹；

若右子樹不為空，后序遍歷右子樹；

訪問根結(jié)點。

后序遍歷的作用用于文件系統(tǒng)路徑中，或?qū)⒄１磉_式變成逆波蘭表達式。

下面我們來看后序遍歷算法的實現(xiàn)。分為遞歸和非遞歸兩種。

方法一遞歸實現(xiàn)

// 先構(gòu)造一棵二叉樹
function BinaryTree() {
    // 省略二叉排序樹的構(gòu)建方法

    // 定義后序遍歷算法
    let postOrderTraverseNode = function(node, callback) {
        if(node !== null) {
            postOrderTraverseNode(node.left, callback) // 遍歷左子樹
            postOrderTraverseNode(node.right, callback) // 再遍歷右子樹
            callback(node.key) // 訪問根結(jié)點
        }
    }
    
    // 定義后序遍歷方法
    this.postOrderTraverse = function(callback) {
        postOrderTraverseNode(root, callback)
    }
}
let nodes = [8,3,10,1,6,14,4,7,13]
let tree = new BinaryTree()
nodes.forEach(function(key){
    tree.insert(key)
})

// 定義回調(diào)函數(shù)
let callback = function(key) {
    console.log(key)
}

tree.postOrderTraverse(callback) // 1 4 7 6 3 13 14 10 8

方法二非遞歸實現(xiàn)

// 先構(gòu)造一棵二叉樹
function BinaryTree() {
    // 省略二叉排序樹的構(gòu)建方法

    // 定義后序遍歷算法
    let postOrderTraverseNode = function(node, callback) {
        let stack = []
        let res = []
        stack.push(node)
        while(stack.length) {
            let temp = stack.pop()
            res.push(temp.key)
            if(temp.left !== null) {
                stack.push(temp.left)
            }
            if(temp.right !== null) {
                stack.push(temp.right)
            }
        }
        callback(res.reverse())
    }
    
    // 定義后序遍歷方法
    this.postOrderTraverse = function(callback) {
        postOrderTraverseNode(root, callback)
    }
}
let nodes = [8,3,10,1,6,14,4,7,13]
let tree = new BinaryTree()
nodes.forEach(function(key){
    tree.insert(key)
})

// 定義回調(diào)函數(shù)
let callback = function(key) {
    console.log(key)
}

tree.postOrderTraverse(callback) // 1 4 7 6 3 13 14 10 8

廣度優(yōu)先遍歷

廣度優(yōu)先遍歷（Breadth First Search），又叫做寬度優(yōu)先遍歷、層次遍歷，是指從根結(jié)點沿著樹的寬度搜索遍歷。

下面來看它的實現(xiàn)原理

方法一遞歸

function BinaryTree() {
    // 省略二叉排序樹的構(gòu)建
    
    let wideOrderTraverseNode = function(root) {
        let stack = [root] // 先將要遍歷的樹壓入棧

        return function bfs(callback) {
            let node = stack.shift()
            if(node) {
                callback(node.key)
                if(node.left) stack.push(node.left);
                if(node.right) stack.push(node.right);
                bfs(callback)
            }
        }
    }
    
     this.wideOrderTraverse = function(callback) {
        wideOrderTraverseNode(root)(callback)
    }
}

let nodes = [8,3,10,1,6,14,4,7,13]
let tree = new BinaryTree()
nodes.forEach(function(key) {
    tree.insert(key)
})
// 定義回調(diào)函數(shù)
let callback = function(key) {
    console.log(key)
}

tree.wideOrderTraverse(callback) // 8,3,10,1,6,14,4,7,13

方法二非遞歸

使用棧實現(xiàn)，未訪問的元素入棧，訪問后則出棧，并將其leve左右元素入棧，直到葉子元素結(jié)束。

function BinaryTree() {
    // 省略二叉排序樹的構(gòu)建
    
    let wideOrderTraverseNode = function(node, callback) {
        let stack = []
        if(node === null) {
            return []
        }
        stack.push(node)
        while(stack.length) {
            // 每一層的結(jié)點數(shù)
            let level = stack.length
            // 遍歷每一層元素
            for(let i = 0; i < level; i++) {
                // 當(dāng)前訪問的結(jié)點出棧
                let temp = stack.shift()
                
                // 出棧結(jié)點的孩子入棧
                temp.left ? queue.push(temp.left) : ""
                temp.right ? queue.push(temp.right) : ""
                callback(temp.key)
            }
        }
    }
    
     this.wideOrderTraverse = function(callback) {
        wideOrderTraverseNode(root, callback)
    }
}

let nodes = [8,3,10,1,6,14,4,7,13]
let tree = new BinaryTree()
nodes.forEach(function(key) {
    tree.insert(key)
})
// 定義回調(diào)函數(shù)
let callback = function(key) {
    console.log(key)
}

tree.wideOrderTraverse(callback) // 8,3,10,1,6,14,4,7,13

方法三非遞歸

function BinaryTree() {
    // 省略二叉排序樹的構(gòu)建
    
    let wideOrderTraverseNode = function(node, callback) {
        let stack = []
        if(node === null) {
            return []
        }
        stack.push(node)
        while(stack.length) {
            let temp = stack.shift()
            callback(temp.key)
            if(temp.left) {
                stack.push(temp.left)
            }
            if(temp.right) {
                stack.push(temp.right)
            }
        }
    }
    
     this.wideOrderTraverse = function(callback) {
        wideOrderTraverseNode(root, callback)
    }
}

let nodes = [8,3,10,1,6,14,4,7,13]
let tree = new BinaryTree()
nodes.forEach(function(key) {
    tree.insert(key)
})
// 定義回調(diào)函數(shù)
let callback = function(key) {
    console.log(key)
}

tree.wideOrderTraverse(callback) // 8,3,10,1,6,14,4,7,13

鑒于篇幅過長，二叉樹結(jié)點的查找和刪除會在下一篇文章內(nèi)~

云服務(wù)器 GPU云服務(wù)器二叉樹遍歷二叉樹的遍歷 JS二叉樹遍歷非遞歸二叉樹遍歷

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/109763.html

發(fā)表評論

登陸后可評論

0條評論

aboutU

男|高級講師

我要關(guān)注我要私信

TA的文章

【如何構(gòu)建商業(yè)級別聊天系統(tǒng)】 MQTT 篇（五）保活 Keep Alive，請不要讓你的 MQTT

閱讀 2570·2021-09-02 15:40
javascript 事件流捕獲與冒泡

閱讀 1575·2019-08-30 15:54
一個極簡主義設(shè)計的 Hexo 主題

閱讀 1088·2019-08-30 12:48
三列布局（左右固定，中間自適應(yīng)）

閱讀 3409·2019-08-29 17:23
回味background

閱讀 1056·2019-08-28 18:04
二叉樹遍歷

閱讀 3673·2019-08-26 13:54
對JavaScript對象的理解

閱讀 614·2019-08-26 11:40
精讀《源碼學(xué)習(xí)》

閱讀 2404·2019-08-26 10:15

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

二叉樹遍歷

定義

插入算法

定義

方法一遞歸實現(xiàn)

方法二非遞歸實現(xiàn)

定義

方法一遞歸實現(xiàn)

方法二非遞歸實現(xiàn)

定義

方法一遞歸實現(xiàn)

方法二非遞歸實現(xiàn)

方法一遞歸

方法二非遞歸

方法三非遞歸

相關(guān)文章

**Java數(shù)據(jù)結(jié)構(gòu)與算法——二叉樹及操作(包括二叉樹遍歷)**

js數(shù)據(jù)結(jié)構(gòu)和算法（三）二叉樹

**【數(shù)據(jù)結(jié)構(gòu)初階之二叉樹】：二叉樹相關(guān)的性質(zhì)和經(jīng)典的習(xí)題（用C語言實現(xiàn)，附圖詳解）**

【數(shù)據(jù)結(jié)構(gòu)】鏈?zhǔn)?em>二叉樹結(jié)構(gòu)的實現(xiàn)

發(fā)表評論

0條評論

aboutU

男|高級講師

TA的文章

【如何構(gòu)建商業(yè)級別聊天系統(tǒng)】 MQTT 篇（五）保活 Keep Alive，請不要讓你的 MQTT

javascript 事件流捕獲與冒泡

一個極簡主義設(shè)計的 Hexo 主題

三列布局（左右固定，中間自適應(yīng)）

回味background