详细说明二叉树中的JavaScript数据结构和算法

二叉树的概念。

二叉树是n(n=0)个节点的有限集合，它或者是一个空集合(空二叉树)，或者是由一个根节点和两个不相交的二叉树组成，分别称为根节点的左子树和右子树。

二叉树的特征。

每个节点最多有两个子树，所以二叉树中没有度数大于2的节点。二叉树中的每个节点都是一个对象，每个数据节点都有三个指针，分别是指向父节点、左子节点和右子节点的指针。每个节点通过指针相互连接。连接指针之间的关系是父子关系。

二叉树节点的定义

二叉树节点定义如下：复制代码如下： struct二叉树节点{ int m _ nvalueBinaryTreeNode * m _ pLeftBinaryTreeNode * m _ pRight};

二叉树的五种基本形式。

一棵空的二叉树只有一个根节点，只有左边的子树根节点，只有右边的子树根节点同时拥有左边的子树和右边的子树。

有三个节点的普通树只有两种情况：两层或三层。然而，由于左右的区别，二叉树将演变成以下五种形式：

特殊二叉树

斜树

如上面倒数第二张图片的图2和图3所示。

完全二叉树

在二叉树中，如果所有的分支节点都有左子树和右子树，并且所有的叶子都在同一层，这样的二叉树称为全二叉树。如下图所示：

完全二叉树

完整的二叉树意味着最后一层的左边是满的，右边可能是满的或者不满意的，然后剩下的层都是满的。深度为k、节点数为2^k-1的二叉树是完全二叉树(完全二叉树)。这是一棵树，深度为k，没有空位。

完整的二叉树特征是：

叶节点只能出现在底部两层。

最低的叶子必须集中在左边连续的位置。

在倒数第二层，如果有叶节点，它们必须都在正确的连续位置。

如果节点度为1，则该节点只剩下子节点。

对于同节点树的二叉树，完全二叉树的深度最小。

注意：完全二叉树一定是完全二叉树，但完全二叉树不一定是完全二叉树。

算法如下：

复制代码如下： boulis _ complete(tree * root){ queueq；树* ptr//执行广度优先遍历(层次遍历)，将空节点放入队列q.push(根)；while ((ptr=q.pop())！=NULL){ q . push(ptr-left)；q . push(ptr-right)；}

//判断while(！q . is _ empty()){ ptr=q . pop()；

//如果有未被访问的非空节点，则树为空，如果(NULL！=ptr){ return false；} }

返回真；}

二叉树的性质。

二叉树的第一个性质是二叉树的第I层最多有2个(I-1)节点(i=1)。

二叉树的第二个性质：深度为k的二叉树最多有2 k-1个节点(k=1)。

二叉树的顺序存储结构。

二叉树的顺序存储结构是用一维数组将每个节点存储在二叉树中，节点的存储位置可以反映节点之间的逻辑关系。

二进制链表

由于顺序存储的适用性不强，所以要考虑链式存储结构。根据国际惯例，二叉树通常存储在链式存储结构中。

二叉树的每个节点最多有两个子节点，因此为其设计一个数据字段和两个指针字段是一个很自然的想法。我们称这个链表为二进制链表。

二叉树遍历。

遍历二叉树是指从根节点开始，依次按一定的顺序访问二叉树中的所有节点，这样每个节点都被访问一次，并且只被访问一次。

遍历二叉树有三种方法，如下所示：

(1)序言遍历(DLR)，首先访问根节点，然后遍历左子树，最后遍历右子树。记住根-左-右。

(2)中间顺序遍历(LDR)，先遍历左子树，再访问根节点，最后遍历右子树。简，记住左-根-右。

(3)后序遍历(LRD)，先遍历左子树，再遍历右子树，最后访问根节点。简记得左-右-根。

前言遍历：

如果二叉树为空，则返回null操作；否则，先访问根节点，然后依次遍历左子树，再依次遍历右子树。

遍历顺序为：A B D H I E J C F K G复制代码如下：//第一个遍历函数preOrder(node){ if(！node==null){ put str(node . show()' ')；preOrder(node . left)；preOrder(node . right)；}}

顺序遍历：

如果树为空，则返回null操作；否则，从根节点开始(注意先不访问根节点)，按照中间顺序遍历根节点的左子树，然后访问根节点，最后按照中间顺序遍历右子树。

遍历顺序为：H . D . I . B . E . J . A F K . C . G复制代码如下：//使用递归方法实现中序遍历函数inoder(node){ if(！(node==null)){ Inorder(node . left)；//首先访问左边的子树put str(node . show()' ')；//再次访问根节点Inorder(node . right)；//最后访问右边的子树}}

顺序遍历：

如果树为空，则返回null操作；否则，从左到右遍历左右子树，最后访问根节点。

遍历顺序为：H I D J E B K F G C A复制代码如下：//遍历函数postOrder(节点){ if(！node==null){ PostOrder(node . left)；posterorder(node . right)；putStr(node . show()' ')；}}

实施二叉查找树。

二叉查找树(BST)是由nodes组成的，所以我们定义一个Node对象如下：Copy code代码如下： Function Node(数据，左，右){this。数据=数据；this.left=left//保存左节点链接this.right=rightthis.show=show}

函数show(){ return this . data；//显示保存在节点中的数据}

找出最大值和最小值。

在BST上求最小值和最大值非常简单，因为较小的值总是在左边的子节点上。在BST上求最小值只需要遍历左边的子树，直到找到最后一个节点。

查找最小复制代码如下： function getmin(){ var current=this . root；while(！(current . left==null)){ current=current . left；}返回current.data}该方法沿着BST的左子树逐一遍历，直到到达BST最左边的节点，定义为：复制代码如下：current.left=null此时，保存在当前节点上的值是最小值。

求最大值。

在BST上寻找最大值只需要遍历右子树，直到找到最后一个节点，存储在这个节点上的值就是最大值。复制的代码如下：函数getmax(){ var current=this . root；while(！(current . right==null)){ current=current . right；}返回current.data}