二叉树的创建与方法

二叉树是一种重要的数据存储结构，它体现了一对多的数据存储方式，一颗二叉树有一个根节点(root)，与众多分结点组成，每个双亲最多有两个子树分为左子树和右子树，结点的分支数称为这个结点的度，整个二叉树的度为最大的度.度为0的结点称为叶结点. 代码放在GitHub：二叉查找树

满二叉树与完全二叉树

满二叉树每个层级的结点都达到最大完全二叉树必须从左到右依次排序，造成只能右边存在缺失（如果左边缺失势必造成不是正确的排序）

二叉树的创建

每个结点最多只有两个分支left（左子树）、right（右子树）

使用JavaScript实现二叉树的创建

/** * @name: 二叉树创建封装 * @params: null * @return: undefined */ function BinarySearchTree() { // 根节点 this.root=null; // 结点包括左子树和右子树结点和当前的键 this.node=function (key) { this.key=key; this.left=null; this.right=null; }; }

可以看到非常的简单，每个结点由相应的key、left（左子树）、right（右子树）构成，还有一个root（根节点）

添加插入结点的方法

小于双亲的结点在双亲的左边，大于双亲的在双亲的右边根节点的左边为全部小于结点的树，右边全部为大于跟结点如果没有root（根节点）则插入结点为根节点 /** * @name: 二叉树插入方法 * @params: 插入的键 * @return: undefined */ BinarySearchTree.prototype.insert=function (key) { // 创建新结点 let newNode=new this.node(key); if(this.root===null){ this.root=newNode; }else{ this.insertRecurse(this.root,newNode); } } /** * @name:二叉树递归插入方法 * @params: parent（双亲） node（插入的结点） * @return: undefined */ BinarySearchTree.prototype.insertRecurse=function (parent,node) { // 小于为左子树部分，大于为右子树部分 if(node.key<parent.key){ parent.left?this.insertRecurse(parent.left,node):parent.left=node; } else{ parent.right?this.insertRecurse(parent.right,node):parent.right=node; } }

遍历操作

二叉树数据结构常用的遍历方法主要有4种：

前序遍历中序遍历后序遍历层序遍历

各种遍历操作可以用根节点的位置进行区分，遍历顺序都是优先遍历左在遍历右，所以前序遍历顺序为双亲(D)->左子树(L)->右子树( R)，中序遍历顺序为左子树(L)->双亲(D)->右子树( R)，后序遍历顺序为左子树(L)->右子树( R)->双亲(D)，层序遍历就是从左到右、从上到下进行遍历，一般没做说明. 例：如上图满二叉树，前序遍历顺序为 A BDE CFG,上图非完全二叉树遍历顺序为A BD CEF

JavaScript实现前序遍历 假设利用上边的二叉树插入方法，生成一颗二叉树如下： 插入数值

var bst=new BinarySearchTree() bst.insert(11); bst.insert(5); bst.insert(8); bst.insert(10); bst.insert(15); bst.insert(16); bst.insert(12); bst.insert(14); bst.insert(17);

则想要实现的前序遍历顺序应该 11 5 8 10 15 12 14 16 17 实现前序遍历算法：

/** * @name:前序遍历算法 * @params: 接收遍历结果的回调 * @return: undefined */ BinarySearchTree.prototype.prevOrderIterate=function(callback) { this.prevOrderIterateRecurse(this.root,callback); }; // 前序遍历递归 BinarySearchTree.prototype.prevOrderIterateRecurse=function (node,callback) { if(node!==null){ // 返回遍历值 callback(node.key); // 继续遍历左子树，再遍历右子树(利用栈结构特点) this.prevOrderIterateRecurse(node.left,callback); this.prevOrderIterateRecurse(node.right,callback); } } /*调用*/ var res='' bst.prevOrderIterate(function(e) { res+=' '+e; }) console.log(res);

JavaScript实现中序遍历、后序遍历 思想同前序遍历，只需改变递归操作中的顺序即可

/** * @name:中序遍历 * @params: 接收参数的回调 callback: [Function] * @return: undefined */ BinarySearchTree.prototype.midOrderInterate=function (callback) { this.midOrderInterateRecurse(this.root,callback); }; // 中序遍历递归 BinarySearchTree.prototype.midOrderInterateRecurse=function (node,callback) { if(node!==null){ this.midOrderInterateRecurse(node.left,callback); callback(node.key); this.midOrderInterateRecurse(node.right,callback); } }; /** * @name:后序遍历 * @params: 后序遍历的回调 callback [Function] * @return: undefined */ BinarySearchTree.prototype.aftOrderInterate=function (callback) { this.aftOrderInterateRecurse(this.root,callback); }; // 后序遍历递归 BinarySearchTree.prototype.aftOrderInterateRecurse=function (node,callback) { if(node!==null){ this.midOrderInterateRecurse(node.left,callback); this.midOrderInterateRecurse(node.right,callback); callback(node.key); } }