TypeScript 玩转二叉树

悠悠 2023-01-15 09:28 160阅读 0赞

# 认识二叉树 #

## 普通树与二叉树的区别 ##

首先把普通树与二叉树（Binary Tree）区别开来。普通树能直观地反映树状结构的数据以及它们之间的关系，和我们普通认知的树那样子的差不多，例如文件夹啊、分类啊、行政管理门类啊、族谱啊之类。而二叉树，虽然也有个“树”字，但更多的是为提高排序、搜索、插入、删除速度而准备的那么一种数据结构。如果要用二叉树去展示树状结构，不是不行，它也可以从普通树转换为二叉树，但是那样的话会很别扭和不直观，不便于理解。相同的地方是，二叉树当然也是树结构里面的一种，一般研究树的方法也可以适用于二叉树，例如树的一些概念（根节点、父子节点、深度、度等等），还有搜索、遍历（前序遍历、中序遍历、后序遍历）等等。

## 二叉树特点 ##

二叉树具有以下特点。

*  最大度数为 2，就是说子节点数只能是 `0`、`1`、`2` 这三种情况之一
 *  为有序树
 *  比父节点小的放左边，小的放右边（如果相等的呢？好像是放右边）
 *  即使只有一个节点，也区分左右

如下例子。

5
       /   \
      3      6
     / \
    1   4

下面是两种特殊的二叉树。

*  满二叉树（Full Binary Tree）：所有叶子在最后一层，且度数为 2。
 *  完全二叉树（Complete Binary Tree），又称“近乎满二叉树”，所有叶子在最后一层或倒数第二层，且都是左节点。据说还有国内和国外标准之分，参见[这里][Link 1]。

## 为什么要有二叉树？ ##

没有对比就没有伤害。先看看数组结构插入元素的时间复杂度为 `O(N)`，也就是说在头部插入一个元素，那么数组里面所有的元素都要往后（往右边）移动 N 次。在头部插入是最坏的情况，开销最大。删除同理；再看看 Hash 或者 Map，插入或删除都很快，时间复杂度为 `O(1)`，但致命弱点是无序的；链表呢？解决了数组插入删除慢的缺点而且可以有序的，问题是查找挺慢的，时间复杂度为 `O(N)`。

那有没有鱼与熊掌都能兼顾的数据结构呢？有～答案就是优秀的“二叉树”。这篇[文章][Link 2]总结比较精辟，摘录如下。

>  *  数组：按序号访问元素，连续存储，元素可以有序、也可以无序，用下标来定位元素，元素的数量确定(有上限)，按下标访问很快，插入和删除元素、排序的开销比较大(元素的移位操作)，数组元素无序时，元素的排序速度比较慢(依次比较)，数组元素有序时，元素的查找速度比较慢(二分查找，比无序时快)。
>  *  链表：插入、删除方便；元素数量不受限制。非连续存储，元素可以有序、也可以无序；查找、访问元素的开销比较大：依次比较每一个元素。元素的数量不受限制。插入和删除元素、排序的开销比较小(修改指针域)。
>  *  二叉树：插入、删除方便，查找快。非连续存储，元素一定是有序(建树时判定在左子树、还是右子树上需要有依据)，查找、访问元素的开销比较小(比较次数不超过二叉树的深度)，元素的数量不受限制，插入和删除元素、排序的开销比较小(修改指针)。

> **数组、链表、二叉树各自适用的场合**
> 
>  *  数组：数据集中元素的数量基本可以确定；不需要频繁的插入、删除。
>  *  链表：需要频繁的插入、删除元素；不可预知元素的数量范围。
>  *  二叉树：需要频繁的插入、删除、查找元素。

那么代价呢？肯定有，那就是前期得花一些心智去转换为二叉树。当然还有你的学习成本啦～

# 编码 #

## 树节点和树 ##

是为 TreeNode 也。`key/value` 字段类似于 Map。  
/

**
     * 节点
     */
    class TreeNode { 
        /** * 节点索引 */
        key: number;
    
        /** * 实际的内容数据 */
        value: any;
    
        /** * 左子节点 */
        left?: TreeNode;
    
        /** * 右子节点 */
        right?: TreeNode;
    
        /** * 创建一个节点 * * @param key 节点索引 * @param value 实际的内容数据 */
        constructor(key: number, value?: any) { 
            this.key = key;
    
            if (value)
                this.value = value;
        }
    }

固然还需要一个树 `BinaryTree` 。

/** * 树 */
    class BinaryTree { 
        /** * 根节点 */
        public root: TreeNode | undefined;
        ……
    }

BinaryTree 下面 `root` 属性表示根节点，当然还有其他的操作方法，下面再讲。

## 插入节点 ##

详细请见代码和注释。树的定义本身就是递归定义，所以编码时候经常运用到递归的思想。总之树的结构与递归之间的关系非常密切，——不管是现在的插入节点方法还是后面要提到的查找、遍历等的操作方法，都能够得到充分体现密切的关系。

/** * 插入节点。 * 如果根节点为空，则插入到根节点。如果不是，插入到根节点下面 * * @param newNode * @returns */
    public insert(newNode: TreeNode): void { 
        if (!this.root) { 
            this.root = newNode;
            return;
        }
    
        this.insertNode(this.root, newNode);
    }
    
    /** * 实际的插入方法。这是一个递归的方法。 * * @param node 被插入的父节点 * @param newNode 插入的子节点 */
    private insertNode(node: TreeNode, newNode: TreeNode): void { 
        if (node.key > newNode.key) {  // 比父节点小，插入在左边
            if (node.left) { 
                this.insertNode(node.left, newNode); // 如果非空，则要再一次判断，插入到子节点下面
                return;
            }
    
            node.left = newNode;
            return;
        } else { // 比父节点大，插入在右边
            if (node.right) { 
                this.insertNode(node.right, newNode);// 如果非空，则要再一次判断，插入到子节点下面
                return;
            }
    
            node.right = newNode;
            return;
        }
    }

## 遍历 ##

二叉树一般有前序、中序以及后序三种遍历方法，它们区别如下。

*  前序遍历：父结点 —> 左子树 —> 右子树
 *  中序遍历：左子树—> 父结点 —> 右子树
 *  后序遍历：左子树 —> 右子树 —> 父结点

源码不粘贴了。测试代码如下。

// test
    let rootNode: TreeNode = new TreeNode(3, "B");
    let tree: BinaryTree = new BinaryTree();
    tree.insert(rootNode);
    tree.insert(new TreeNode(2, "B"));
    tree.insert(new TreeNode(1, "A"));
    tree.insert(new TreeNode(4, "B"));
    tree.insert(new TreeNode(5, "B"));

结果如图所示。  
![在这里插入图片描述][20210422132246649.png]  
这三种都属于树的深度遍历。另外一种广度遍历的二叉树也有，就是层次遍历了，参见[该文][Link 3]比较详细。另外也有非递归版本的。

不过有个可以改进的地方，就是加入一个 lambda 用于遍历的时候实际执行的逻辑。

## 查找 ##

这个就是二叉树惊艳的地方！查找非常快：由于大的在右边，只需要一直寻找最右边的就行了。寻找最小的也同理。

public findMax(): number { 
        return this.root ? this.findMaxNode(this.root).key : 0;
    }
    
    public findMaxNode(node: TreeNode): TreeNode { 
        if (node && node.right)
            return this.findMaxNode(node.right);
    
        return node;
    }
    
    public findMin(): number { 
        return this.root ? this.findMinNode(this.root).key : 0;
    }
    
    public findMinNode(node: TreeNode): TreeNode { 
        if (node && node.left)
            return this.findMinNode(node.left);
    
        return node;
    }

代码虽超级简单，——然而是不是深深叹服于这结构之精妙呢？

## 删除节点 ##

比较麻烦， TODO。

## 树的深度和节点总数 ##

如源码所示。

/** * 获取二叉树节点个数 * * @returns 二叉树节点个数 */
    public size(): number { 
        return this.root ? this._size(this.root) : 0;
    }
    
    /** * * @param subTree * @returns */
    private _size(subTree: TreeNode | undefined): number { 
        if (!subTree)
            return 0;
        else
            return 1 + this._size(subTree.left) + this._size(subTree.right);
    }
    
    /** * 获取二叉树层级数 * * @returns 二叉树层级数 */
    public height(): number { 
        return this.root ? this._height(this.root) : 0;
    }
    
    /** * * @param subTree * @returns */
    private _height(subTree: TreeNode | undefined): number { 
        if (!subTree)
            return 0;
        else { 
            let i = this._height(subTree.left),
                j = this._height(subTree.right);
    
            return i < j ? (j + 1) : (i + 1);
        }
    }

求深度的话有个可读性更好的版本：

public treeDepth (root: TreeNode) : number { 
    	// 一个二叉树的深度为 左子树深度和右子树深度的最大值 + 1
    	return (root === undefined || root.val === null)  ? 0 : Math.max(this.treeDepth(root.left), this.treeDepth(root.right)) + 1
    }

# 二叉树的存储 #

不太懂，TODO。

# 结语 #

二叉树还有其他待学习的地方，例如 AVL 平衡二叉树，非常重要，日后有机会再讲。

本文源码在：[https://gitee.com/sp42\_admin/ajaxjs/blob/master/aj-ts/src/data-stru/bin-tree.ts][https_gitee.com_sp42_admin_ajaxjs_blob_master_aj-ts_src_data-stru_bin-tree.ts]。

# 参考 #

*  简单易懂的二叉树实现 [https://zhuanlan.zhihu.com/p/87482994][https_zhuanlan.zhihu.com_p_87482994] 非递归版本 [https://zhuanlan.zhihu.com/p/87953541][https_zhuanlan.zhihu.com_p_87953541]
 *  很全面的二叉树实现 [https://juejin.cn/post/6844903975595016200][https_juejin.cn_post_6844903975595016200]
 *  TS 算法集锦 [https://github.com/Reaper622/DataStructure-Algorithm-TS][https_github.com_Reaper622_DataStructure-Algorithm-TS]

[Link 1]: https://blog.csdn.net/qq_44624386/article/details/104461018?utm_source=app&app_version=4.5.8
[Link 2]: https://www.cnblogs.com/zhibei/p/13371223.html
[20210422132246649.png]: /images/20221022/d1de731d97ba4a2b862bc79d0b85b5ec.png
[Link 3]: https://www.cnblogs.com/fanguangdexiaoyuer/p/10493104.html
[https_gitee.com_sp42_admin_ajaxjs_blob_master_aj-ts_src_data-stru_bin-tree.ts]: https://gitee.com/sp42_admin/ajaxjs/blob/master/aj-ts/src/data-stru/bin-tree.ts
[https_zhuanlan.zhihu.com_p_87482994]: https://zhuanlan.zhihu.com/p/87482994
[https_zhuanlan.zhihu.com_p_87953541]: https://zhuanlan.zhihu.com/p/87953541
[https_juejin.cn_post_6844903975595016200]: https://juejin.cn/post/6844903975595016200
[https_github.com_Reaper622_DataStructure-Algorithm-TS]: https://github.com/Reaper622/DataStructure-Algorithm-TS