独家是指向老人、左孩子和右孩子的指针,二〇一五騰訊校招廣州站

  1. 有关二叉树,下边说法科学的是() 

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

B. 二个怀有102陆个节点的二叉树,其惊人范围在11~1025之间

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

D. 二叉树中最少有叁个节点的度为2

JavaScript数据结构和算法之二叉树详解,javascript二叉树

二叉树的定义

二叉树(Binary
Tree)是n(n>=0)个结点的点滴集合,该集合大概为空集(空二叉树),只怕由2个根结点和两棵互不相交的、分小名叫根结点的左子树和右子树的二叉树组成。

图片 1

二叉树的特色

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

二叉树节点的概念

二叉树节点定义如下:

复制代码 代码如下:

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

二叉树的四种基本造型

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

图片 2

不无四个结点的平凡树只有三种情景:两层依然三层。但由于二叉树要分别左右,所以就会演变成如下的八种形象:

图片 3

特殊二叉树

斜树

如上面倒数第壹副图的第3、3小图所示。

满二叉树

在一棵二叉树中,假如拥有支行结点都设有左子树和右子树,并且有所叶子都在同等层上,那样的二叉树称为满二叉树。如下图所示:

图片 4

完全二叉树

一齐二叉树是指最终一层右边是满的,右侧恐怕满也说不定不满,然后别的层都以满的。一个深度为k,节点个数为
2^k – 1
的二叉树为满二叉树(完全二叉树)。正是一棵树,深度为k,并且没有空位。

完全二叉树的特色有:

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

最下层的纸牌一定集中在左部三番五次地方。

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

一旦结点度为1,则该结点唯有左孩子。

同一结点树的二叉树,完全二叉树的吃水最小。

图片 5

小心:满二叉树一定是一点一滴二叉树,但完全二叉树不自然是满二叉树。

算法如下:

复制代码 代码如下:

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-3个结点(k>=1)

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

二叉树的顺序存款和储蓄结构便是用一维数组存款和储蓄二叉树中的各样结点,并且结点的仓库储存地点能反映结点之间的逻辑关系。

图片 6

二叉链表

既然顺序存款和储蓄格局的适用性不强,那么大家即将考虑链式存储结构啦。二叉树的囤积依照国际惯例来说一般也是运用链式存款和储蓄结构的。

二叉树每一个结点最多有五个孩子,所以为它安排一个数据域和三个指针域是比较自然的想法,大家称这样的链表叫做二叉链表。

图片 7

二叉树的遍历

二叉树的遍历(traversing binary
tree)是指从根结点出发,遵照某种次序依次走访二叉树中全数结点,使得各类结点被访问一回且仅被访问一遍。

二叉树的遍历有三种格局,如下:

(1)前序遍历(DLRAV4),首先访问根结点,然后遍历左子树,末了遍历右子树。简记根-左-右。

(2)中序遍历(LD宝马X5),首先遍历左子树,然后访问根结点,最后遍历右子树。简记左-根-右。

(3)后序遍历(L福特ExplorerD),首先遍历左子树,然后遍历右子树,最终访问根结点。简记左-右-根。

前序遍历:

若二叉树为空,则空操作再次回到,不然先走访根结点,然后前序遍历左子树,再前序遍历右子树。

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

兑现二叉查找树

二叉查找树(BST)由节点组成,所以大家定义1个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)个结点的蝇头集合,该集合可能为空集(…

題源:二〇一四騰訊校招廣州站

回顧

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

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

  visit (node) {

    print node.value

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

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

  }

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

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

created with creately.com

相关文章