树(Tree)

树的定义

树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。

树(Tree): n(n>= 0) 个结点构成的有限集合。

当n = 0时,称为空树
结点的度(Degree): 节点的子树个数>= 1
树的度：树的所有结点中最大的度数
叶子结点：度为0的结点
路径和路径长度：结点之间的线段数,如a-b-c 为2
结点的层次：规定根结点在1层，其他任意结点的层数是其父结点的层数加1
树的深度：树中所有节点的最大层次

树的表示方式

普通表示法

这种表示法实现起来较复杂，采用数组的实现方式，子节点过多时，数组的维度越大，效率更低。
兄弟结点表示法

这种表示方法可采用链表来实现，即保证兄弟之间的位置，都根据左右结点来表示，即转成二叉树的实现方式，也就是说，所有的树结构都可以转成二叉树的形式。
```
// A结点
Node {
    this.data = data;
    this.leftChild = B;
    this.rightSibling = C
}
// C结点
Node {
    this.data = data;
    this.leftChild = G;
    this.rightSibling = D
}
```

二叉树

二叉树：每个节点最多含有两个子树的树称为二叉树；

特点

一个二叉树第i层的最大结点树为: 2^(i - 1)
深度为k的二叉树中最多含有2^k-1个节点
在二叉树中，有n0个叶子结点，n2个度为2的节点，则n0 = n2 + 1

特殊类型

满二叉树：叶节点除外的所有节点均含有两个子树的树被称为满二叉树

JS实现树结构

完全二叉树：除最后一层外，其他各层的节点数都达到最大值，且最后一层从左向右的叶节点连续存在，只缺右侧若干节点。

JS实现树结构

存储

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

使用数组：完美二叉树或者完全二叉树
使用链表：非完全二叉树

因为如果继续使用数组的话，会造成空间浪费。

JS实现树结构

二叉搜索树

特点

左节点的key值 < 父节点的key值 < 右节点的key值

代码实现

初始化二叉树代码

这里采用的是简单的三个属性

key: 用来保存值的大小

left: 用来表示左子树

right: 用来表示右字数

function BinarySearchTree() {
  // 节点元素
  function Node(key) {
    this.key = key // 这里简单的实现key为数字的，也可以保存为key-value的键值对
    this.left = null;
    this.right = null;
  }
   
  //初始化根节点
  this.root = null;
}

插入操作

判断是否有root根节点 --> 没有则直接添加为root
有根节点 -->添加递归插入方法
判断是添加在左节点还是右节点 --> 若是添加在左节点，判断是否为null，null则添加，反之，则一样。

BinarySearchTree.prototype.insert = (key) => {
    // 1. 创建节点元素
    const newNode = new Node(key);
    // 2. 判断是否有root根节点
    if(this.root === null) {
      this.root = newNode
    }else {
      insertNode(this.root, newNode)
    }
  }
   
  // 插入递归操作
  function insertNode(oldNode, newNode) {
    // 1. 判断是在左节点还是在右节点
    if( newNode.key < oldNode.key) {
      // 2. 判断左节点是否为null
      if(oldNode.left === null) {
        // 为null时，直接添加在后面
        oldNode.left = newNode;
      }else {
        // 不为null，则需要重新递归
        insertNode(oldNode.left, newNode)
      }
    }else {
      // 同上
      if(oldNode.right === null) {
        oldNode.right = newNode;
      }else {
        insertNode(oldNode.right, newNode)
      }
    }
  }
   
   
   
// 测试插入代码
const bsts = new BinarySearchTree();
bsts.insert(11)
bsts.insert(7)
bsts.insert(15)
bsts.insert(5)
bsts.insert(9)
bsts.insert(13)
bsts.insert(20)
bsts.insert(3)
bsts.insert(8)
bsts.insert(10)
bsts.insert(12)
bsts.insert(14)
bsts.insert(18)
bsts.insert(25)
bsts.insert(19)

添加完测试代码后，视图如下：

遍历操作

先序遍历

处理根节点
先序遍历左节点
先序遍历右节点

  BinarySearchTree.prototype.preOrder = function(cb) {
    _preOrderNode(this.root, cb)
  }
  // 先序遍历递归函数
  function _preOrderNode(node, cb) {
    // 如果在处理过程中，左右子树都为null后，则停止递归
    if(node !== null) {
      // 1处理key，将node.key通过callback函数进行累加
      cb(node.key);
      // 2处理经过的左子树
      _preOrderNode(node.left, cb)
      // 3处理经过的右子树
      _preOrderNode(node.right, cb)
      
    }
  }

中序遍历

中序遍历左节点
找到根节点
中序遍历右节点

BinarySearchTree.prototype.midOrder = function(cb) {
    _midOrderNode(this.root, cb)
  }
  function _midOrderNode(node, cb) {
    if(node !== null) {
      //  1. 中序遍历左节点
      _midOrderNode(node.left, cb)
      //  2. 找到根节点
      cb(node.key)
      //  3. 中序遍历右节点
      _midOrderNode(node.right, cb)
    }
  }

后序遍历

后序遍历左子树节点
后序遍历右子树节点
找到根节点

BinarySearchTree.prototype.postOrder = function(cb) {
    _postOrderNode(this.root, cb)
  }
  function _postOrderNode(node, cb) {
    if(node !== null) {
      //  1. 后序遍历左子树节点
      _postOrderNode(node.left, cb)
      //  2. 后序遍历右子树节点
      _postOrderNode(node.right, cb)
      //  3. 找到根节点
      cb(node.key)
    }
  }

测试代码

// 先序遍历测试
let pre = ""
bst.preOrder((key) => {
  pre += key + " "
})
console.log("先序遍历测试" + pre)
      
// 中序遍历测试
let mid = ""
bst.midOrder((key) => {
  mid += key + " "
})
console.log("中序遍历测试" +　mid)
      
      
// 后序遍历测试
let post = ""
bst.postOrder((key) => {
  post += key + " "
})
console.log("后序遍历测试" +post)
      
      
序遍历测试11 7 5 3 9 8 10 15 13 12 14 20 18 19 25
中序遍历测试3 5 7 8 9 10 11 12 13 14 15 18 19 20 25
后序遍历测试3 5 8 10 9 7 12 14 13 19 18 25 20 15 11

查找最值

结合二叉搜索树的特点，左子树节点 < 父节点 < 右子树节点

/**
   * 最大值max
   * 在当右子树为null时，所在的元素为最大
   */
  BinarySearchTree.prototype.max = () => {
    let node = this.root
    let key = null
    while(node) {
      key = node.key
      node = node.right
    }
    return key
  }
   
  /**
   * 最小值min
   * 在当左子树为null时，所在的元素为最小
   */
  BinarySearchTree.prototype.min = () => {
    let node = this.root
    let key = null
    while(node) {
      key = node.key
      node = node.left
    }
    return key
  }

搜索是否存在某个key值

 /**
   * 搜索是否存在某个key
   */
  BinarySearchTree.prototype.search = (key) => {
    let current = this.root;
    while(current) {
      if(key < current.key) {
        current = current.left
      }else if (key > current.key){
        current = current.right;
      }else {
        return true
      }
    }
    return false;
  }

删除操作

若key为叶子节点，key的父节点指向null
若key后只有一个节点，这key的父节点指向key的子节点
若key后有两个节点，需要考虑前驱或者后继节点来填补，再调整后续的节点变动

/**
   * 删除某个key
   * 1 若key为叶子节点，key的父节点指向null
   * 2 若key后只有一个节点，这key的父节点指向key的子节点
   * 3.若key后有两个节点，需要考虑前驱或者后继节点来填补，再调整后续的节点变动
   */
  BinarySearchTree.prototype.remove = (key) => {
    let current = this.root;
    // 需要记录parent，isLeftChild是左节点还是右节点
    let parent = this.root;
    let isLeftChild = true
    // 找出当前key所在位置
    while(current.key !== key) {
      parent = current
      if(key < current.key) {
        current = current.left
        isLeftChild = true
      }else {
        current = current.right
        isLeftChild = false
      }
      // 如果current为null，则直接退出
      if (current === null) {
        return false;
      }
    }
    const type = isLeftChild ? 'left' : 'right';
    // 当只有叶子节点
    if(current.left === null && current.right === null) {
      if(current.key === this.root.key) {
        this.root = null
      }else {
        parent[type] = null
      }
    }
    // 只有一个左子树节点，则需要将parent指向子节点
    else if (current.left === null && current.right) {
      // 将父节点指向子节点
      parent[type] = current.right
    } else if (current.right === null && current.left) {
      parent[type] = current.left
    }
    // 有两个子节点，可以找出前驱或者后继
    // 这里采用的是后继的做法，即比删除节点大一点点的树，即在右子树的最最最左节点
    else {
      // 找出后继节点
      const node = _closeBigger(current.right)
      if(current.key === this.root.key) {
        this.root = node
        node.left = current.left
      }else {
        if(isLeftChild) {
          parent.left = node
          node.left = current.left
        }else {
          parent.right = node
          node.left = current.left
        }
      }
    }
  }
  // 找出后继节点
  function _closeBigger(node) {
    let temp = node
    let current = null
    // 保存一个后继节点的父节点，因为可能存在后继节点不是node，而是后边left子树的节点
    let currentParent = null
    while(node) {
      currentParent = current // 保存父节点
      current = node
      node = node.left
    }
    // 当node.key !== current.key时，需要调整节点
    if(temp !== current) {
      // 根据平衡二叉树的性质，最左边是最小的，当currentParent.left -> current.right(存在或者为null)
      currentParent.left = current.right
      current.right = currentParent
    }
    return current
  }
}

上一篇： JS实现哈希表

JS实现树结构

树(Tree)

树的定义

树的表示方式

二叉树

特点

特殊类型

存储

二叉搜索树

特点

代码实现

常见问题FAQ

掘金(1h) SVIP

发表评论

如需帝国cms功能定制以及二次开发请联系我们

升级SVIP会员

工作时间

树(Tree)

树的定义

树的表示方式

二叉树

特点

特殊类型

存储

二叉搜索树

特点

代码实现

常见问题FAQ

掘金(1h) SVIP

相关推荐

发表评论

如需帝国cms功能定制以及二次开发请联系我们

升级SVIP会员

工作时间

请选择支付方式