[date: 2019-03-01 23:42] [visits: 15]

数据结构-二叉树

树的定义

树是n个结点的有限集合,在一个非空的树中有且只有一个根结点,其余结点可分为m个互不相交的有限子集,其中每个子集又是一棵树,并且成为根节点的子树。

文字定义有点绕,但图形化很容易记住:

        |----------A----------|
        |          |          |
    |---B---|      C      |---D---|
    |       |             |   |   |
    E       F             G   H   I

树的基本概念

树的基本概念主要有以下几种:

结点的子树称为结点的孩子;相应地,该结点称为其子结点的双亲;具有相同双亲的结点互为兄弟结点;上图中,BCD是A的孩子,A是BCD的双亲,同时BCD互为兄弟结点

结点的度是指结点孩子结点的个数,A有3个孩子所以度为3,其他结点也以此类推

度为0的结点称为叶子结点,也称为终端结点,上图中CEFGHI为叶子结点

度不为0的结点称为内部结点,也称为中间结点,上图中BD为中间结点

根为第一层结点,根的孩子为第二层结点,结点的层次即为目标节点与根结点构成的路径中结点的个数

树中所有结点的最大层次即为树的高度,上图中树的高度为3

树中每个结点的孩子结点顺序不可交换为有序树,反之称为无序树

二叉树

二叉树的定义:“所有结点的孩子数不超过2的有序树”。

二叉树的种类

所有非叶子结点的孩子数均为2的二叉树即为满二叉树,若其深度为k则树的结点数为2k - 1

高度为h的二叉树,除第h层外的每一层结点数均是满的,且h层的结点不存在左兄弟结点为空的情况,符合上述条件的二叉树被称为完全二叉树

在结点中记录了某种遍历方式对应的结点线性顺序关系的二叉树

最优二叉树也称为哈夫曼树,它是一类带权路径长度最短的树,树的带权路径长度等于所有叶子结点的带权路径长度只和,带权路径长度等于权重乘以路径长度,经典应用-霍夫曼编码

二叉树的遍历

二叉树的遍历,是指按某种策略访问树中的每个结点,主要有四种方式:先序、中序、后序与按层。为了后文描述遍历算法,先对树结点做一个结构定义:

// tree node
{
    data: '',       // 结点的值
    left: null,     // 左孩子,不存在则为null
    right: null     // 右孩子,不存在则为null
}

先序遍历

先序遍历是指先访问根结点,继而先序遍历左子树再先序遍历右子树,算法代码如下:

function preOrder(root) {
    if (root === null) {
        return;
    }

    console.log(root.data);
    preOrder(root.left);
    preOrder(root.right);
}

中序遍历

中序遍历是指先中序访问左子树,继而访问根结点再中序遍历右子树,算法代码如下:

function inOrder(root) {
    if (root === null) {
        return;
    }

    inOrder(root.left);
    console.log(root.data);
    inOrder(root.right);
}

非递归方式:

function inOrderWithStack(root) {
    let stack = [];    

    let p = root;
    let q = null;

    while(p !== null || stack.length !== 0) {
        if (p !== null) {
            stack.push(p);              // 结点入栈
            p = p.left;                 
            continue;
        }

        q = stack.pop();                // 结点出栈
        console.log(q.data);
        p = q.right;
    }
}

后序遍历

后序遍历是指先后序访问左子树,继而后序访问右子树再访问根结点,算法代码如下:

function postOrder(root) {
    if (root === null) {
        return;
    }

    postOrder(root.left);
    postOrder(root.right);
    console.log(root.data);
}

按层遍历

按层遍历是指根据树的层从小到大,每一层从左向右访问各结点,刷法代码如下:

function levelOrder(root) {
    let p = null;       // 用于保存队列出来的结点
    let queue = [];

    queue.push(root);
    while((p = queue.shift())) {            // queue为空时表达式的值为undefined,即为false
        consolg.log(p.data);
        
        p.left && queue.push(p.left);       // if的一种简写
        p.right && queue.push(p.right);
    }
}

树的应用

查找二叉树

查找二叉树也称为二叉排序书,它满足以下两个条件:

查找二叉树主要作用就是可以进行快速查找,从某查找二叉树中查找值的算法如下:

function searchBST(root, key) {
    let p = root;

    while(p !== null && p.data !== key) {
        p = key < p.data ? p.left : p.right;
    }

    return p;
}

查找二叉树的插入算法与查找算法相似,如下:

function insertBST(root, key) {
    let node = treeNodeFrom(key);

    let p = root;
    let q = null;   // 指向p的双亲结点

    while(p !== null && p.data !== key) {
        q = p;
        p = key < p.data ? p.left : p.right;
    }

    if (p !== null) {
        throw new Error('duplicate key');
    }

    if (q.data > key) {
        q.left = node;
    }
    else {
        q.right = node;
    }
}

平衡二叉树

平衡树满足以下两个条件:

一颗平衡查找二叉树的查找效率会优于不平衡的查找二叉树,但是插入和删除结点可能涉及需要对树做调整使其保持平衡,这其中的操作用代码表示会比较复杂,暂时不展开。

B树

B树是一个一般化的二叉查找树,主要用在数据库和文件系统上,相信内容移步wiki