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; 
}

二叉树的性质

二叉树的性质一:在二叉树的第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;
}

时间: 2015-02-09

Javascript数据结构与算法之列表详解

前言:在日常生活中,人们经常要使用列表,比如我们有时候要去购物时,为了购物时东西要买全,我们可以在去之前,列下要买的东西,这就要用的列表了,或者我们小时候上学那段时间,每次考完试后,学校都会列出这次考试成绩前十名的同学的排名及成绩单,等等这些都是列表的列子.我们计算机内也在使用列表,那么列表适合使用在什么地方呢?不适合使用在什么地方呢? 适合使用在:当列表的元素不是很多的情况下,可以使用列表,因为对列表中的元素查找或者排序时,效率还算非常高,反之:如果列表元素非常多的情况下,就不适合使用列表了.

JavaScript数据结构学习之数组、栈与队列

前言 数据结构就是关系,没错,就是数据元素相互之间存在的一种或多种特定关系的集合. 常用的数据结构有: 数组,队列(queue),堆(heap),栈(stack),链表(linked list ),树(tree),图(graph)和散列表(hash) 本文主要介绍的是数组.栈与队列,下面来一起看看详细的介绍吧. 一.数组 数组是平时使用最常用的数据结构,在JavaScript中数组是动态的分配大小,在这里我不会介绍JavaScript里面数组的所有的方法,而是针对数据结构这个方向谈谈所用到的方法

JavaScript数据结构与算法之栈与队列

学习起因 曾经有一次在逛V2EX时,碰到这么一个帖子. 数学完全还给老师了,想学回一些基础数学,大概是高中程度的,有什么书籍推荐? 发帖的楼主大学没有高数课程,出去工作时一直在从事前端的工作.感觉到数学知识的匮乏,所以想补一补数学. 看了看帖子,感觉和我很像,因为我的专业是不开高数的,我学的也是前端.也同样感觉到了数学知识匮乏所带来的困顿.同时因为自己的数学思维实在是不怎么好,所以决定努力补习数学与计算机基础知识. 当时也有人说:"前端需要什么数据结构与算法",但是对于这个事情我有自己

JavaScript队列的应用实例详解【经典数据结构】

本文实例讲述了JavaScript队列的应用.分享给大家供大家参考,具体如下: 和前面介绍的栈相反,队列是一种先进先出的线性表,它只允许在表的一端进行插入,而在另一端进行删除.JavaScript自己提供了两个队列方法shift和push方法,分别是出队和入队,其原理就是将元素插入数组最后一个和删除第一个元素. 这里需要注意一点,就是unshift方法的效率比push的效率要低很多.因为它要将入队之前的数组全部往前移动一位.这里我们就不用代码再次演示了. 和线性表类似,队列也分为顺序队列和链队列

JavaScript数据结构之链表的实现

前面楼主分别讨论了数据结构栈与队列的实现,当时所用的数据结构都是用的数组来进行实现,但是数组有的时候并不是最佳的数据结构,比如在数组中新增删除元素的时候需要将其他元素进行移动,而在javascript中使用spit()方法不需要访问其他元素.如果你在使用数组的时候发现很慢,就可以考虑使用链表. 链表的概念 链表是一种常见的数据结构.它是动态地进行存储分配的一种结构.链表有一个"头指针"变量,以head表示,它存放一个地址,指向一个元素.每个结点都使用一个对象的引用指标它的后继,指向另一

JavaScript队列、优先队列与循环队列

队列是一种遵从先进先出(FIFO)原则的有序集合 队列在尾部添加新元素,从顶部移除元素 队列的理解 队列在我们生活中最常见的场景就是排队了 队列这个名字也已经很通俗易懂了 和栈很像,这不过队列是先入先出的数据结构 队列的前面是队头 队列的后面是队尾 出队从队头出 入队从队尾入 队列的创建 和栈类似,这里我就不就不啰嗦了 同样需要实现一些功能 这里我类比生活中的排队上厕所 向队列中添加元素(进入排队的队伍中) 移除队头元素(队伍最前面的人出队进入厕所) 查看队头元素(查看队伍最前面的人) 判断队列

javascript中利用数组实现的循环队列代码

//循环队列 function CircleQueue(size){ this.initQueue(size); } CircleQueue.prototype = { //初始化队列 initQueue : function(size){ this.size = size; this.list = new Array(); this.capacity = size + 1; this.head = 0; this.tail = 0; }, //压入队列 enterQueue : functio

JS实现队列与堆栈的方法

本文实例讲述了JS实现队列与堆栈的方法.分享给大家供大家参考,具体如下: 在面向对象的程序设计里,一般都提供了实现队列(queue)和堆栈(stack)的方法,而对于JS来说,我们可以实现数组的相关操作,来实现队列和堆栈的功能,看下面的相关介绍. 一.看一下它们的性质,这种性质决定了它们的使用场合 队列:是一种支持先进先出(FIFO)的集合,即先被插入的数据,先被取出! 堆栈:是一种支持后进先出(LIFO)的集合,即后被插入的数据,先被取出! 二.看一下实现的代码(JS代码) var a=new

JavaScript数据结构之优先队列与循环队列实例详解

本文实例讲述了JavaScript数据结构之优先队列与循环队列.分享给大家供大家参考,具体如下: 优先队列 实现一个优先队列:设置优先级,然后在正确的位置添加元素. 我们这里实现的是最小优先队列,优先级的值小(优先级高)的元素被放置在队列前面. //创建一个类来表示优先队列 function Priorityqueue(){ var items=[];//保存队列里的元素 function QueueEle(e,p){//元素节点,有两个属性 this.element=e;//值 this.pr

JS实现队列的先进先出功能示例

本文实例讲述了JS实现队列的先进先出功能.分享给大家供大家参考,具体如下: /** * [Queue] * @param {[Int]} size [队列大小] */ function Queue(size) { var list = []; //向队列中添加数据 this.push = function(data) { if (data==null) { return false; } //如果传递了size参数就设置了队列的大小 if (size != null && !isNaN(s

JavaScript数组的栈方法与队列方法详解

数组(Array)和对象(Object)应该是JavaScript中使用最多也是最频繁的两种类型了,Array提供了很多常用的方法:栈方法.队列方法.重排序方法.操作方法.位置方法.迭代方法等等. 1.Array的栈方法 栈是一种LIFO(Last-In-First-Out,后进先出)的数据结构,也就是最新添加的项最早被移除.栈中项的插入(push)和移除,只发生在一个位置--栈的顶部.ECMAScript为数组提供了push()和pop()方法,可以实现类似栈的行为.下面两图分别演示了入栈与出

JAVA基于静态数组实现栈的基本原理与用法详解

本文实例讲述了JAVA基于静态数组实现栈.分享给大家供大家参考,具体如下: 1.栈的定义 栈是一种"先进后出"的一种线性数据结构,有压栈出栈两种操作方式.如下图: 2.栈的分类 栈主要分为两类: 静态栈 动态栈 [静态栈] 静态栈的核心是数组,类似于一个连续内存的数组,我们只能操作其栈顶元素. [动态栈] 静态栈的核心是数组,类似于一个连续内存的数组,我们只能操作其栈顶节点. 此节我们在我们之前封装的动态数组的基础上(引用封装好的动态数组),实现基本的栈操作. 3.栈实现 1.先定义一

javascript数组遍历for与for in区别详解

js中遍历数组的有两种方式 复制代码 代码如下: var array=['a'] //标准的for循环 for(var i=1;i<array.length;i++){     alert(array[i]) } //foreach循环 for(var i in array){     alert(array[i]) } 正常情况下上面两种遍历数组的方式结果一样.首先说两者的第一个区别 标准的for循环中的i是number类型,表示的是数组的下标,但是foreach循环中的i表示的是数组的key

JavaScript数组实现数据结构中的队列与堆栈

一.队列和堆栈的简单介绍 1.1.队列的基本概念 队列:是一种支持先进先出(FIFO)的集合,即先被插入的数据,先被取出! 如下图所示: 1.2.堆栈的基本概念 堆栈:是一种支持后进先出(LIFO)的集合,即后被插入的数据,先被取出! 如下图所示: 二. 在JavaScript中实现队列和堆栈 在JavaScript中实现队列和数组主要是通过数组,js数组中提供了以下几个方法可以让我们很方便实现队列和堆栈: •shift:从数组中把第一个元素删除,并返回这个元素的值. •unshift: 在数组

类似Object监视器方法的Condition接口(详解)

在<基于线程.并发的基本概念(详解)>中,我们利用synchronized关键字.Queue队列.以及Object监视器方法实现了生产者消费者,介绍了有关线程的一些基本概念.Object类提供的wait的方法和notifyAll方法,与之对应的是Condition接口提供是await和signalAll.await(或wait)是让当前线程进入等待状态并释放锁,signalAll(或notifyAll)则是唤醒等待中的线程,使得等待中的线程有竞争锁的资格,注意只是资格,并不代表被唤醒的线程就一

Android Canvas方法总结最全面详解API(小结)

本篇文章主要介绍了Android Canvas方法总结最全面详解API,分享给大家,具体如下: 常用方法 drawXxx方法族:以一定的坐标值在当前画图区域画图,另外图层会叠加, 即后面绘画的图层会覆盖前面绘画的图层. clipXXX方法族:在当前的画图区域裁剪(clip)出一个新的画图区域,这个 画图区域就是canvas对象的当前画图区域了.比如:clipRect(new Rect()), 那么该矩形区域就是canvas的当前画图区域 getXxx方法族:获得与Canvas相关一些值,比如宽高

使用AngularJS编写多选按钮选中时触发指定方法的指令代码详解

最近在做项目时,遇到了需要用到多选按钮选中触发事件的功能,因此我查找了一下AngularJS的提供的指令,但是没有发现相应的指令.而一个看起来很像的指令就是ng-checked,但是这个指令是用来代替标签里面checked属性的,所以也用不了.因此我就自己动手试着写一个这样的指令,相应的代码如下: <form name="test_form" ng-controller="TestCtrl"> <input type="checkbox&

python类:class创建、数据方法属性及访问控制详解

在Python中,可以通过class关键字定义自己的类,然后通过自定义的类对象类创建实例对象. python中创建类 创建一个Student的类,并且实现了这个类的初始化函数"__init__": class Student(object):     count = 0     books = []     def __init__(self, name):         self.name = name 接下来就通过上面的Student类来看看Python中类的相关内容. 类构造和

servlet配置方法及其生命周期详解

servlet配置: 在web.xml中,首先向服务器注册一个servlet.在<servlet>标签下 给定一个servlet名字,这个servlet-name是我们自己用的,方便我们用它对servlet进行配置. 1 <servlet-name>AServlet</servlet-name>然后指定一个全类名,这个是给服务器使用,服务器用来创建全类名对象的实例 1 <servlet-class>com.servlet.AServlet</servl