二叉树遍历

aboutU 发布于2019-08-26 13:54 / 3635人阅读

摘要：前言本篇文章是在二叉排序树的基础上进行遍历查找与删除结点。接下来我们根据构造的这颗二叉树进行相应遍历查找与删除操作。遍历二叉树二叉树的遍历分为深度优先遍历和广度优先遍历。中序遍历二叉排序树，得到的数组是有序的且是升序的。

前言

本篇文章是在二叉排序树的基础上进行遍历、查找、与删除结点。

那么首先来看一下什么是二叉排序树？

二叉排序树

定义

二叉排序树，又称二叉查找树、二叉搜索树。

若左子树不为空，左子树上所有结点均小于它的根结点的值；

若右子树不为空，右子树上所有结点均大于它的根结点的值；

左右子树也分别为二叉排序树。

插入算法

我们知道了什么是二叉排序树，现在来看下它的具体算法实现。

// 构建二叉树
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二叉树遍历非递归二叉树遍历

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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

阅读 2483·2021-09-02 15:40
javascript 事件流捕获与冒泡

阅读 1544·2019-08-30 15:54
一个极简主义设计的 Hexo 主题

阅读 1063·2019-08-30 12:48
三列布局（左右固定，中间自适应）

阅读 3357·2019-08-29 17:23
回味background

阅读 1033·2019-08-28 18:04
二叉树遍历

阅读 3636·2019-08-26 13:54
对JavaScript对象的理解

阅读 587·2019-08-26 11:40
精读《源码学习》

阅读 2374·2019-08-26 10:15

资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

二叉树遍历

定义

插入算法

定义

方法一递归实现

方法二非递归实现

定义

方法一递归实现

方法二非递归实现

定义

方法一递归实现

方法二非递归实现

方法一递归

方法二非递归

方法三非递归

相关文章

**Java数据结构与算法——二叉树及操作(包括二叉树遍历)**

js数据结构和算法（三）二叉树

**【数据结构初阶之二叉树】：二叉树相关的性质和经典的习题（用C语言实现，附图详解）**

**【数据结构】链式二叉树结构的实现**

发表评论

0条评论

aboutU

男|高级讲师

TA的文章

【如何构建商业级别聊天系统】 MQTT 篇（五）保活 Keep Alive，请不要让你的 MQTT

javascript 事件流捕获与冒泡

一个极简主义设计的 Hexo 主题

三列布局（左右固定，中间自适应）

回味background