201肆騰訊校招廣州站,分别是指向双亲、左孩子和右孩子的指针

2014騰訊校招廣州站,分别是指向父母、左孩子和右孩子的指针

  1. 关于2叉树,上面说法科学的是() 

A. 对于N个节点的二叉树,其惊人为nlog2n;

B. 2个具备10贰四个节点的二叉树,其入骨范围在1壹~1025之间

C.
2叉树的先序遍历是EFHIGJK,中序遍历为HFIEJKG,该二叉树的右子树的根为G

D. 2叉树中足足有多个节点的度为二

JavaScript数据结构和算法之2叉树详解,javascript2叉树

二叉树的概念

二叉树(Binary
Tree)是n(n>=0)个结点的有数集结,该集结或然为空集(空二叉树),也许由2个根结点和两棵互不相交的、分小名称为根结点的左子树和右子树的2叉树组成。

图片 1

贰叉树的风味

种种结点最多有两棵子树,所以二叉树中不存在度大于二的结点。二叉树中每二个节点都以贰个对象,每1个多少节点都有多个指针,分别是指向堂上、左孩子和右孩子的指针。每二个节点都以经过指针相互连接的。相连指针的关联都是父亲和儿子关系。

贰叉树节点的定义

贰叉树节点定义如下:

复制代码 代码如下:

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

二叉树的四种基本造型

空贰叉树
只有贰个根结点
根结点只有左子树
根结点唯有右子树
根结点既有左子树又有右子树

图片 2

具备多个结点的常常树唯有两种情状:两层或然三层。但鉴于2叉树要分歧左右,所以就会演变成如下的各种形态:

图片 3

诡异贰叉树

斜树

如下边尾数第二副图的第三、3小图所示。

满二叉树

在壹棵二叉树中,借使具备支行结点都留存左子树和右子树,并且具有叶子都在同壹层上,这样的二叉树称为满二叉树。如下图所示:

图片 4

一心2叉树

统统2叉树是指最终一层右侧是满的,右侧或然满也说不定不满,然后其他层都以满的。四个深度为k,节点个数为
贰^k – 1的二叉树为满2叉树(完全二叉树)。就是一棵树,深度为k,并且未有空位。

完全二叉树的风味有:

叶子结点只可以出现在最下两层。

最下层的叶子一定集中在左部一连地点。

尾数第一层,若有叶子结点,一定都在右部三番五次地点。

若果结点度为一,则该结点唯有左孩子。

平等结点树的贰叉树,完全二叉树的吃水最小。

图片 5

留神:满2叉树一定是全然2叉树,但一心二叉树不分明是满贰叉树。

算法如下:

复制代码 代码如下:

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节点,则树存在空洞,为非完全2叉树 
        if (NULL != ptr) 
        { 
            return false; 
        } 
    } 

    return true; 

二叉树的个性

二叉树的品质1:在2叉树的第i层上至多有2^(i-一)个结点(i>=一)

二叉树的质量二:深度为k的2叉树至多有2^k-二个结点(k>=壹)

二叉树的顺序存款和储蓄结构

二叉树的顺序存款和储蓄结构正是用1维数组存款和储蓄2叉树中的各类结点,并且结点的积存地方能反映结点之间的逻辑关系。

图片 6

2叉链表

既然如此顺序存款和储蓄方式的适用性不强,那么大家即将思量链式存款和储蓄结构啦。2叉树的蕴藏依照国际惯例来说一般也是使用链式存款和储蓄结构的。

贰叉树每种结点最多有三个男女,所认为它布署贰个数据域和三个指针域是比较自然的主见,我们称那样的链表叫做贰叉链表。

图片 7

二叉树的遍历

二叉树的遍历(traversing binary
tree)是指从根结点出发,依据某种次序依次走访贰叉树中负有结点,使得各样结点被访问贰回且仅被访问3次。

贰叉树的遍历有二种方法,如下:

(壹)前序遍历(DL汉兰达),首先走访根结点,然后遍历左子树,最终遍历右子树。简记根-左-右。

(二)中序遍历(LDCRUISER),首先遍历左子树,然后访问根结点,最后遍历右子树。简记左-根-右。

(3)后序遍历(L牧马人D),首先遍历左子树,然后遍历右子树,最后访问根结点。简记左-右-根。

前序遍历:

若二叉树为空,则空操作重返,不然先拜访根结点,然后前序遍历左子树,再前序遍历右子树。

遍历的次第为: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);
    }
}

中序遍历:

若树为空,则空操作重回,不然从根结点开始(注意并不是先拜访根结点),中序遍历根结点的左子树,然后是造访根结点,末了中序遍历右子树。

图片 8

遍历的次第为: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);//最后访问右子树
    }
}

后序遍历:

若树为空,则空操作重返,不然从左到右先叶子后结点的点子遍历访问左右子树,最后访问根结点。

图片 9

遍历的顺序为: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()+ ” “);
    }
}

兑现2叉查找树

二叉查找树(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://www.bkjia.com/Javascript/957147.htmlwww.bkjia.comtruehttp://www.bkjia.com/Javascript/957147.htmlTechArticleJavaScript数据结构和算法之二叉树详解,javascript二叉树
二叉树的概念 二叉树(Binary
Tree)是n(n=0)个结点的有数集结,该集结也许为空集(…

題源:2014騰訊校招廣州站

回顧

二叉樹是每個結點最多有兩個子樹的樹結構,即壹個結點可有沒有子樹,或唯有左子樹或右子樹,最簡單的二叉樹是1個結點,看似最不像2叉樹的是每個結點唯有一個子樹,雖未「二叉」,但依舊按定義爲二叉樹。滿二叉樹的具有非葉結點都有兩個子樹,第k層有二^(k-1)個結點,全樹共有2^k-一個結點(等比數列)。一心贰叉樹是從滿2叉樹倒序砍掉末尾的许多結點而得,說是完全,除了最後一層還沒有長滿,别的層已經「發育完全」,當然,未經修剪的滿二叉樹自動是完全贰叉樹。

能够用遞歸過程來說二叉數的遍歷,先序遍歷是這樣產生的:

  visit (node) {

    print node.value

    if (node.left) visit(node.left)

    if (node.right) visit (node.right)

  }

先序(或前序)即每一回訪問一個結點時先輸出其值,再去訪問左樹,等左樹訪問完,才行訪問右樹。所以當前結點是在訪問左樹和右數在此以前,故稱先序。對應地,中序在中間,後序在最後。

反觀該題,唯有C選項正確。

created with creately.com