• 数据结构——树&二叉树

    一、树

    （1）树的定义:

    • 树（Tree）: n（n≥0）个结点构成的有限集合

      • 当n=0时，称为空树

      • 对于任一棵非空树（n> 0），它具备以下性质：

      • 树中有一个称为“根（Root）”的特殊结点，用 root 表示；

      • 其余结点可分为m(m>0)个互不相交的有限集T1，T2，... ，Tm，其中每个集合本身又是一棵树，称为原来树的“子树（SubTree）”

    注意:

    • 子树之间不可以相交

    • 除了根结点外，每个结点有且仅有一个父结点

    • 一棵N个结点的树有N-1条边

    （2）树的结构

     

    （3）树的优点：

            树结构、数组和链表的对比

    • 数组:

      • 优点:

        • 数组的主要优点是根据下标值访问效率会很高.

        • 根据元素来查找对应的位置时先对数组进行排序, 再进行二分查找

      • 缺点:

        • 需要先对数组进行排序, 生成有序数组, 才能提高查找效率.

        • 另外数组在插入和删除数据时, 需要有大量的位移操作(插入到首位或者中间位置的时候), 效率很低.

    • 链表:

      • 优点:

      • 缺点:

        • 查找效率很低, 需要从头开始依次访问链表中的每个数据项, 直到找到.

        • 而且即使插入和删除操作效率很高, 但是如果要插入和删除中间位置的数据, 还是需要重头先找到对应的数据.

    • 树结构:

      • 不能说树结构比其他结构都要好, 因为每种数据结构都有自己特定的应用场景.

      • 但是树确实也综合了上面的数据结构的优点(当然优点不足于盖过其他数据结构), 并且也弥补了上面数据结构的缺点.

      • 而且为了模拟某些场景,使用树结构会更加方便. 比如文件的目录结构.

    （4）树的术语:

    1. 结点的度（Degree）：结点的子树个数

    2. 树的度：树的所有结点中最大的度数. (树的度通常为结点的个数N-1)

    3. 叶结点（Leaf）：度为0的结点. (也称为叶子结点)

    4. 父结点（Parent）：有子树的结点是其子树的根结点的父结点

    5. 子结点（Child）：若A结点是B结点的父结点，则称B结点是A结点的子结点(也称孩子结点)

    6. 兄弟结点（Sibling）：具有同一父结点的各结点彼此是兄弟结点

    7. 路径和路径长度：从结点n1到nk的路径为一个结点序列n1 , n2,… , nk, ni是 ni+1的父结点，路径所包含边的个数为路径的长度

    8. 结点的层次（Level）：规定根结点在1层，其它任一结点的层数是其父结点的层数加1

    9. 树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度

    二、二叉树

    1）概念

    • 树中每个节点最多只能有两个子节点, 这样的树就成为"二叉树"

       二叉树的定义

    • 二叉树可以为空, 即没有结点

    • 不为空时它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成

       二叉树的五种形态

    注：c和d是不同的二叉树, 因为二叉树有左右之分

    2）二叉树的特性

    • 一个二叉树第 i 层的最大结点数为：2^(i-1), i >= 1

    • 深度为k的二叉树有最大结点总数为： 2^k - 1, k >= 1

    • 对任何非空二叉树 T，若n0表示叶结点的个数、n2是度为2的非叶结点个数，那么两者满足关系n0 = n2 + 1

    3）特殊的二叉树

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

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

    • 完全二叉树(Complete Binary Tree)

      • 除二叉树最后一层外, 其他各层的节点数都达到最大个数

      • 且最后一层从左向右的叶结点连续存在, 只缺右侧若干节点

      • 完美二叉树是特殊的完全二叉树

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

    4）二叉树的存储

    • 二叉树的存储常见的方式是使用链表存储.

    • 链表存储:

      • 每个结点封装成一个Node, Node中包含存储的数据, 左结点的引用, 右结点的引用.

    三、二叉搜索树

    1）概念

    • 二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树

    • 二叉搜索树是一颗二叉树, 可以为空

    • 如果不为空，满足以下性质：

      • 非空左子树的所有键值小于其根结点的键值

      • 非空右子树的所有键值大于其根结点的键值

      • 左、右子树本身也都是二叉搜索树

    2）特点

    • 二叉搜索树的特点就是相对较小的值总是保存在左结点上, 相对较大的值总是保存在右结点上

    • 查找效率非常高, 这也是二叉搜索树中, 搜索的来源

    四、程序实现二叉搜索树

    1）创建二叉搜索树类

    1. //节点类
    2. class Node {
    3.             constructor(data) {
    4.                 this.left = null
    5.                 this.data = data
    6.                 this.right = null
    7.             }
    8.         }
    9. //二叉搜索树类
    10. class BST {
    11.             constructor() {
    12.                 this.root = null
    13.             }
    14. }

    2）二叉搜索树的操作

    二叉搜索树常见的操作：

    • insert(key)：向树中插入一个新的键

    • search(key)：在树中查找一个键，如果结点存在，则返回true；如果不存在，则返回false

    • preOrderTraverse：通过先序遍历方式遍历所有结点

    • inOrderTraverse：通过中序遍历方式遍历所有结点

    • postOrderTraverse：通过后序遍历方式遍历所有结点

    • min：返回树中最小的值/键

    • max：返回树中最大的值/键

    • remove(key)：从树中移除某个键

    （1） 向树中插入数据

    1. insert(ele) {
    2.                 //创建新节点
    3.                 let newnode = new Node(ele)
    4.                 if (this.root == null) {
    5.                     //空树
    6.                     this.root = newnode
    7.                 } else {
    8.                     this.insertNode(this.root, newnode)
    9.                 }
    10.  
    11.             }
    12.  
    13. insertNode(root, newnode) {
    14.                 if (newnode.data < root.data) { //放左边
    15.                     if (root.left == null) {
    16.                         root.left = newnode
    17.                     } else {
    18.                         this.insertNode(root.left, newnode)
    19.                     }
    20.                 }else{ //放右边
    21.                     if (root.right == null) {
    22.                         root.right = newnode
    23.                     } else {
    24.                         this.insertNode(root.right, newnode)
    25.                     }
    26.                 }
    27.             }

     图示：

    （2）遍历二叉搜索树

     1)preOrderTraverse：通过先序遍历方式遍历所有结点

    遍历过程：

    1. 访问根结点
    2. 先序遍历其左子树
    3. 先序遍历其右子树
    1. preOrderTraversal(){
    2.                 this.preOrderTraversalNode(this.root)
    3.             }
    4.  
    5.             preOrderTraversalNode(root){
    6.                 if(root!=null){
    7.                     //1.根
    8.                     console.log(root.data)
    9.                     //2.前序遍历左子树
    10.                     this.preOrderTraversalNode(root.left)
    11.                     //3.前序遍历右子树
    12.                     this.preOrderTraversalNode(root.right)
    13.                 }
    14.             }

     2）inOrderTraverse：通过中序遍历方式遍历所有结点

    遍历过程:

    1. 中序遍历其左子树

    2. 访问根结点

    3. 中序遍历其右子树

    1. inOrderTraversal(){
    2.                 this.inOrderTraversalNode(this.root)
    3.             }
    4.  
    5.             inOrderTraversalNode(root){
    6.                 if(root!=null){
    7.                     //1.中序遍历左子树
    8.                     this.inOrderTraversalNode(root.left)
    9.                     //2.根
    10.                     console.log(root.data)
    11.                     //3.中序遍历右子树
    12.                     this.inOrderTraversalNode(root.right)
    13.                 }
    14.             }

     3）postOrderTraverse：通过后序遍历方式遍历所有结点

    遍历过程：

    1. 后序遍历其左子树

    2. 后序遍历其右子树

    3. 访问根结点

    1. postOrderTraversal(){
    2.                 this.postOrderTraversalNode(this.root)
    3.             }
    4.  
    5.             postOrderTraversalNode(root){
    6.                 if(root!=null){
    7.                     //1.后序遍历左子树
    8.                     this.postOrderTraversalNode(root.left)
    9.                     //2.中序遍历右子树
    10.                     this.postOrderTraversalNode(root.right)
    11.                     //3.根
    12.                     console.log(root.data)
    13.                     
    14.                 }
    15.             }

    (3)返回树中最小的值/键

    1. getMin(){
    2.                 if(this.root==null){
    3.                     return
    4.                 }else{
    5.                     let current=this.root
    6.                     while(current.left!=null){
    7.                         current=current.left
    8.                     }
    9.                     return current.data
    10.                 }
    11.             }

    (4)返回树中最大的值/键

    1.  getMax(){
    2.                 if(this.root==null){
    3.                     return
    4.                 }else{
    5.                     let current=this.root
    6.                     while(current.right!=null){
    7.                         current=current.right
    8.                     }
    9.                     return current.data
    10.                 }
    11.             }

    (5)从树中移除某个键

    1.   remove(ele) {
    2.                 if (this.root == null) return
    3.                 let current = this.root,
    4.                     parent, isLeftChild
    5.                 //找到删除节点及其父节点，判断是否为左子节点
    6.                 while (ele != current.data) {
    7.                     if (ele < current.data) {
    8.                         //左边找
    9.                         parent = current
    10.                         current = current.left
    11.                         isLeftChild = true
    12.                     } else {
    13.                         parent = current
    14.                         current = current.right
    15.                         isLeftChild = false
    16.                     }
    17.                 }
    18.                 console.log(`当前删除的节点是${current.data},删除元素的父节点是${parent.data},是左子节点吗？${isLeftChild}`)
    19.  
    20.                 let delNode = current
    21.                 //1.删除叶节点 （左右子树都为空）
    22.                 if (delNode.left == null && delNode.right == null) {
    23.                     if (delNode == this.root) {
    24.                         this.root = null
    25.                     } else {
    26.                         if (isLeftChild) {
    27.                             //左子节点
    28.                             parent.left = null
    29.                         } else {
    30.                             //右子节点
    31.                             parent.right = null
    32.                         }
    33.                     }
    34.                 } else if (delNode.left != null && delNode.right == null) {
    35.                     //2.删除只有一个左子节点的节点
    36.                     if (delNode == this.root) {
    37.                         this.root = this.root.left
    38.                     } else {
    39.                         if (isLeftChild) {
    40.                             parent.left = delNode.left
    41.                         } else {
    42.                             parent.right = delNode.left
    43.                         }
    44.                     }
    45.                 } else if (delNode.left = null && delNode.right !== null) {
    46.                     //3.删除只有一个右子节点的节点
    47.                     if (delNode == this.root) {
    48.                         this.root = this.root.right
    49.                     } else {
    50.                         if (isLeftChild) {
    51.                             parent.left = delNode.right
    52.                         } else {
    53.                             parent.right = delNode.right
    54.                         }
    55.                     }
    56.                 } else {
    57.                     //4.删除有左右两个子节点的节点
    58.                     //前驱：左子树中的最大值   后继：右子树中的最小值
    59.                     let houji = this.gethouji(delNode)
    60.                     if(delNode==this.root){
    61.                         this.root=houji   
    62.                     }else{
    63.                         if(isLeftChild){
    64.                             parent.left=houji           
    65.                         }else{
    66.                             parent.right=houji
    67.                         }
    68.                     }
    69.                     houji.left=delNode.left
    70.                 }
    71.             }
    72.             gethouji(delNode) {
    73.                 let current = delNode.right  //后继
    74.                 let houjiparent = delNode
    75.                 while (current.left != null) {
    76.                     houjiparent = current
    77.                     current = current.left
    78.                 }
    79.                 if(current!=delNode.right){    //当后继为删除节点的右节点 
    80.                     houjiparent.left = current.right
    81.                     current.right=delNode.right
    82.                 }  
    83.                 return current
    84.             }

    (6) 查找（搜索）元素

    1.  search(ele){
    2.                 if(this.root==null) return
    3.                 let current=this.root
    4.                 while(current){
    5.                     if(eledata){
    6.                         //左边找
    7.                         current=current.left
    8.                     }else if(ele>current.data){
    9.                         //右边找
    10.                         current=current.right
    11.                     }else{
    12.                         return true
    13.                     }
    14.                 }
    15.                 return false
    16.             }

  • 相关阅读:
    多输入多输出 | MATLAB实现GA-BP遗传算法优化BP神经网络多输入多输出
    2022年最新河北水利水电施工安全员模拟试题题库及答案
    分布式数据库HBase（林子雨慕课课程）
    5.27机器人基础-机械臂逆解
    【AI视野·今日NLP 自然语言处理论文速览 第四十三期】Thu, 28 Sep 2023
    【Vue】Vue的Mustache插值语法、v-bind指令
    数据持久化技术（Python）的使用
    JavaScript实现MD5加密的6种方式
    用户体验 | 如何度量用户体验？
    仿写el-upload组件，彻底搞懂文件上传
  • 原文地址：https://blog.csdn.net/qq_56668869/article/details/126505681