树

树是有一个根节点和若干棵子树构成。树中结点具有相同数据类型及层次关系。

存储结构

• 双亲表示法：假设以一组连续空间存储数的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置

• 孩子表示法：把每个结点的孩子结点排列起来，以单链表作为存储结构，则 n 个结点有 n 个孩子链表，如果是叶子结点则此单链表为空。然后 n 个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。

孩子表示法可以结合双亲表示法，组合为双亲孩子表示法

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

结点结构：

data	firstchild	rightsib

树的实现

JavaScript 中没有树的数据结构，但是可以用 Object 和 Array 构建树。

const tree = {
    val: 1,
    left: {
        val: 2,
        left: {
            val: 4,
            left: null,
            right: null,
        }
    },
    right: {
        val: 3,
        left: {
            val: 6,
            left: null,
            right: null,
        },
        right: {
            val: 7,
            left: null,
            right: null,
        },
    },
};

树的常用操作：树的深度、广度遍历、先中后序遍历。

树的应用

• DOM 树
• 级联选择
• 树形控件