数据结构（12）二进制搜索树

在前面，我们学习了一些有关树木以及更重要的二叉树的特征的概念.

现在，我们向二叉树添加另一个限制，然后我们可以形成二叉搜索树.

首先让我们简要地了解什么是二叉搜索树.

以下哪些是二进制搜索树，哪些不是？

img

二叉搜索树的特征:

现在，我们使用代码来实现二进制搜索树.

对于BinarySearchTree，您只需保存根节点，因为可以通过根节点找到其他节点. 在代码中的insertNode方法中，我们尚未实现它，这是我们接下来要完成的任务.

插入非根节点

BinarySerachTree.prototype.insertNode = function (node, newNode) {
    if (newNode.key < node.key) { // 1.准备向左子树插入数据
        if (node.left === null) { // 1.1.node的左子树上没有内容
            node.left = newNode
        } else { // 1.2.node的左子树上已经有了内容
            this.insertNode(node.left, newNode)
        }
    } else { // 2.准备向右子树插入数据
        if (node.right === null) { // 2.1.node的右子树上没有内容
            node.right = newNode
        } else { // 2.2.node的右子树上有内容
            this.insertNode(node.right, newNode)
        }
    }
}

代码分析:

代码的数字1位置是准备将数据插入到左子树中. 但是，它分为两种情况. 该代码的数字2位置与数字1位置几乎相同，但是它位于右侧. <

测试代码: 如果按照以下代码插入，最终会形成什么样的树？

// 测试代码
var bst = new BinarySerachTree()
// 插入数据
bst.insert(11)
bst.insert(7)
bst.insert(15)
bst.insert(5)
bst.insert(3)
bst.insert(9)
bst.insert(8)
bst.insert(10)
bst.insert(13)
bst.insert(12)
bst.insert(14)
bst.insert(20)
bst.insert(18)
bst.insert(25)

形成的树

img

如果这时我插入一个新数据6，插入位置和顺序应该是什么？

bst.insert(6)

新树:

img

树的遍历:

穿越过程:

img

遍历的代码实现

BinarySerachTree.prototype.preOrderTraversal = function (handler) {
    this.preOrderTranversalNode(this.root, handler)
}
BinarySerachTree.prototype.preOrderTranversalNode = function (node, handler) {
    if (node !== null) {
        // 1.打印当前经过的节点
        handler(node.key)
        // 2.遍历所有的左子树
        this.preOrderTranversalNode(node.left, handler)
        // 3.遍历所有的右子树
        this.preOrderTranversalNode(node.right, handler)
    }
}

按顺序遍历代码的示例:

img

穿越过程:

img

遍历的代码实现:

// 中序遍历
BinarySerachTree.prototype.inOrderTraversal = function (handler) {
    this.inOrderTraversalNode(this.root, handler)
}
BinarySerachTree.prototype.inOrderTraversalNode = function (node, handler) {
    if (node !== null) {
        this.inOrderTraversalNode(node.left, handler)
        handler(node.key)
        this.inOrderTraversalNode(node.right, handler)
    }
}

测试代码:

// 测试中序遍历结果
resultString = ""
bst.inOrderTraversal(function (key) {
    resultString += key + " "
})
alert(resultString) // 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25 

代码分析:

代码中的顺序遍历图:

img

穿越过程:

img

遍历的代码实现:

// 后续遍历
BinarySerachTree.prototype.postOrderTraversal = function (handler) {
    
}
BinarySerachTree.prototype.postOrderTraversalNode = function (node, handler) {
    if (node !== null) {
        this.postOrderTraversalNode(node.left, handler)
        this.postOrderTraversalNode(node.right, handler)
        handler(node.key)
    }
}

测试代码:

// 测试后续遍历结果
resultString = ""
bst.postOrderTraversal(function (key) {
    resultString += key + " "
})
alert(resultString) // 3 6 5 8 10 9 7 12 14 13 18 25 20 15 11 

后续遍历

后续代码遍历的例证:

img

它也可以使用递归来实现数据结构二叉排序树，但是在这里不是必须的，但是递归增加了代码的复杂性.

代码测试:

// 获取最值
alert(bst.min()) // 3
alert(bst.max()) // 25

在其他情况下，根据节点的密钥. 以及传入的键来确定是向左看还是向右看.

测试代码:

// 查找特定的值
alert(bst.search(10)) // true
alert(bst.search(21)) // false

非递归代码实现:

BinarySerachTree.prototype.search = function (key) {
    var node = this.root
    while (node !== null) {
        if (node.key > key) {
            node = node.left
        } else if (node.key < key) {
            node = node.right
        } else {
            return true
        }
    }
    return false
}

递归还是循环？

二进制搜索树的删除有些复杂. 为了让每个人都更清楚地理解该原理数据结构二叉排序树，我将分别解释这一部分.

首先寻找要删除的节点

// 删除结点
BinarySerachTree.prototype.remove = function (key) {
    // 1.定义临时保存的变量
    var current = this.root
    var parent = this.root
    var isLeftChild = true
    // 2.开始查找节点
    while (current.key !== key) {
        parent = current
        if (key < current.key) {
            isLeftChild = true
            current = current.left
        } else {
            isLeftChild = false
            current = current.right
        }
        // 如果发现current已经指向null, 那么说明没有找到要删除的数据
        if (current === null) return false
    }
    return true
}

代码分析:

在上面代码2的位置，开始搜索相应的密钥.

说明过程:

代码实现如下:

// 3.删除的结点是叶结点
if (current.left === null && current.right === null) {
    if (current == this.root) {
        this.root == null
    } else if (isLeftChild) {
        parent.left = null
    } else {
        parent.right = null
    }
}

代码分析:

说明过程:

img

代码实现如下:

// 4.删除有一个子节点的节点
else if (current.right === null) {
    if (current == this.root) {
        this.root = current.left
    } else if (isLeftChild) {
        parent.left = current.left
    } else {
        parent.right = current.left
    }
} else if (current.left === null) {
    if (current == this.root) {
        this.root = current.right
    } else if (isLeftChild) {
        parent.left = current.right
    } else {
        parent.right = current.right
    }
}

代码分析:

如果分析清楚，则相对简单.

首先考虑一下我的一些问题:

img

首先，让我们总结一下删除两个节点的规则:

如何找到该节点？前任和后继者将删除具有两个子节点的当前节点，或者找到其前任或后继者. 所以，接下来，我们首先找到一个这样的节点（前任或后任者都很好，我将在这里寻找后任者作为示例）

查找后继代码实现:

// 找后继的方法
BinarySerachTree.prototype.getSuccessor = function (delNode) {
    // 1.使用变量保存临时的节点
    var successorParent = delNode
    var successor = delNode
    var current = delNode.right // 要从右子树开始找
    // 2.寻找节点
    while (current != null) {
        successorParent = successor
        successor = current
        current = current.left
    }
    // 3.如果是删除图中15的情况, 还需要如下代码
    if (successor != delNode.right) {
        successorParent.left = successor.right
        successor.right = delNode.right
    }
    
    return successor
}

代码分析:

查找后续处理代码:

// 5.删除有两个节点的节点
else {
    // 1.获取后继节点
    var successor = this.getSuccessor(current)
    
    // 2.判断是否是根节点
    if (current == this.root) {
        this.root = successor
    } else if (isLeftChild) {
        parent.left = successor
    } else {
        parent.right = successor
    }
    
    // 3.将删除节点的左子树赋值给successor
    successor.left = current.left
}

代码分析:

要求3: 要从判决中提取后继者. left= current.left.

回头看待办事项

完成它，结束工作！！！上面的方法看起来很聪明，但实际上是一种转义.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-242898-1.html