这篇文章主要介绍了JavaScript数据结构和算法之二叉树详解,本文讲解了二叉树的概念、二叉树的特点、二叉树节点的定义、查找最大和最小值等内容,需要的朋友可以参考下
二叉树的概念
二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
二叉树的特点
每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点。二叉树中每一个节点都是一个对象,每一个数据节点都有三个指针,分别是指向父母、左孩子和右孩子的指针。每一个节点都是通过指针相互连接的。相连指针的关系都是父子关系。
二叉树节点的定义
二叉树节点定义如下:
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
二叉树的五种基本形态
空二叉树
只有一个根结点
根结点只有左子树
根结点只有右子树
根结点既有左子树又有右子树
拥有三个结点的普通树只有两种情况:两层或者三层。但由于二叉树要区分左右,所以就会演变成如下的五种形态:
特殊二叉树
斜树
如上面倒数第一副图的第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;
}
以上就是JavaScript数据结构和算法之二叉树详解的详细内容,更多请关注0133技术站其它相关文章!