JavaScript数据结构与算法：二叉树详解与实现

二叉树基础概念与形态

二叉树的概念

二叉树（Binary Tree）是由n（n≥0）个节点组成的有限集合。该集合要么为空集（称为空二叉树），要么由一个根节点和两棵互不相交的二叉树构成，这两棵子树分别被称为根节点的左子树和右子树。

二叉树的特点

每个节点最多拥有两棵子树，因此二叉树中不存在度大于2的节点。在二叉树中，每个节点作为一个对象，包含三个指针域，分别指向其父节点、左孩子节点和右孩子节点。所有节点通过指针相互连接，形成的关系均为父子关系。

二叉树节点的定义

二叉树节点的定义如下所示：

struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};

二叉树的五种基本形态

1. 空二叉树 2. 只有一个根节点 3. 根节点只有左子树 4. 根节点只有右子树 5. 根节点既有左子树又有右子树

拥有三个节点的普通树仅存在两种结构：两层或三层。但由于二叉树严格区分左右子树，因此演变为上述五种基本形态。

特殊二叉树

斜树

参考前述图示中倒数第一幅图的第2和第3小图所示情况。

满二叉树

若一棵二叉树中所有分支节点均同时存在左子树和右子树，且所有叶子节点都位于同一层上，则该二叉树称为满二叉树。具体结构如下图所示：

完全二叉树

完全二叉树是指最后一层左侧节点已满，右侧可能满也可能不满，而其余各层均为满二叉树。若一棵深度为k且节点总数为 2^k - 1 的二叉树，则称为满二叉树（也是完全二叉树的一种）。即深度为k且没有任何空位的树。

完全二叉树具有以下特点：

叶子节点只能出现在最下面两层。

最下层的叶子节点一定集中在左侧连续位置。

倒数第二层若存在叶子节点，则一定都在右侧连续位置。

如果节点的度为1，则该节点只有左孩子。

在节点数量相同的二叉树中，完全二叉树的深度最小。

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

判定完全二叉树的算法如下：

bool is_complete(tree *root)
{  
queue q;
tree *ptr;
// 进行广度优先遍历（层次遍历），并将NULL节点也加入队列
q.push(root);
while ((ptr = q.pop()) != NULL)
    {  
q.push(ptr->left);
q.push(ptr->right);
    } 
// 判断队列中是否还有未被访问到的节点 
 while (!q.is_empty()) 
 { 
 ptr = q.pop();
// 若存在未被访问到的非NULL节点，说明树中存在空洞，判定为非完全二叉树 
 if (NULL != ptr) 
 { 
 return false; 
 } 
 }
return true; 
}

二叉树性质与存储结构

二叉树的性质

性质一：在二叉树的第i层上，至多有 2^(i-1) 个节点（i≥1）。

性质二：深度为k的二叉树，至多有 2^k - 1 个节点（k≥1）。

二叉树的顺序存储结构

二叉树的顺序存储结构使用一维数组来存储二叉树中的各个节点，并通过节点在数组中的存储位置来体现节点之间的逻辑关系。

二叉链表

鉴于顺序存储方式的适用性有限，我们通常考虑链式存储结构。按照国际惯例，二叉树的存储一般采用链式存储结构。

由于二叉树每个节点最多有两个孩子，因此为其设计一个数据域和两个指针域是自然的选择，这种链表被称为二叉链表。

二叉树遍历算法实现

二叉树的遍历

二叉树的遍历（traversing binary tree）是指从根节点出发，按照特定次序依次访问二叉树中的所有节点，确保每个节点被访问一次且仅被访问一次。

二叉树的遍历主要有以下三种方式：

（1）前序遍历（DLR）：首先访问根节点，然后遍历左子树，最后遍历右子树。简记为：根-左-右。

（2）中序遍历（LDR）：首先遍历左子树，然后访问根节点，最后遍历右子树。简记为：左-根-右。

（3）后序遍历（LRD）：首先遍历左子树，然后遍历右子树，最后访问根节点。简记为：左-右-根。

前序遍历：

若二叉树为空，则执行空操作返回；否则先访问根节点，接着前序遍历左子树，最后前序遍历右子树。

遍历顺序示例：A B D H I E J C F K G

//先序遍历
function preOrder(node){
if(!node == null){
putstr(node.show()+ " ");
preOrder(node.left);
preOrder(node.right);
    }
}

中序遍历：

若树为空，则执行空操作返回；否则从根节点开始（注意并非先访问根节点），中序遍历根节点的左子树，接着访问根节点，最后中序遍历右子树。

遍历顺序示例：H D I B E J A F K C G

//使用递归方式实现中序遍历
function inOrder(node){
if(!(node == null)){
inOrder(node.left);//先访问左子树
putstr(node.show()+ " ");//再访问根节点
inOrder(node.right);//最后访问右子树
    }
}

后序遍历：

若树为空，则执行空操作返回；否则按照从左到右先叶子后节点的顺序遍历访问左右子树，最后访问根节点。

遍历顺序示例：H I D J E B K F G C A

//后序遍历
function postOrder(node){
if(!node == null){
postOrder(node.left);
postOrder(node.right);
putStr(node.show()+ " ");
    }
}

二叉查找树（BST）构建与查询

实现二叉查找树

二叉查找树（BST）由节点组成，因此我们需要定义一个Node节点对象，具体定义如下：

function Node(data,left,right){
this.data = data;
this.left = left;//保存left节点链接
this.right = right;
this.show = show;
}
function show(){
 return this.data;//显示保存在节点中的数据
}

查找最大和最小值

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

查找最小值

function getMin(){
var current = this.root;
while(!(current.left == null)){
current = current.left;
    }
return current.data;
}

该方法沿着BST的左子树逐个遍历，直到到达BST最左侧的节点，该节点被定义为：

current.left = null;

此时，当前节点上保存的值即为最小值。

查找最大值

在BST上查找最大值只需遍历右子树，直到找到最后一个节点，该节点上保存的值即为最大值。

function getMax(){
var current = this.root;
while(!(current.right == null)){
current = current.right;
    }
return current.data;
}