前言我上一篇写的二叉堆可能有些人没有看过，所以这里把二叉树的基本概念复制过来，如果你看过的话，可以忽略前面介绍的二叉树的基本概念，如果对链表的数据结构不清楚的话，最好看看我之前写的js数据结构——链表二叉树BinaryTree(二叉树）是一种树结构，其特点是一个节点最多有两个分支节点，二叉树通常由根节点、分支节点和叶节点组成。每个分支节点通常称为子树。根节点：二叉树的最顶层节点分支节点：除了根节点，它还有叶子节点叶子节点：除了自己之外没有其他子节点。2是6和3的父节点，反之6和3是2个子节点。二叉树的三个性质在二叉树的第i层，当i=1时，最多有2^i-1个节点，只有一个根节点，2^(i-1)=2^0=1一棵深度为k的二叉树，当i=2时最多有2^k-1个节点，2^k-1=2^2-1=3个节点对于任意一棵二叉树T，如果汇总点数为n0，度数为2（子树数为2）的节点数为n2，则n0=n2+1树和二叉树的三个主要差分树的节点数至少为1，而二叉树树中的节点个数可以为0。树中节点的最大度（节点个数）没有限制，而二叉树中节点的最大度为2.完全二叉树（completebinarytree）和满二叉树（fullbinarytree）满二叉树：深度为k，节点数为2^k-1的二叉树称为满二叉树完全二叉树：完全二叉树树的意思是左边最后一层是满的，右边可能满也可能不满，其余层都是满二叉树称为完全二叉树（满二叉树也是完全二叉树）二叉搜索树二叉搜索树满足以下性质：如果任一节点的左子树不为空，则左子树上所有节点的值都小于其根节点的值；如果任一节点的右子树不为空，则右子树上所有节点的值都大于其根节点值的值；任意节点的左右子树也需要满足左小右大的性质。我们举个例子来理解下面这组数据：12,4,18,1,8,16,20如下图所示可以看出左边的图满足二叉树的性质，每一个它的左子节点小于它的父节点，它的右子节点大于它的父节点。同时，左子树的节点小于根节点，右子树的节点大于根节点二叉查找树的主要操作：查找（search）插入（insert）遍历（横向）二叉搜索树的链式存储结构从下图我们可以知道，二叉搜索树的节点通常包含4个域，数据元素由指向它们左右节点的指针和指向它们的指针组成父节点。这种存储结构一般称为三叉链表。用代码初始化二叉搜索树节点：指向父节点的指针parent指向左节点的指针left指向右节点的指针right数据元素，可以是键和值classBinaryTreeNode{constructor(key,value){this.parent=null;this.left=null;this.right=null;this.key=键；this.value=值；然后我们用代码初始化一棵二叉搜索树，在二叉搜索树中，我们会维护一个根指针，相当于链表中的头指针。没有插入节点时指向空，插入节点后指向根节点。classBinarySearchTree{constructor(){this.root=null;}}创建节点staticcreateNode(key,value){returnnewBinarySearchTree(key,value);}插入操作看下图，13就是我们要插入的节点，它插入的具体步骤：与根节点12比较，比12大，所以我们确定这个节点插入到右边子树并且根节点右边已经有一个节点了，然后和这个节点18比较，结果如果小于18就去18的左节点找位置，18的左节点已经有结点了，所以继续和这个结点比较，结果小于16，正好16的左结点为空（left=null），所以结点13被插入到16的左结点中。通过上面的描述，我们来看看代码是怎么写的。定义两个指针p和tail，初始指向root，p用来指向待插入位置的父节点。指针，tail是用来寻找插入位置的，所以最后会指向null。以上图为例，p指向末尾的节点6，tail指向末尾的null（如果tail为null，则表示已经找到要插入的对象插入位置）循环，tail根据上面的分析一步步找到要插入的位置，如果比当前节点小就向左查找，如果比当前节点大就向右查找，直到tail找到一个空位置,为null如果当前root为null则表示当前结构中没有节点,所以第一个插入的节点直接为根节点,即this.root=node插入的父指针node指向父节点insert(node){letp=this.root;让tail=this.root;//循环寻找对应的位置while(tail){p=tail;//要插入的节点key小于当前节点if(node.key
