二叉樹遍歷

aboutU 發布于2019-08-26 13:54 / 3669人閱讀

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

前言

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

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

二叉排序樹

定義

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

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

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

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

插入算法

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

// 構建二叉樹
function BinaryTree() {
    // 定義結點
    let Node = function(key) {
        this.key = key
        this.left = left
        this.right = right
    }
    
    // 定義根結點
    let root = null
    
    // 獲得整棵樹
    this.getRoot = function() {
        return this.root
    }
    // 定義插入結點算法
    let 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.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]
// 創建樹實例
let tree = new BinaryTree()
nodes.forEach(function(key) {
    tree.insert(key)
})
console.log("創建的二叉樹是：", tree.getRoot())

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

遍歷二叉樹

二叉樹的遍歷分為深度優先遍歷和廣度優先遍歷。

深度優先遍歷

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

這里前序、中序、后序是根據根結點的順序命名的。

1、前序遍歷

定義

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

先訪問根結點；

前序遍歷左子樹；

前序遍歷右子樹。

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

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

方法一遞歸實現

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

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

方法二非遞歸實現

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) // 構造二叉樹
})

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

2、中序遍歷

定義

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

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

訪問根結點；

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

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

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

方法一遞歸實現

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

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

方法二非遞歸實現

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

function BinaryTree() {
    // 省略二叉排序樹的構建方法
    
     // 定義中序遍歷算法
    let inOrderTraverseNode = function(node, callback) {
        let stack = []
        while(true) {
            // 將當前結點的左子樹推入棧
            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) // 構造二叉樹
})

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

3、后序遍歷

定義

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

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

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

訪問根結點。

后序遍歷的作用用于文件系統路徑中，或將正常表達式變成逆波蘭表達式。

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

方法一遞歸實現

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

    // 定義后序遍歷算法
    let postOrderTraverseNode = function(node, callback) {
        if(node !== null) {
            postOrderTraverseNode(node.left, callback) // 遍歷左子樹
            postOrderTraverseNode(node.right, callback) // 再遍歷右子樹
            callback(node.key) // 訪問根結點
        }
    }
    
    // 定義后序遍歷方法
    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)
})

// 定義回調函數
let callback = function(key) {
    console.log(key)
}

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

方法二非遞歸實現

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

    // 定義后序遍歷算法
    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)
})

// 定義回調函數
let callback = function(key) {
    console.log(key)
}

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

廣度優先遍歷

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

下面來看它的實現原理

方法一遞歸

function BinaryTree() {
    // 省略二叉排序樹的構建
    
    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)
})
// 定義回調函數
let callback = function(key) {
    console.log(key)
}

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

方法二非遞歸

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

function BinaryTree() {
    // 省略二叉排序樹的構建
    
    let wideOrderTraverseNode = function(node, callback) {
        let stack = []
        if(node === null) {
            return []
        }
        stack.push(node)
        while(stack.length) {
            // 每一層的結點數
            let level = stack.length
            // 遍歷每一層元素
            for(let i = 0; i < level; i++) {
                // 當前訪問的結點出棧
                let temp = stack.shift()
                
                // 出棧結點的孩子入棧
                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)
})
// 定義回調函數
let callback = function(key) {
    console.log(key)
}

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

方法三非遞歸

function BinaryTree() {
    // 省略二叉排序樹的構建
    
    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)
})
// 定義回調函數
let callback = function(key) {
    console.log(key)
}

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

鑒于篇幅過長，二叉樹結點的查找和刪除會在下一篇文章內~

GPU云服務器云服務器二叉樹遍歷二叉樹的遍歷 JS二叉樹遍歷非遞歸二叉樹遍歷

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

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

Java數據結構與算法——二叉樹及操作(包括二叉樹遍歷)

摘要：本篇主要介紹二叉樹的概念二叉樹的表示二叉樹的操作三種遍歷方式實現求二叉樹的子樹求節點的父節點二叉樹高度，可能是考試中的，也可能是面試中的。通常二叉樹的遍歷根據根節點的遍歷次序分為先根遍歷中根遍歷后根遍歷。聲明：碼字不易，轉載請注明出處，歡迎文章下方討論交流。前言：Java數據結構與算法專題會不定時更新，歡迎各位讀者監督。本篇主要介紹二叉樹的概念、二叉樹的表示、二叉樹的操作（三種遍歷...

muddyway 2019-08-16 11:15 評論0 收藏0
js數據結構和算法（三）二叉樹

摘要：同樣結點樹的二叉樹，完全二叉樹的深度最小。二叉樹每個結點最多有兩個孩子，所以為它設計一個數據域和兩個指針域是比較自然的想法，我們稱這樣的鏈表叫做二叉鏈表。二叉樹的概念二叉樹（Binary Tree）是n（n>=0）個結點的有限集合，該集合或者為空集（空二叉樹），或者由一個根結點和兩棵互不相交的、分別稱為根結點的左子樹和右子樹的二叉樹組成。 showImg(https://seg...

DesGemini 2019-08-21 10:20 評論0 收藏0
【數據結構初階之二叉樹】：二叉樹相關的性質和經典的習題（用C語言實現，附圖詳解）

摘要：當集合為空時，稱該二叉樹為空二叉樹。也就是說，如果一個二叉樹的層數為，且結點總數是，則它就是滿二叉樹。完全二叉樹完全二叉樹是效率很高的數據結構，完全二叉樹是由滿二叉樹而引出來的。 ...

Martin91 2021-11-24 09:39 評論0 收藏0
【數據結構】鏈式二叉樹結構的實現

摘要：但是二叉樹的一些基本實現結構，例如前序遍歷，中序遍歷。。。二叉樹節點聲明二叉樹的遍歷二叉樹的遍歷，是學習二叉樹結構的重要部分。一顆二叉樹的節點個數主要以三個部分構成根節點左子樹的節點個數右子樹的節點個數。前言二叉樹不同于順序表，一顆普通的二叉樹是沒有增刪改查的意義。普通的二叉樹用來存...

changfeng1050 2021-11-17 09:33 評論0 收藏0

發表評論

登陸后可評論

0條評論

aboutU

男|高級講師

我要關注我要私信

TA的文章

【如何構建商業級別聊天系統】 MQTT 篇（五）?；?Keep Alive，請不要讓你的 MQTT

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

閱讀 1572·2019-08-30 15:54
一個極簡主義設計的 Hexo 主題

閱讀 1083·2019-08-30 12:48
三列布局（左右固定，中間自適應）

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

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

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

閱讀 610·2019-08-26 11:40
精讀《源碼學習》

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

国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

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

二叉樹遍歷

定義

插入算法

定義

方法一遞歸實現

方法二非遞歸實現

定義

方法一遞歸實現

方法二非遞歸實現

定義

方法一遞歸實現

方法二非遞歸實現

方法一遞歸

方法二非遞歸

方法三非遞歸

相關文章

**Java數據結構與算法——二叉樹及操作(包括二叉樹遍歷)**

js數據結構和算法（三）二叉樹

**【數據結構初階之二叉樹】：二叉樹相關的性質和經典的習題（用C語言實現，附圖詳解）**

**【數據結構】鏈式二叉樹結構的實現**

發表評論

0條評論

aboutU

男|高級講師

TA的文章

【如何構建商業級別聊天系統】 MQTT 篇（五）?；?Keep Alive，請不要讓你的 MQTT

javascript 事件流捕獲與冒泡

一個極簡主義設計的 Hexo 主題

三列布局（左右固定，中間自適應）

回味background