likes
comments
collection
share

【基础数据结构】树结构 Tree(TS版)

作者站长头像
站长
· 阅读数 16

1. 认识树结构

什么是树?

在真实生活中的树:

  1. 通常有一个,连着的是树干
  2. 树干到上面之后会进行分叉成树枝树枝还会分叉成更小的树枝
  3. 树枝的最后是叶子

【基础数据结构】树结构 Tree(TS版)

数据结构中的树正是由真实生活中的树抽象而来,一个模拟树结构的例子

【基础数据结构】树结构 Tree(TS版)

在上图中,我们可以把

  1. 总经理看成是树干
  2. 每一个部门看成树枝
  3. 部门下更小的部门可以看成树叶

总结:

树是一种分层数据的抽象模型,js 中没有树,但是我们可以用 Object 来构建树

2. 树结构的优点和术语

在说树结构的优点时,我们先来回顾一下之前将的 数组/链表/哈希表 这几种数据结构

结构优点缺点
数组根据下标访问值效率很高1. 查找效率低,需要对数组进行排序生成有序数组,才能提高查找效率。2. 另外,插入和删除数据时,需要有大量的位移操作,效率很低
链表插入和删除效率很高1. 查找效率低,需要从头开始一次访问链表中的每个数据项,直到找到。2. 如果插入和删除中间位置的数据,还是需要重头先找到对应的数据
哈希表插入、查询、删除效率都是非常高的1. 空间利用率不高,底层使用的是数组,并且某些单元是没有被利用的。2. 哈希表中元素是无序的,不能按照固定的顺序来遍历哈希表中的元素。3. 不能快速找出哈希表的最大值或者最小值这些特殊值

树结构:

  1. 我们不能说树结构比其他结构都要好,因为每种数据结构都有自己特定的应用场景
  2. 但是树确实也综合了上面的数据结构的优点(当然优点不足以盖过其他数据结构,比如效率一般情况下没有哈希表高)
  3. 并且也弥补了上面数据结构的缺点

树的术语:

  1. 节点的度(Degree:节点的子树个数.
  2. 树的度(Degree:树的所有节点中最大的度数. (树的度通常为节点的个数 N-1)
  3. 叶节点(Leaf:度为 0 的节点. (也称为叶子节点)
  4. 父节点(Parent:有子树的节点是其子树的根节点的父节点
  5. 子节点(Child:若 A 节点是 B 节点的父节点,则称 B 节点是 A 节点的子节点;子节点也称孩子节点。
  6. 兄弟节点(Sibling:具有同一父节点的各节点彼此是兄弟节点。
  7. 路径和路径长度:从节点 n1nk 的路径为一个节点序列 n1 , n2,… , nk, nini+1 的父节点。路径所包含边的个数为路径的长度。
  8. 节点的层次(Level):规定根节点在 1 层,其它任一节点的层数是其父节点的层数加1。
  9. 树的深度(Depth):树中所有节点中的最大层次是这棵树的深度。

3. 认识二叉树

如果树中的每个节点最多只能有两个子节点,这样的树就称为二叉树

二叉树的定义:

  1. 二叉树可以为空,也就是没有节点
  2. 不为空,则它是由根节点和称为其 左子树(Left Tree)右子树(Right Tree) 的两个不相交的二叉树组成

二叉树几个比较重要的特性:

  1. 一颗二叉树第 i 层的最大节点数为:2^(i-1), i >= 1;
  2. 深度为 k 的二叉树有最大节点总数为: 2^k - 1, k >= 1;
  3. 对任何非空二叉树 T,若 n0 表示叶节点(度为 0 的节点)的个数、n2 是度为 2 的非叶节点个数,那么两者满足关系 n0 = n2 + 1

特殊的二叉树

  1. 完美二叉树(Perfect Binary Tree) , 也称为满二叉树(Full Binary Tree

    • 在二叉树中, 除了最下一层的叶结点外, 每层节点都有 2 个子节点, 就构成了满二叉树.

【基础数据结构】树结构 Tree(TS版)

  1. 完全二叉树(Complete Binary Tree)

    1. 二叉树最后一层外, 其他各层的节点数都达到最大个数.
    2. 最后一层从左向右的叶节点连续存在, 只缺右侧若干节点.
    3. 完美二叉树特殊的完全二叉树.

下面不是完全二叉树, 因为 D 节点还没有节点, 但是 E 节点就有了左右节点.

【基础数据结构】树结构 Tree(TS版)

4. 二叉树常见存储方式

二叉树的存储常见的方式是数组链表

4.1 使用数组的方式

完全二叉树:从上至下,从左到右顺序存储 【基础数据结构】树结构 Tree(TS版)

非完全二叉树:要转换成完全二叉树才可以按照上面的方案存储,而且会造成很大的空间浪费 【基础数据结构】树结构 Tree(TS版)

4.2 使用链表的方式:

二叉树最常见的方式还是使用链表存储(我们之后的封装也会基于链表):每个节点封装成一个 NodeNode包含存储的数据,左节点的引用,右节点的引用

【基础数据结构】树结构 Tree(TS版)

5. 认识二叉搜索树

二叉搜索树(BST,Binary Search Tree),也称为二叉排序树二叉查找树

二叉搜索树是一棵二叉树,可以为空:

如果不为空,需要满足一下性质:

  1. 非空左子树的所有键值小于其根节点的键值
  2. 非空右子树的所有键值大于其根节点的键值
  3. 左右子树本身也都是二叉搜索树

【基础数据结构】树结构 Tree(TS版)

二叉搜索树的特点:

  1. 相对较小的值总是保存在左节点上,相对较大的值总是保存在右节点
  2. 查找效率非常高,这也是二叉搜索树中,搜索的来源

6. 二叉搜索树的封装

一个二叉搜索树的常见操作应该包含以下:

  • 插入操作:
    1. insert(value): 向树中插入一个新的数据
  • 查找操作
    1. search(value):在树中查找一个数据,如果节点存在,则返回 true;如果不存在,则返回 false
    2. min:返回树中最小的值
    3. max:返回树中最大的值
  • 遍历操作:
    1. inOrderTraverse:通过中序遍历方式遍历所有节点
    2. preOrderTraverse:通过先序遍历方式遍历所有节点
    3. postOrderTraverse:通过后序遍历方式遍历所有节点
    4. levelOrderTraverse:通过层序遍历方式遍历所有节点
  • 删除操作
    1. remove(value):从树中移除某个数据

6.1 基础架构 v1 版本

class TreeNode<T> {
  value: T;
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;

  constructor(value: T) {
    this.value = value;
  }
}

class BSTree<T> {
  root: TreeNode<T> | null = null;
}

代码解析:

  1. 封装一个用于保存每一个节点的类 TreeNode
  2. TreeNode 类包含三个属性
    1. value: 节点对应的值
    2. left: 指向左边的子树
    3. right:指向右边的子树
  3. 封装 BSTree 类作为一棵树
  4. 对于 BSTree 来说,只需要保存根节点即可,因为其他节点都可以通过根节点找到。

结构示意图:

【基础数据结构】树结构 Tree(TS版)

6.2 添加 insert 方法 v2 版

BSTree 中添加 insert 方法

insert(value) 的作用为向一棵二叉树插入数据

  insert(value: T) {
    // 1. 根据传入 value 创建 TreeNode 节点
    const newNode = new TreeNode(value);

    // 2. 判断当前是否已经有了根节点
    if (!this.root) {
      // 当前树为空
      this.root = newNode;
    } else {
      // 树中已经有其他值
      this.insertNode(this.root, newNode);
    }
  }

  private insertNode(node: TreeNode<T>, newNode: TreeNode<T>) {
    if (newNode.value < node.value) {
      // 去左边查找空白位置
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else {
      // 去右边查找空白位置
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }

测试:

const bst = new BSTree<number>();

bst.insert(20);
bst.insert(30);
bst.insert(18);
bst.insert(14)
bst.insert(12)
bst.insert(19)
bst.insert(22)

树的结构:

               20
        ┌───────┴───────┐
       18              30
    ┌───┴───┐       ┌───┘
   14      19      22
  ┌─┘
 12

6.3 添加 preOrderTraverse 方法 v3 版

BSTree 中添加 preOrderTraverse 方法

preOrderTraverse 方法的作用是先序遍历一个树

树的先序遍历的过程:

  1. 优先访问根节点
  2. 之后访问左子树
  3. 最后访问右子树
  preOrderTraverse() {
    this.preOrderTraverseNode(this.root);
  }

  private preOrderTraverseNode(node: TreeNode<T> | null) {
    if (node) {
      console.log(node.value);
      this.preOrderTraverseNode(node.left);
      this.preOrderTraverseNode(node.right);
    }
  }

测试:

const bst = new BSTree<number>();

bst.insert(20);
bst.insert(30);
bst.insert(18);
bst.insert(14);
bst.insert(12);
bst.insert(19);
bst.insert(22);

bst.preOrderTraverse();

树的结构:

               20
        ┌───────┴───────┐
       18              30
    ┌───┴───┐       ┌───┘
   14      19      22
  ┌─┘
 12

打印结果:

20
18
14
12
19
30
22

6.4. 添加 inOrderTraverse 方法 v4 版

BSTree 中添加 inOrderTraverse 方法

inOrderTraverse 方法的作用是中序遍历一个树

树的中序遍历的过程:

  1. 优先访问左子树
  2. 之后访问根节点
  3. 最后访问右子树
  inOrderTraverse() {
    this.inOrderTraverseNode(this.root);
  }

  private inOrderTraverseNode(node: TreeNode<T> | null) {
    if (node) {
      this.inOrderTraverseNode(node.left);
      console.log(node.value);
      this.inOrderTraverseNode(node.right);
    }
  }

测试:

const bst = new BSTree<number>();

bst.insert(20);
bst.insert(30);
bst.insert(18);
bst.insert(14);
bst.insert(12);
bst.insert(19);
bst.insert(22);

bst.inOrderTraverse();

树的结构:

               20
        ┌───────┴───────┐
       18              30
    ┌───┴───┐       ┌───┘
   14      19      22
  ┌─┘
 12

打印结果:

12
14
18
19
20
22
30

6.5. 添加 postOrderTraverse 方法 v5 版

BSTree 中添加 postOrderTraverse 方法

postOrderTraverse 方法的作用是后序遍历一个树

树的后序遍历的过程:

  1. 优先访问左子树
  2. 之后访问右子树
  3. 最后访问根节点
  postOrderTraverse() {
    this.postOrderTraverseNode(this.root);
  }

  private postOrderTraverseNode(node: TreeNode<T> | null) {
    if (node) {
      this.postOrderTraverseNode(node.left);
      this.postOrderTraverseNode(node.right);
      console.log(node.value);
    }
  }

测试:

const bst = new BSTree<number>();

bst.insert(20);
bst.insert(30);
bst.insert(18);
bst.insert(14);
bst.insert(12);
bst.insert(19);
bst.insert(22);

bst.postOrderTraverse();

树的结构:

               20
        ┌───────┴───────┐
       18              30
    ┌───┴───┐       ┌───┘
   14      19      22
  ┌─┘
 12

打印结果:

12
14
19
18
22
30
20

6.6. 添加 levelOrderTraverse 方法 v6 版

BSTree 中添加 levelOrderTraverse 方法

levelOrderTraverse 方法的作用是层序遍历一个树

层序遍历的过程:

  1. 从上向向下逐层遍历
  2. 层序遍历通常会借助队列来完成
  levelOrderTraverse() {
    // 1. 如果没有根节点,那么不需要遍历
    if (!this.root) return;

    // 2. 创建队列结构
    const queue: TreeNode<T>[] = [];

    // 第一个节点是根节点
    queue.push(this.root);

    // 3. 遍历队列中所有的节点(依次出队)
    while (queue.length) {
      // 3.1 访问节点的过程
      const current = queue.shift()!;
      console.log(current.value);

      // 3.2 将左子节点放入到队列
      if (current.left) {
        queue.push(current.left);
      }

      // 3.3 将右子节点放入到队列
      if (current.right) {
        queue.push(current.right);
      }
    }
  }

测试:

const bst = new BSTree<number>();

bst.insert(20);
bst.insert(30);
bst.insert(18);
bst.insert(14);
bst.insert(12);
bst.insert(19);
bst.insert(22);

bst.levelOrderTraverse();

树的结构:

               20
        ┌───────┴───────┐
       18              30
    ┌───┴───┐       ┌───┘
   14      19      22
  ┌─┘
 12

打印结果:

20
18
30
14
19
22
12

6.7 添加 getMaxValue 方法 v7 版

BSTree 中添加 getMaxValue 方法

getMaxValue 方法的作用是获取树中的最大值

  getMaxValue(): T | null {
    let current = this.root;
    while (current && current.right) {
      current = current.right;
    }

    return current?.value ?? null;
  }

6.8 添加 getMinValue 方法 v8 版

BSTree 中添加 getMinValue 方法

getMinValue 方法的作用是获取树中的最小值

  getMinValue(): T | null {
    let current = this.root;
    while (current && current.left) {
      current = current.left;
    }

    return current?.value ?? null;
  }

6.9 添加 search 方法 v9 版

BSTree 中添加 search 方法

search 方法的作用:在树中查找一个数据,如果节点存在,则返回 true;如果不存在,则返回 false

  search(value: T): boolean {
    let current = this.root;
    while (current) {
      // 找到了节点
      if (current.value === value) return true;

      if (current.value < value) {
        current = current.right;
      } else {
        current = current.left;
      }
    }

    return false;
  }

6.10 添加 remove 方法 v10 版

BSTree 中添加 remove 方法

remove 方法的作用:删除某个数据

remove 的逻辑比较复杂,我们大致可以分为以下四种情况:

  1. 要删除的的节点是叶子结点(没有子节点)
  2. 要删除的的节点只有一个左子节点
  3. 要删除的的节点只有一个右子节点
  4. 要删除的的节点有两个节点
  remove(value: T): boolean {
   // 1. 获取要删除的节点 current 和 其父节点 parent
   let current = this.root;
   let parent: TreeNode<T> | null = null;
   while (current) {
     // 找到了节点
     if (current.value === value) break;

     parent = current;

     if (current.value < value) {
       current = current.right;
     } else {
       current = current.left;
     }
   }
   // 如果没有找到要删除的节点返回 false
   if (!current) return false;

   // 2.  如果要删除的的节点是叶子结点
   if (current.left === null && current.right === null) {
     if (current === this.root) {
       // current 是根节点
       this.root = null;
     } else if (parent?.left === current) {
       // current 在父节点的左边
       parent!.left = null;
     } else {
       // current 在父节点的右边
       parent!.right = null;
     }
   }

   // 3. 如果要删除的的节点只有一个左子节点
   else if (current.right === null) {
     if (current === this.root) {
       this.root = current.left;
     } else if (parent?.left === current) {
       // current 在父节点的左边
       parent!.left = current.left;
     } else {
       parent!.right = current.left;
     }
   }

   // 4. 如果要删除的的节点只有一个右子节点
   else if (current.left === null) {
     if (current === this.root) {
       this.root = current.right;
     } else if (parent?.left === current) {
       // current 在父节点的左边
       parent!.left = current.right;
     } else {
       parent!.right = current.right;
     }
   }

   // 5. 如果要删除的的节点有两个子节点
   else {
     const successor = this.getSuccessor(current);
     if (current === this.root) {
       this.root = successor;
     } else if (parent?.left === current) {
       parent!.left = successor;
     } else {
       parent!.right = successor;
     }
   }
   return true;
 }

 // 获取后继节点
 private getSuccessor(delNode: TreeNode<T>): TreeNode<T> {
   // 获取右子树
   let current = delNode.right;
   let successor: TreeNode<T> | null = null;
   while (current) {
     successor = current;
     current = current.left;
   }

   // 拿到了后继节点
   if (successor !== delNode.right) {
     delNode!.right!.left = successor?.right ?? null;
     successor!.right = delNode.right;
   }

   // 一定要进行的操作:将删除几点的 left 赋值给后继节点的 left
   successor!.left = delNode.left;

   return successor!;
 }
转载自:https://juejin.cn/post/7197424757216706615
评论
请登录