js数据结构和算法（三）二叉树

DesGemini 发布于2019-08-21 10:20 / 1278人阅读

摘要：同样结点树的二叉树，完全二叉树的深度最小。二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。

二叉树的概念

二叉树（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;  
}

二叉树的性质

二叉树的性质一：在二叉树的第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）由节点组成，所以我们定义一个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;
}

二叉树相关题目：http://blog.csdn.net/luckyxiaoqiang/article/details/7518888

GPU云服务器云服务器二叉树算法最优二叉树算法图 JS二叉树遍历 js怎么建二叉树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/85346.html

数据结构与算法:二叉树算法

摘要：因此，根据题目给出的先序遍历和中序遍历，可以画出二叉树选参考数据结构与算法描述实现二叉树算法浅谈数据结构二叉树慕课网实现二叉树算法前端树控件腾讯软件开发面试题内容衔接上一章数据结构与算法:常见排序算法内容提要什么是树　　- 为什么使用树二叉树二叉查找树红黑树Ｂ、Ｂ＋树堆伸展树树可以点击链接感受下笔者用d3.js画的tree https://codepen...

Little_XM 2019-08-22 11:09 评论0 收藏0
JS中的二叉树遍历

摘要：一个二叉树的例子广度优先遍历广度优先遍历是从二叉树的第一层根结点开始，自上至下逐层遍历在同一层中，按照从左到右的顺序对结点逐一访问。有的书里将二叉树的遍历只讲了上面三种递归遍历。二叉树是由根节点，左子树，右子树组成，左子树和友子树分别是一个二叉树。这篇文章主要在JS中实现二叉树的遍历。一个二叉树的例子 var tree = { value: 1, left: { ...

ghnor 2019-08-19 17:52 评论0 收藏0
JS二叉树非递归遍历

摘要：一个二叉树的例子先实现三种遍历的递归算法以作比较。先序遍历递归算法中序遍历递归算法先遍历到最左边的节点，然后输出后序遍历看完上面的递归遍历，下面对比一下非递归的二叉树遍历。终止条件最后树遍历完了自然就结束后序遍历二叉树的递归遍历很简单就可以实现，二叉树非递归遍历却想不出来？那你可以看看下面的例子。一个二叉树的例子 var root = { val: 1, left: { val...

guyan0319 2019-08-21 16:20 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0