排序二叉树

什么是排序二叉树？

• 首先它是二叉树，二叉树的每个结点最多有两个子节点
• 排序二叉树就是左节点（如果存在的话）一定小于父节点，右节点（如果存在的话）一定大于父节点的二叉树

常用遍历方法

• 前序遍历（复制一个排序二叉树最快）
• 中序遍历（得到二叉树从小到大排序的数据）
• 后序遍历（文件系统常用）

引用一张图片作为例子

image

算法思想和例子

前序遍历

• 思想：先访问根节点，再访问左孩子，最后访问右孩子
• 以上图为例：得到 [8, 3, 1, 6, 4, 7, 10, 14, 13]
• 伪代码：

// 根 --> 左 --> 右
// root是根节点或者是当前节点
function Traversal(root) {
    //访问输出根节点
    print(root)
    // 左节点存在
    if (root.left) {
        Traversal(root.left)
    }
    //右节点存在
    if (root.right) {
        // root.right作为根节点
        Traversal(root.right)
    }
}

中序遍历

• 思想：先访问左孩子，再访问根节点，最后访问右孩子
• 以上图为例：得到 [1, 3, 4, 6, 7, 8, 10, 13, 14]
• 伪代码：

// 左 --> 根 --> 右
function Traversal(root){
    if (root.left) {
        Traversal(root.left)
    }

    print(root)

    if (root.right) {
        Traversal(root.right)
    }
}

后序遍历

• 思想：先访问左孩子，再访问右孩子，最后访问根节点
• 以上图为例：得到 [1, 4, 7, 6, 3, 13, 14, 10, 8]
• 伪代码：

// 左 --> 右 --> 根
function Traversal(root){
    if (root.left) {
        Traversal(root.left)
    }

    if (root.right) {
        Traversal(root.right)
    }

    print(root)
}

总结帮助记忆

• X序遍历一定都是先访问左子树再访问右子树的
• 前序遍历：根 --> 左 --> 右
• 中序遍历：左 --> 根 --> 右
• 后序遍历：左 --> 右 --> 根
• X序遍历是指访问根的顺序