二叉树相信有深入了解过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常见问题及解决方法的小伙伴可以来关注我们的网站了解详情。
推荐阅读：