重启数据结构与算法9 #29

Ray-56 · 2020-07-08T03:27:00Z

重启数据结构与算法9

重启数据结构与算法，一些代码案例使用 Deno 与 TypeScript 实现，相关代码都在这里

树的基础部分

在计算机科学中，树（英语：tree）是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的

为什么需要树这种数据结构

1、数组存储方式的分析

在内存中连续存放

优点：取值效率高
缺点：增加元素效率低，因为要移动大量的元素。删除同理

2、链式存储方式的分析

通过指针联系在一起

优点：增加元素与删除元素效率高一点，只需要找到指定位置将指针修改即可
缺点：取值也需要遍历链表，效率低

3、树型存储方式的分析

以二叉树为例，同时具备数组取值的高效率还具有链式存储的增删效率

应用场景：常见业务需求像决策树、目录树、索引树、甚至简单的流程树都可以用二叉树来实现。

常用术语

节点的度：一个节点含有的子树的个数称为该节点的度；
树的度：一棵树中，最大的节点度称为树的度；
叶节点或终端节点：度为零的节点；
非终端节点或分支节点：度不为零的节点；
父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
兄弟节点：具有相同父节点的节点互称为兄弟节点；
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；
高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；
堂兄弟节点：父节点在同一层的节点互为堂兄弟；
节点的祖先：从根到该节点所经分支上的所有节点；
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
森林：由m（m>=0）棵互不相交的树的集合称为森林

二叉树的概念

在计算机科学中，二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。

满二叉树

一棵深度为k，且有{\displaystyle 2^{\begin{aligned}k\end{aligned}}-1} $2^{\begin{aligned}k\end{aligned}}-1$ 个节点的二叉树，称为满二叉树（Full Binary Tree）。这种树的特点是每一层上的节点数都是最大节点数。

完全二叉树

在一颗二叉树中，若除最后一层外的其余层都是满的，并且最后一层要么是满的，要么在右边缺少连续若干节点，则此二叉树为完全二叉树（Complete Binary Tree）。具有n个节点的完全二叉树的深度为{\displaystyle log_{2}n+1}。深度为k的完全二叉树，至少有{\displaystyle 2^{\begin{aligned}k-1\end{aligned}}} $2^{\begin{aligned}k-1\end{aligned}}$ 个节点，至多有{\displaystyle 2^{\begin{aligned}k\end{aligned}}-1} $2^{\begin{aligned}k\end{aligned}}-1$ 个节点。

前中后序遍历二叉树

前序遍历：父 -> 左（递归）-> 右（递归）
中序遍历：左（递归）-> 父 -> 右（递归）
后序遍历：左（递归）-> 右（递归）-> 父

从上面找规律，找到父的输出位置，就可以知道是哪种方式遍历

class HeroNode {
    public no: number;
    public name: string;
    public left: HeroNode | null = null;
    public right: HeroNode | null = null;
    constructor(no: number, name: string) {
        this.no = no;
        this.name = name;
    }
    public toString(): string {
        return `no = ${this.no}, name = ${this.name} `;
    }
    /** 前序 */
    public preOrder() {
        console.log(this.toString()); // 父
        // left 不为 null 递归执行
        this.left?.preOrder();
        // right 不为 null 递归执行
        this.right?.preOrder();
    }
    /** 中序 */
    public infixOrder() {
        this.left?.infixOrder();
        console.log(this.toString());
        this.right?.infixOrder();
    }
    /** 后序 */
    public postOrder() {
        this.left?.postOrder();
        this.right?.postOrder();
        console.log(this.toString());
    }
}

class BinaryTree {
    public root: HeroNode | null = null;
    public preOrder() {
        this.root?.preOrder();
    }
    public infixOrder() {
        this.root?.infixOrder();
    }
    public postOrder() {
        this.root?.postOrder();
    }
}

window.onload = function main() {
    const root = new HeroNode(1, '宋江');
    const node2 = new HeroNode(2, '卢俊义');
    const node3 = new HeroNode(3, '吴用');
    const node4 = new HeroNode(4, '公孙胜');
    const node5 = new HeroNode(5, '关胜');

    // 这里先使用手动创建树
    root.left = node2;
    root.right = node3;
    node3.left = node5;
    node3.right = node4;

    const binaryTree = new BinaryTree();
    binaryTree.root = root;
    binaryTree.preOrder(); // 1, 2, 3, 5, 4
    binaryTree.infixOrder(); // 2, 1, 5, 3, 4
    binaryTree.postOrder(); // 2, 5, 4, 3, 1
}

前中后序查找二叉树

二叉树查找的思路与遍历一致，只是多了判断是否一致并且返回

class HeroNode {
    public no: number;
    public name: string;
    public left: HeroNode | null = null;
    public right: HeroNode | null = null;
    constructor(no: number, name: string) {
        this.no = no;
        this.name = name;
    }
    public toString(): string {
        return `no = ${this.no}, name = ${this.name} `;
    }
    /** 前序 */
    public preOrder() {
        console.log(this.toString()); // 父
        // left 不为 null 递归执行
        this.left?.preOrder();
        // right 不为 null 递归执行
        this.right?.preOrder();
    }
    /** 中序 */
    public infixOrder() {
        this.left?.infixOrder();
        console.log(this.toString());
        this.right?.infixOrder();
    }
    /** 后序 */
    public postOrder() {
        this.left?.postOrder();
        this.right?.postOrder();
        console.log(this.toString());
    }
    /** 前序搜索 */
    public preOrderSearch(no: number): HeroNode | null {
        // 对比当前，正确直接返回
        if (this.no === no) return this;
        let ret: HeroNode | null = null;
        // 如果 left 不为 null，递归遍历，赋值结果 ret
        if (this.left) {
            ret = this.left?.preOrderSearch(no);
        }
        // 结果 ret 不为 null，说明找到，直接返回 ret
        if (ret) return ret;
        // 如果 right 不为 null，递归遍历，赋值结果 ret
        if (this.right) {
            ret = this.right?.preOrderSearch(no);
        }
        // 将结果返回
        return ret;
    }
    infixOrderSearch(no: number): HeroNode | null {
        let ret: HeroNode | null = null;
        if (this.left) {
            ret = this.left.infixOrderSearch(no);
        }
        if (ret) return ret;
        if (this.no === no) return this;
        if (this.right) {
            ret = this.right.infixOrderSearch(no);
        }
        return ret;
    }
    postOrderSearch(no: number): HeroNode | null {
        let ret: HeroNode | null = null;
        if (this.left) {
            ret = this.left.infixOrderSearch(no);
        }
        if (ret) return ret;
        if (this.right) {
            ret = this.right.infixOrderSearch(no);
        }
        if (ret) return ret;
        if (this.no === no) return this;
        return ret;
    }
}

class BinaryTree {
    public root: HeroNode | null = null;
    public preOrder() {
        this.root?.preOrder();
    }
    public infixOrder() {
        this.root?.infixOrder();
    }
    public postOrder() {
        this.root?.postOrder();
    }
    public preOrderSearch(no: number): HeroNode | null {
        if (!this.root) return null;
        return this.root.preOrderSearch(no);
    }
    public infixOrderSearch(no: number): HeroNode | null {
        if (!this.root) return null;
        return this.root.infixOrderSearch(no);
    }
    public postOrderSearch(no: number): HeroNode | null {
        if (!this.root) return null;
        return this.root.postOrderSearch(no);
    }
}

window.onload = function main() {
    const root = new HeroNode(1, '宋江');
    const node2 = new HeroNode(2, '卢俊义');
    const node3 = new HeroNode(3, '吴用');
    const node4 = new HeroNode(4, '公孙胜');
    const node5 = new HeroNode(5, '关胜');

    // 这里先使用手动创建树
    root.left = node2;
    root.right = node3;
    node3.left = node5;
    node3.right = node4;

    const binaryTree = new BinaryTree();
    binaryTree.root = root;
    binaryTree.preOrder(); // 1, 2, 3, 5, 4
    // binaryTree.infixOrder(); // 2, 1, 5, 3, 4
    // binaryTree.postOrder(); // 2, 5, 4, 3, 1

    console.log(binaryTree.postOrderSearch(5)?.toString()); // no = 5, name = 关胜
}

二叉树的删除

我们规定

如果节点是叶子节点，删除节点
如果不是，删除子树

// HeroNode
public delNode(no: number) {
    if (this.left?.no === no) {
        this.left = null;
        return;
    }
    if (this.right?.no === no) {
        this.right = null;
        return;
    }
    this.left?.delNode(no);
    this.right?.delNode(no);
}

// BinaryTree
public delNode(no: number): void {
    if (this.root === null) {
        console.log(`当前树为空树`);
        return;
    }
    if (this.root.no === no) {
        this.root = null;
        return;
    }
    this.root.delNode(no);
}

顺序存储二叉树

二叉树可以用数组或链接串列来存储，若是满二叉树就能紧凑排列而不浪费空间。

如果某个节点的索引为 n，假设根节点为 0 的情况下：

左子节点的索引为2 * n + 1
右子节点的索引为2 * n + 2
父节点的索引为(n - 1) / 2

class ArrBinaryTree {
    private arr: number[];
    constructor(arr: number[]) {
        this.arr = arr;
    }
    /**
     * 先序遍历
     * @param index arr的下标
     */
    proOrder(index: number = 0) {
        if (this.arr?.length === 0) {
            console.log('数组为空');
            return;
        }
        console.log(`${this.arr[index]}`);
        // 左递归遍历
        if ((index * 2 + 1) < this.arr.length) {
            this.proOrder(index * 2 + 1);
        }
        // 右递归遍历
        if ((index * 2 + 2 < this.arr.length)) {
            this.proOrder(index * 2 + 2);
        }
    }
    /**
     * 中序遍历
     * @param index
     */
    infixOrder(index: number = 0) {
        if (this.arr?.length === 0) {
            console.log('数组为空');
            return;
        }
        // 左递归遍历
        if ((index * 2 + 1) < this.arr.length) {
            this.infixOrder(index * 2 + 1);
        }
        console.log(`${this.arr[index]}`);
        // 右递归遍历
        if ((index * 2 + 2 < this.arr.length)) {
            this.infixOrder(index * 2 + 2);
        }
    }
    /**
     * 后序遍历
     * @param index
     */
    postOrder(index: number = 0) {
        if (this.arr?.length === 0) {
            console.log('数组为空');
            return;
        }
        // 左递归遍历
        if ((index * 2 + 1) < this.arr.length) {
            this.postOrder(index * 2 + 1);
        }
        // 右递归遍历
        if ((index * 2 + 2 < this.arr.length)) {
            this.postOrder(index * 2 + 2);
        }
        console.log(`${this.arr[index]}`);
    }
}

window.onload = function main() {
    const arrBinaryTree = new ArrBinaryTree([1, 2, 3, 4, 5, 6, 7]);
    // arrBinaryTree.proOrder(); // 1, 2, 4, 5, 3, 6, 7
    // arrBinaryTree.infixOrder(); // 4, 2, 5, 1, 6, 3, 7
    arrBinaryTree.postOrder(); // 4, 5, 2, 6, 7, 3, 1
}

线索化二叉树

在计算机科学中，二叉树添加了直接指向节点的前驱和后继的指针的二叉树称为线索二叉树。

一个二叉树通过如下的方法“穿起来”：所有原本为空的右(孩子)指针改为指向该节点在中序序列中的后继，所有原本为空的左(孩子)指针改为指向该节点的中序序列的前驱。

class HeroNode {
    public no: number;
    public name: string;
    public left: HeroNode | null = null;
    public right: HeroNode | null = null;
    /** 左节点类型，0：子树，1：前驱 */
    public leftType: 0 | 1 = 0;
    /** 右节点类型，0：子树，1：后继 */
    public rightType: 0 | 1 = 0;
    constructor(no: number, name: string) {
        this.no = no;
        this.name = name;
    }
    public toString(): string {
        return `no = ${this.no}, name = ${this.name} `;
    }
    /** 前序 */
    public preOrder() {
        console.log(this.toString()); // 父
        // left 不为 null 递归执行
        this.left?.preOrder();
        // right 不为 null 递归执行
        this.right?.preOrder();
    }
    /** 中序 */
    public infixOrder() {
        this.left?.infixOrder();
        console.log(this.toString());
        this.right?.infixOrder();
    }
    /** 后序 */
    public postOrder() {
        this.left?.postOrder();
        this.right?.postOrder();
        console.log(this.toString());
    }
    /** 前序搜索 */
    public preOrderSearch(no: number): HeroNode | null {
        // 对比当前，正确直接返回
        if (this.no === no) return this;
        let ret: HeroNode | null = null;
        // 如果 left 不为 null，递归遍历，赋值结果 ret
        if (this.left) {
            ret = this.left?.preOrderSearch(no);
        }
        // 结果 ret 不为 null，说明找到，直接返回 ret
        if (ret) return ret;
        // 如果 right 不为 null，递归遍历，赋值结果 ret
        if (this.right) {
            ret = this.right?.preOrderSearch(no);
        }
        // 将结果返回
        return ret;
    }
    infixOrderSearch(no: number): HeroNode | null {
        let ret: HeroNode | null = null;
        if (this.left) {
            ret = this.left.infixOrderSearch(no);
        }
        if (ret) return ret;
        if (this.no === no) return this;
        if (this.right) {
            ret = this.right.infixOrderSearch(no);
        }
        return ret;
    }
    postOrderSearch(no: number): HeroNode | null {
        let ret: HeroNode | null = null;
        if (this.left) {
            ret = this.left.infixOrderSearch(no);
        }
        if (ret) return ret;
        if (this.right) {
            ret = this.right.infixOrderSearch(no);
        }
        if (ret) return ret;
        if (this.no === no) return this;
        return ret;
    }
    public delNode(no: number) {
        if (this.left?.no === no) {
            this.left = null;
            return;
        }
        if (this.right?.no === no) {
            this.right = null;
            return;
        }
        this.left?.delNode(no);
        this.right?.delNode(no);
    }
}

class ThreadedBinaryTree {
    public root: HeroNode | null = null;
    public pre: HeroNode | null = null;
    public preOrder() {
        this.root?.preOrder();
    }
    public infixOrder() {
        this.root?.infixOrder();
    }
    public postOrder() {
        this.root?.postOrder();
    }
    public preOrderSearch(no: number): HeroNode | null {
        if (!this.root) return null;
        return this.root.preOrderSearch(no);
    }
    public infixOrderSearch(no: number): HeroNode | null {
        if (!this.root) return null;
        return this.root.infixOrderSearch(no);
    }
    public postOrderSearch(no: number): HeroNode | null {
        if (!this.root) return null;
        return this.root.postOrderSearch(no);
    }
    public delNode(no: number): void {
        if (this.root === null) {
            console.log(`当前树为空树`);
            return;
        }
        if (this.root.no === no) {
            this.root = null;
            return;
        }
        this.root.delNode(no);
    }
    /** 中序线索化二叉树 */
    public threadedNodes(node: HeroNode | null) {
        if (node === null) return;
        // 中序遍历的顺序为 左 =》当前 =》右
        // 1. 左递归
        this.threadedNodes(node.left);

        // 2. 当前
        // 2.1. 当前前驱
        if (node.left === null) {
            node.left = this.pre;
            node.leftType = 1;
        }
        // 2.2. 当前后继
        if (this.pre !== null && this.pre.right === null) {
            this.pre.right = node;
            this.pre.rightType = 1;
        }

        // 记录上一个值
        this.pre = node;

        // 3. 右递归
        this.threadedNodes(node.right);
    }
}

window.onload = function main() {
    const root = new HeroNode(1, 'aa');
    const node2 = new HeroNode(3, 'bb');
    const node3 = new HeroNode(6, 'cc');
    const node4 = new HeroNode(8, 'dd');
    const node5 = new HeroNode(10, 'ee');
    const node6 = new HeroNode(14, 'ff');

    // 这里先使用手动创建树
    root.left = node2;
    root.right = node3;
    node2.left = node4;
    node2.right = node5;
    node3.left = node6;

    const tree = new ThreadedBinaryTree();
    tree.root = root;
    tree.threadedNodes(root);
    console.log(node5.left?.toString()); // 3
    console.log(node5.right?.toString()); // 1
};

在原来二叉树的代码中加了一些代码

class HeroNode {
    ...
    /** 左节点类型，0：子树，1：前驱 */
    public leftType: 0 | 1 = 0;
    /** 右节点类型，0：子树，1：后继 */
    public rightType: 0 | 1 = 0;
    ...
}
class ThreadedBinaryTree {
    ...
    /** 记录上一个节点值 */
    public pre: HeroNode | null = null;
    ...
    /** 中序线索化二叉树 */
    public threadedNodes(node: HeroNode | null) {
        if (node === null) return;
        // 中序遍历的顺序为 左 =》当前 =》右
        // 1. 左递归
        this.threadedNodes(node.left);

        // 2. 当前
        // 2.1. 当前前驱
        if (node.left === null) {
            node.left = this.pre;
            node.leftType = 1;
        }
        // 2.2. 当前后继
        if (this.pre !== null && this.pre.right === null) {
            this.pre.right = node;
            this.pre.rightType = 1;
        }

        // 记录上一个值
        this.pre = node;

        // 3. 右递归
        this.threadedNodes(node.right);
    }
}

遍历线索化二叉树

ThreadedBinaryTree 中加入方法

    ...
    /** 中序遍历线索化二叉树 */
    public threadedList() {
        let node = this.root;
        while (node !== null) {
            // 找最左最底
            while (node!.leftType === 0) {
                node = node!.left;
            }
            console.log(node?.toString());
            // 往右边找
            while (node!.rightType === 1) {
                node = node!.right;
                console.log(node?.toString());
            }
            node = node!.right;
        }
    }

线索化二叉树的实用场景（堆排序）

这里也是前面八大排序中遗留的地方，当时没有讲到二叉树所以先搁置，现在补齐

需要注意的点:

升序使用大顶堆
降序使用小顶堆
不会去创建二叉树，只是对数组类型使用线索化二叉树的概念
左子节点2*n+1
右子节点2*n+2
整个顺序为左->右，底->上

思路：

构建大顶堆
依次将最大值沉底（顶底交换）
由于交换后大顶堆变化，重新构建大顶堆

function heapSort(arr: number[]) {
    for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
        adjustHeap(arr, i, arr.length);
    }
    // 依次将大值沉底
    for (let j = arr.length - 1; j > 0; j--) {
        const temp = arr[j];
        arr[j] = arr[0];
        arr[0] = temp;
        adjustHeap(arr, 0, j);
    }
}
function adjustHeap(arr: number[], index: number, len: number) {
    let temp = arr[index];
    for (let k = index * 2 + 1; k < len; k = k * 2 + 1) {
        // 判断左子节点与右子节点
        if (k + 1 < len && arr[k] < arr[k + 1]) {
            k++;
        }
        // 子节点大于父节点，不满足大顶堆条件，交换
        if (arr[k] > temp) {
            arr[index] = arr[k];
            index = k;
        } else {
            break;
        }
    }
    arr[index] = temp; // 交换赋值
}

window.onload = function main() {
    const arr = [4, 6, 8, 5, 9];
    // 测试构建大顶堆
    // adjustHeap(arr, 1, arr.length);
    // adjustHeap(arr, 0, arr.length);
    // console.log(arr); // [ 9, 6, 8, 5, 4 ]
    heapSort(arr);
    console.log(arr); // [ 4, 5, 6, 8, 9 ]
}

下期预告

赫夫曼树

The text was updated successfully, but these errors were encountered:

Ray-56 added the 数据结构与算法 label Jul 8, 2020

This was referenced Sep 16, 2020

重启数据结构与算法10 #33

Open

重启数据结构与算法11 #34

Open

重启数据结构与算法12 #35

Open

重启数据结构与算法 #36

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

重启数据结构与算法9 #29

重启数据结构与算法9 #29

Ray-56 commented Jul 8, 2020

重启数据结构与算法9 #29

重启数据结构与算法9 #29

Comments

Ray-56 commented Jul 8, 2020

重启数据结构与算法9

树的基础部分

为什么需要树这种数据结构

1、数组存储方式的分析

2、链式存储方式的分析

3、树型存储方式的分析

常用术语

二叉树的概念

满二叉树

完全二叉树

前中后序遍历二叉树

前中后序查找二叉树

二叉树的删除

顺序存储二叉树

线索化二叉树

遍历线索化二叉树

线索化二叉树的实用场景（堆排序）

下期预告