树

作者: yuzhiyi_宇 | 来源:发表于2019-01-19 18:34 被阅读0次

树(Tree)是 n >=0 个结点的有限集。n=0 时称为空树。在任意一颗非空树中：有且仅有一个特定的称为根(Root)的结点，当n>1时，其余结点可以为m(m>0)个互不相交的有限集，其中每一个集合本身又是一棵数，并且称为树的子树(SubTree)。

结点分类

树的结点包含一个数据元素及若干指向其子树的分支。
结点拥有的子树数称为结点的度(Degree)。度为 0 的结点称为叶结点(Leaf)或终端结点；度不为 0 的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。
数的度是数内结点的度的最大值。

结点间关系

结点的子树的根称为该结点的孩子(Child)，相应地，该结点称为孩子的双亲(Parent)。
同一个双亲的孩子之间互为兄弟。
结点的祖先是从根到该结点所经分支上的所有结点。
以某结点为根的子数中的任一结点都被称为该结点的子孙。

树的其他相关概念

结点的层次(Level)从根开始定义起，根为第一层，根的孩子为第二层。
双亲在同一层的结点互为堂兄弟。
树中结点的最大层次称为树的深度(Depth)或高度。
如果将树中结点的各子数看成从左至右是有次序的，不能互换的，则称为该树为有序树，否则称为无序树。
森林(Forest)是 m (m>=0) 棵互不相干的树的集合。

树的存储结构

双亲表示法

在每个结点中，附设一个指示器指示其双亲结点在数组中的位置。
结点结构如下。

data	parent

data 是数据域，parent 是指针域，存储该结点的双亲在数组的下标。

class PTNode {
    constructor(data, parent) {
        this.data = data; // 结点位置
        this.parent = parent; // 双亲位置
    }
}

class PTree {
    constructor() {
        this.nodes = []; // 结点数组
        this.n = 0; // 结点数
        this.r = 0; // 根的位置
    }
}

存储结构是否合适，是否方便，时间复杂度好不好，都可以拿来判断一个存储结构是否合理。

孩子表示法

每个结点有多个指针域，每个指针指向一颗子树的根节点，叫做多重链表表示法。

1. 指针域的个数等于树的度

data	child1	child 2	....	child n

data 是数据域，child1 到 childn 是指针域，用来指向该结点的孩子结点。
对于树中各结点的度相差很大时，很浪费空间。

2. 每个结点指针域的个数等于该结点的度

data	degree	child1	child 2	....	child n

data 是数据域，degree 是度域，child1 到 childn 是指针域，用来指向该结点的孩子结点。
克服了空间的浪费，由于各结点的链表是不同的结构，加上要维护的结点的度的数值，在运算上会带来时间上的损耗。

3. 孩子表示法
把每个结点的孩子结点排列起来，以单链表作存储结构，则 n 个结点有 n 个孩子链表，如果是叶子结点则此单链表为空。

孩子链表的孩子结点。

child	next

child 是数据域，用来存储某个结点在表头数组中的下标。next 是指针域，用来存储指向某结点的下个孩子结点的指针。

表头数组的表头结点。

data	firstchild

data 是数据域，存储某结点的数据信息。firstchild 是头指针域，存储该结点的孩子链表的头指针。

class CTNode {
    constructor(child, next) {
        this.child = child;
        this.next = next;
    }
}

class CTBox {
    constructor(data, firstchild) {
        this.data = data;
        this.firstchild = firstchild;
    }
}

class CTree {
    constructor() {
        this.nodes = []; // 结点数组
        this.n = 0; // 结点数
        this.r = 0; // 根的位置
    }
}

孩子兄弟表示法

任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的有兄弟如果存在也是唯一的。设置两个指针，分别指向该结点的第一个孩子和该结点的右兄弟。

data	firstchild	rightsib

data 是数据域，firstchild 为指针域，存储该结点的第一个孩子结点的存储地址，rightsib 是指针域，存储该结点的右兄弟结点的存储地址。

class CSNode {
    constructor(data, firstchild, rightsib) {
        this.data = data;
        this.firstchild = firstchild;
        this.rightsib = rightsib;
    }
}

好处是它把一颗复杂的树变成二叉树。

二叉树

二叉树(Binary Tree) 是 n(n >= 0) 个结点的有限结合，该集合或者为空集(空二叉树)，或者由一个根结点和两棵互不相交的，分别称为根结点的左子树和右子树的二叉树组成。

二叉树特点

二叉树热点

每个结点最多有两棵子树，所以二叉树不存在度大于 2 的结点。
左子树和右子树是有顺序的，次序不能任意颠倒。
即使树中某个结点只有一颗子树，也要区分是左子树还是右子树。

二叉树五种基本形态

空二叉树。
只有一个根结点。
根结点只有左子树。
根结点只有右子树。
根结点既有左子树又有右子树。

特殊二叉树

1. 斜树
所有的结点都只有左子树的二叉树称为左斜树。所有结点都是只有右子树的二叉树称为右斜树。统称为斜树。

2. 满二叉树
一颗二叉树中，所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，称为满二叉树。
满二叉树热点：
(1) 叶子只能出现在最下一层。
(2) 非叶子结点的度一定是 2 。
(3) 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

完全二叉树
对一颗具有 n 个结点的二叉树按层序编号，如果编号为 i (1 <= i <=n) 的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。
完全二叉树特点：
(1) 叶子结点只能出现在最下两层。
(2) 最下层的叶子一定集中在左部连续位置。
(3) 倒数两层，若有叶子结点，一定都在右部连续位置。
(4) 如果结点度为 1，则该结点只有左孩子，不存在只有右子树的情况。
(5) 同样结点数的二叉树，完全二叉树的深度最小。

二叉树的性质

在二叉树的第 i 层上至多有 2 ^ (i - 1) 个结点(i >= 1)。
深度为 k 的二叉树至多有 2 ^ k -1 个结点。
对任何一颗二叉树 T ，如果其终端结点数为 n0，度为 2 的结点数为 n2，则 n0 = n2 + 1。
具有 n 个结点的完全二叉树的深度为 [log₂n] + 1。
如果对一棵有 n 个结点的完全二叉树的结点按层序编号，对任一结点 i (1 <= i <= n)有

如果 i = 1，则结点 i 是二叉树的根，无双亲；如果 i > 1，则其双亲是结点 [i / 2]。
如果 2i > n，则结点 i 无左孩子(结点 i 为叶子结点)；否则其左孩子是结点 2i。
如果 2i+1>n，则结点 i 无右孩子；否则其右孩子是结点 2i+1。

二叉树的存储结构

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，数据下边要能体现结点之间的逻辑关系。
顺序存储结构一般只用于完全二叉树。

二叉链表

一个数据域和两个指针域，称为二叉链表。

lchild	data	rchild

data 是数据域，lchild 和 rchild 都是指针域，分别存储指向左孩子和右孩子的指针。

class BiTNode {
    constructor(data, lchild, rchild) {
        this.data = data;
        this.lchild = lchild;
        this.rchild = rchild;
    }
}

遍历二叉树

二叉树的遍历(traversing binart tree) 是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅访问一次。

二叉树遍历方法

1. 前序遍历
规则是若二叉树是空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。

class BiTNode {
    constructor(data, lchild, rchild) {
        this.data = data;
        this.lchild = lchild;
        this.rchild = rchild;
    }
}

function preOrderTraverse(t) {
    if (t === null) {
        return;
    }
    console.log(t.data);
    preOrderTraverse(t.lchild);
    preOrderTraverse(t.rchild);
}

2. 中序遍历
规则是若二叉树是空，则空操作返回，否则从根结点开始，中序遍历根节点的左子树，然后是访问根结点，最后中旬访问右子树。

class BiTNode {
    constructor(data, lchild, rchild) {
        this.data = data;
        this.lchild = lchild;
        this.rchild = rchild;
    }
}

function inOrderTraverse(t) {
    if (t === null) {
        return;
    }
    inOrderTraverse(t.lchild);
    console.log(t.data);
    inOrderTraverse(t.rchild);
}

3. 后续遍历
规则是若二叉树是空，则空操作返回，否则就从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。

class BiTNode {
    constructor(data, lchild, rchild) {
        this.data = data;
        this.lchild = lchild;
        this.rchild = rchild;
    }
}

function postOrderTraverse(t) {
    if (t === null) {
        return;
    }
    postOrderTraverse(t.lchild);
    postOrderTraverse(t.rchild);
    console.log(t.data);
}

4. 层序遍历
规则是若树为空，则空操作返回，否则从树的第一层，也就是根节点开始访问，从上至下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

推导遍历结果

已知前序遍历和中序遍历序列，可以唯一确定一棵二叉树。
已知后序遍历和中序遍历序列，可以唯一确定一棵二叉树。
已知前序和后续遍历，不能确定一棵二叉树。

线索二叉树

指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树(Threaded Binary Tree)。
对二叉树以某种次序遍历使其变成线索二叉树的过程称做是线索化。

lchild	ltag	data	rtag	rchild

ltag 为 0 时指向该结点的左孩子，为 1 时指向该结点的前驱。
rtag 为 0 时指向该结点的右孩子，为 1 时指向该结点的后驱。

class BiThrTNode {
    constructor(data, lchild, ltag, rchild, rchild) {
        this.data = data;
        this.lchild = lchild;
        this.ltag = ltag;
        this.rchild = rchild;
    }
}

如果采用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构是不错的选择。

树、森林与二叉树的装换

树转换为二叉树

加线。在所有兄弟结点之间加一条连线。
去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。
层次分明。以树的根结点为轴心，将整颗树顺时针旋转一定的角度，使之结构层次分明。

森林转换为二叉树

把每个树转换成二叉树。
第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根节点的右孩子，用线连接。

二叉树转换为树

二叉树转换为树是树转换成二叉树的逆过程。

加线。若某结点的左孩子结点存在，则将这个左孩子的右孩子结点，右孩子的右孩子结点，右孩子的右孩子的右孩子结点....都做为该结点的孩子。将该结点与这些右孩子结点用线连接起来。
去线。删除原二叉树中所有结点与其右孩子结点的连线。
层次调整。使之结构层次分明。

二叉树转换为森林

判断一棵二叉树能否转换成森林，看根节点是否有右孩子。

从根结点开始，若右孩子存在，则把与右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除...，直到所有右孩子连线都删除为止，得到分离的二叉树。
再将每棵分离后的二叉树转换为树即可。

树与森林的遍历

树的遍历

一种是先根遍历树，即先访问树的根节点，然后一次先遍历根的每棵子树。
另一种是后根遍历，即先依次后跟遍历每棵子树，然后再访问根结点。

森林的遍历

前序遍历：先访问森林中第一棵树的根节点，然后再一次先遍历根的每棵子树，再一次用同样的方式遍历除去第一棵树的剩余树构成的森林。
后序遍历：是先访问森林中第一棵树，后根遍历的方式遍历每颗子树，然后再访问根结点，再一次同样方式遍历除去第一棵树的剩余树构成的森林。

哈弗曼树定义与遍历

从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做路径长度。
树的路劲长度就是从树根到每个结点的路径长度之和。
带权路径长度 WPL 最小的二叉树称做哈弗曼树。

构造哈弗曼树步骤。

根据给定的 n 个权值 {w₁，w₂,...w_n}构成 n 棵二叉树的集合 F={T₁,T₂,...T_n}，其中每棵二叉树 T_i 中只有一个带权为 w_i 根结点，其左右子树均为空。
在 F 中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左右子树上根结点的权值之和。
在 F 中删除这两棵树，同时将新得到的二叉树加入 F 中。
重复 2 和 3 步骤，直到 F 只含一棵树为止。

哈弗曼编码

若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称做前缀编码。
设需要编码的字符集 {d₁，d₂,...d_n}，各个字符在电文中出现的次数或频率集合为 {w₁，w₂,...w_n}，以d₁，d₂,...d_n作为叶子结点，以 w₁，w₂,...w_n 作为相应叶子结点的权值来构造一棵哈弗曼树。规定哈弗曼树的左分支代表 0，右分支代表 1，则从根节点到叶子结点所经过的路径分支组成的 0 和 1 的序列便为该结点对应字符的编码，这就是哈弗曼编码。

树