乐趣区

二叉树遍历

jiezi

前言

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

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

二叉排序树

定义

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

  • 若左子树不为空，左子树上所有结点均小于它的根结点的值；
  • 若右子树不为空，右子树上所有结点均大于它的根结点的值；
  • 左右子树也分别为二叉排序树。
插入算法

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

// 构建二叉树
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 10 1 6 14 4 7 13
方法二 非递归实现

非递归的实现是借助于栈，先访问根结点，并将当前结点从栈中推出，再将当前结点的左右子树推进栈中。

function BinaryTree() {
    // ...
    
    // 定义前序遍历算法
    let preOrderTraverseNode = function(node, callback) {let stack = []
        if(node !== null) {stack.push(node)
            while(stack.length) {let temp = stack.shift()
                callback(temp.key)
                if(temp.left !== null) {stack.push(temp.left)
                }
                if(temp.right !== null) {stack.push(temp.right)
                }
            }
        }
    }
    
    // 定义前序遍历方法
    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 10 1 6 14 4 7 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），又叫做宽度优先遍历、层次遍历，是指从根结点沿着树的宽度搜索遍历。

下面来看它的实现原理

方法一 非递归

使用栈实现，未访问的元素入栈，访问后则出栈，并将其 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

鉴于篇幅过长，二叉树结点的查找和删除会在下一篇文章内~

退出移动版