二叉樹遍歷

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

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

前言

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

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

二叉排序樹

定義

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

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

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

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

插入算法

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

// 構(gòu)建二叉樹
function BinaryTree() {
    // 定義結(jié)點(diǎn)
    let Node = function(key) {
        this.key = key
        this.left = left
        this.right = right
    }
    
    // 定義根結(jié)點(diǎn)
    let root = null
    
    // 獲得整棵樹
    this.getRoot = function() {
        return this.root
    }
    // 定義插入結(jié)點(diǎn)算法
    let insertNode = function(node, newNode) {
        // 比較要插入結(jié)點(diǎn)與當(dāng)前結(jié)點(diǎn)值的大小，若大于當(dāng)前結(jié)點(diǎn)，插入左子樹，反之，插入右子樹
        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)建樹實(shí)例
let tree = new BinaryTree()
nodes.forEach(function(key) {
    tree.insert(key)
})
console.log("創(chuàng)建的二叉樹是：", tree.getRoot())

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

遍歷二叉樹

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

深度優(yōu)先遍歷

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

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

1、前序遍歷

定義

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

先訪問根結(jié)點(diǎn)；

前序遍歷左子樹；

前序遍歷右子樹。

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

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

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

function BinaryTree() {
    // 這里省略了二叉排序樹的構(gòu)建方法
    
    // 定義前序遍歷算法
    let preOrderTraverseNode = function(node, callback) {
        if(node !== null) {
            callback(node.key) // 先訪問當(dāng)前根結(jié)點(diǎn)
            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

方法二非遞歸實(shí)現(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)
            // 這里先放右邊再放左邊是因?yàn)槿〕鰜淼捻樞蛳喾?            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é)點(diǎn)；

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

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

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

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

function BinaryTree() {
    // 省略二叉排序樹的創(chuàng)建
    
    // 定義中序遍歷算法
    let inOrderTraverseNode = function(node, callback) {
        if(node !== null) {
            inOrderTraverseNode(node.left, callback) // 先訪問左子樹
            callback(node.key) // 再訪問當(dāng)前根結(jié)點(diǎn)
            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

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

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

function BinaryTree() {
    // 省略二叉排序樹的構(gòu)建方法
    
     // 定義中序遍歷算法
    let inOrderTraverseNode = function(node, callback) {
        let stack = []
        while(true) {
            // 將當(dāng)前結(jié)點(diǎn)的左子樹推入棧
            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é)點(diǎn)。

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

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

方法一遞歸實(shí)現(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é)點(diǎn)
        }
    }
    
    // 定義后序遍歷方法
    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

方法二非遞歸實(shí)現(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é)點(diǎn)沿著樹的寬度搜索遍歷。

下面來看它的實(shí)現(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

方法二非遞歸

使用棧實(shí)現(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é)點(diǎn)數(shù)
            let level = stack.length
            // 遍歷每一層元素
            for(let i = 0; i < level; i++) {
                // 當(dāng)前訪問的結(jié)點(diǎn)出棧
                let temp = stack.shift()
                
                // 出棧結(jié)點(diǎn)的孩子入棧
                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é)點(diǎn)的查找和刪除會在下一篇文章內(nèi)~

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

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

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

發(fā)表評論

登陸后可評論

0條評論

aboutU

男|高級講師

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

TA的文章

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

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

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

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

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

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

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

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

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

成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲中文字幕日韩无码

資訊專欄INFORMATION COLUMN

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

二叉樹遍歷

定義

插入算法

定義

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

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

定義

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

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

定義

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

方法二非遞歸實(shí)現(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語言實(shí)現(xiàn)，附圖詳解）**

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

發(fā)表評論

0條評論

aboutU

男|高級講師

TA的文章

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

javascript 事件流捕獲與冒泡

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

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

回味background