java二叉树的实现代码怎么编写?

TheDisguiser 2020-07-14 17:17:13 java常见问答 5549

二叉树相信有深入了解过java的小伙伴们一定都是知道的,这种数据结构一直是程序一个较重要的环节,这次通过一些实例让我们来了解了解它是如何实现的吧。

例:

// 结点
function Node(key, value)
{
    this.key = key;
    this.value = value;
    this.left = this.right = null;
}
// 二叉树
function BinaryTree()
{
    this.size = 0;
    this.root = null;
}
// 检查二叉树是否为空
BinaryTree.prototype.isEmpty = function ()
{
    return this.size == 0;
}
// DFS
BinaryTree.prototype.__addNode = function (node, newNode)
{
    if (node == null)
        return newNode;
    else if (node.key > newNode.key)
    {
        node.left = this.__addNode(node.left, newNode);
        return node;
    }
    else
    {
        node.right = this.__addNode(node.right, newNode);
        return node;
    }
}
// 添加数据到二叉树中
BinaryTree.prototype.add = function (key, value)
{
    var node = new Node(key, value);
    this.root = this.__addNode(this.root, node);
    this.size++;
}
BinaryTree.prototype.__findLeftMax = function (node)
{
    if (node.right == null)
        return node;
    return this.__findLeftMax(node.right);
}
// DFS
BinaryTree.prototype.__deleteNode = function (node, key)
{
    if (node == null)
        return null;
    if (node.key == key)
    {
        var left = node.left;
        var right = node.right;
        this.size--;
        // 叶子
        if (left == null && right == null)
        {
            return null;
        }
        // 有两个儿子
        else if (left != null && right != null)
        {
            var t = this.__findLeftMax(node.left);
            node.key = t.key;
            node.value = t.value;
            node.left = this.__deleteNode(node.left, t.key);
            return node;
        }
        // 只有一个儿子
        else if (left != null || right != null)
        {
            var t = left != null ? left : right;
            return t;
        }
    }
    else if (node.key > key)
    {
        node.left = this.__deleteNode(node.left, key);
        return node;
    }
    else
    {
        node.right = this.__deleteNode(node.right, key);
        return node;
    }
}
// 从二叉树中删除一个数据
BinaryTree.prototype.delete = function (key)
{
    if (this.isEmpty())
        return;
    this.root = this.__deleteNode(this.root, key);
}
BinaryTree.prototype.__search = function (node, key)
{
    if (node == null)
        return null;
    if (node.key == key)
        return node.value;
    else if (node.key > key)
        return this.__search(node.left, key);
    else
        return this.__search(node.right, key);
}
// 根据key搜索二叉树
BinaryTree.prototype.search = function (key)
{
    if (this.isEmpty())
        return null;
    return this.__search(this.root, key);
}
// 检查二叉树是否存在某个key的数据
BinaryTree.prototype.contains = function (key)
{
    return this.search(key) != null;
}
BinaryTree.prototype.__traverse = function (node)
{
    if (node == null)
        return "";
    var s1 = this.__traverse(node.left);
    var str = s1 + " " + node.key;
    var s2 = this.__traverse(node.right);
    return str + " " + s2;
}
// 遍历二叉树
BinaryTree.prototype.traverse = function ()
{
    if (this.isEmpty())
        return;
    var str = this.__traverse(this.root);
    console.log(str);
}
// 调用实例
var tree = new BinaryTree();
tree.add(10, 10);
tree.add(6, 6);
tree.add(4, 4);
tree.add(7, 7);
tree.add(20, 20);
tree.add(14, 14);
tree.add(23, 23);
tree.add(15, 15);
tree.add(21, 21);
tree.add(8, 8);
tree.traverse();
console.log("tree contains 20: " + tree.contains(20));
tree.delete(10); // 删除根结点,有两个儿子
console.log("tree contains 10: " + tree.contains(10));
tree.traverse();
tree.delete(15); // 删除叶子结点,无儿子
tree.traverse();
tree.delete(23); // 删除内部结点,只有一个儿子
tree.traverse();

以上就是关于二叉树实现的所有内容,还想了解更多java常见问题及解决方法的小伙伴可以来关注我们的网站了解详情。

推荐阅读:

java二叉树算法,二叉树常用算法实现详解

java二叉树中所有距离为K的结点详解

二叉树是线性结构吗?什么是线性结构呢?