JavaScript二叉树实现和原理完全讲解 _数据结构

数组、链表、栈和队列都是线性数据结构，树（tree）是有层次的数据结构，树是非线性数据结构，本质上属于图（graph）（更多图深入的内容可查看：图论算法实现和原理解析）。二叉树的查找效率介于线性表和散列表之间，是比较适中的数据结构，二叉树的查找、插入和删除平均时间都是O(logn)，数据库如MySQL也是使用树实现的（更全面的树内容可查看：二叉树、AVL平衡二叉树、伸展树、B-树和B+树详解）。

文章图片
一、二叉树的基本概念

文章图片
如上图是一个二叉树，最顶部的结点叫做的根，每个结点下面的两个直接几点叫做这个结点的儿子，结点上面连接的是它的父结点。例如根结点9的左儿子是7，右儿子是20，结点8的父结点是7，没有儿子的结点叫做叶子结点，如13是叶子结点。
为什么使用树这种数据结构呢？当遇到需要储存某些有层次的数据信息时，使用树储存更方便，例如计算机内的文件系统。树如二叉树提供更稳定的访问或查找、插入和删除，相对于链表更快（但是比数组和散列表慢），类似于链表，但不像数组，结点间的连接使用指针，可动态创建节点或释放结点。
树或二叉树有哪些应用？可操作有层次或分层的数据；更容易更快访问数据；数据可排序；作为一个工作流程，合成数字图像的视觉效果；路由算法；多阶段决策的多种形式（如决策树）等。
二叉树：一个树中每个结点只有最多两个儿子的树叫做二叉树（binary tree），因为每个结点只有两个儿子，所以我们可以简单地称它们为左儿子和右儿子。
二叉树的结点关键字及其关系：每个结点都有一个关键字key，一般形式是当前结点P关键字P.key大于左儿子的关键字L.key，小于右儿子的关键字R.key。
【JavaScript二叉树实现和原理完全讲解】二叉树的深度和高度：一个结点的深度是指从根结点到该结点的结点数，如上图，结点7的深度为2；一个结点的高度是指从该结点到叶结点的结点数，如结点7的高度为2；一棵树的深度等于它的高度，上图二叉树的高度和深度为3（有些书中，根结点的深度和叶子结点的高度为0，如果使用这个标准，那么相关的操作需要做相应的变化）。
二叉树的数据结构表示：一个树可以用一个根结点的指针root表示，如果树为空，那么root的值为null，一个树结点至少包含以下三个部分：

数据部分
指向左儿子的指针或引用
指向右儿子的指针或引用

二、二叉树的属性详解二叉树的一些重要属性如下：
1、二叉树中，层次数为l的二叉树的最大结点数为2^(l-1)
其中层数l是根结点到当前结点的结点数，根结点的层数为1，当只有一个根结点事，结点数为2^0=1。因为二叉树只有最多两个儿子，所以在层数l的下一层的结点数有2倍多的结点，即2*2^(l-1)。
2、高度为h的二叉树最大结点数为2^h-1
单结点树的高度为1，上图二叉树的高度为3，最大结点数为2^3-1=7。
3、n个结点的二叉树中，最小可能高度为Log(n+1)，该结论可以由上面的结论推出来。
三、JavaScript实现二叉树实现二叉树的最重要的两个操作是插入和删除，其中涉及到DFS深度遍历，可查看上面提供的二叉树文章获取更多内容。其中删除操作稍微困难，它的基本逻辑是：

如果只有一个儿子，则使用这个儿子替换当前结点。
如果有两个儿子，获取左子树中的最大值结点q，或右子树的最小值结点q替换该结点，然后再删除q。
对于没有儿子的结点，即叶结点，直接删除。

文章图片
如上图，删除结点17，该结点只有一个儿子21，直接使用21替换17。如果要删除5，因为结点5的关键字比所有左子树的关键字都大，比右子树的所有结点关键字都小，所以，可以取左子树的最大值3替换5，或取右子树的最小值19替换5。
你可以发现，频繁的删除操作会导致二叉树偏左或偏右，导致二叉树极度不平衡，这样会使二叉树的深度过深，最差的情况为O(n)。因此有两种树可以做平衡操作：AVL平衡二叉树和伸展树，更多内容可以参考上面的文章。
二叉树的大部分操作都是基于DFS或BFS，所以如果你对DFS和BFS不了解，建议你参考上面提供的关于树的文章。
下面是普通二叉树的JavaScript实现代码：

// 结点 function Node(key, value){ this.key = key; this.value = http://www.srcmini.com/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 = http://www.srcmini.com/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();