数据结构--笔记--树

typescript实现版本

一个树结构包含一系列存在父子关系的节点，每个节点都有一个父节点（除了根节点）以及零个或多个子节点。子树为互补相交的有限集合，除了根节点外，每个节点有且只有一个父节点

树是一种分层次组织的结构

树的一些基本术语

节点的度：节点的子树个数
树的度：树中所有节点中最大的度数
叶节点: 度为0的节点
父节点：有子树的结点是其子树的根节点的父节点
子节点：若a节点是b节点的父节点，则称b节点是a节点的子节点
兄弟节点：具有同一父节点的各节点彼此是兄弟节点
路径和路径长度：从节点n1到nk的路径为一个节点序列n1,n2,...,nk, ni是ni+1的父节点。路径所包含边的个数为路径的长度。下面图中A->B->D就是一个路径，长度是2
祖先节点：沿树根到某一节点路径上的所有节点都是这个节点的祖先节点。A，B就是D的祖先节点
子孙节点：某一节点的子树中所有节点都是这个节点的子孙
节点的层次：规定根节点在1层，其他任一节点的层数都是其父节点的层数加1
树的深度：树中所有节点中最大层次就是这棵树的深度。图中为树的深度3
```
graph LR
A-->B
A-->c
B-->D
B-->E
```
树的表示

用链表实现树结构
由于树可能有多个子节点，用同一种节点结构来表示可能会造成很大的空间浪费，n个节点的树有n-1个指针，如果用三个指针的结构来表示节点，就会有2n+1个指针是指向空的。

儿子兄弟表示法
```
graph LR
Element-->FirstChild
Element-->NextSibling
```

这样一般的树结构都可以用二叉树来表示。

二叉树和二叉搜索树

二叉树的子节点最多只有两个，一个左节点一个右节点。
二叉树的几个重要性质二叉搜索树（BST）是二叉树的一种，但它只允许左节点储存比父节点小的值，右节点储存比父节点大的值

常用的遍历方法：

preOrderTreverse 先序---根，左子树，右子树
inOrderTraverse 中序---左子树，根，右子树
postOrderTraverse 后序---左子树，右子树，根
levelOrderTraverse 层次便利---从上到下，从左到右

Todo用栈或者队列连实现遍历

class Node {
  constructor (key) {
    this.key = key
    this.left = null
    this.right = null
  }
}
class BinarySearchTree {
  constructor () {
    this.root = null
  }
  insert (key) {
    const newNode = new Node(key)
    if (this.root === null) {
      this.root = newNode
    } else {
      this._insertNode(this.root, newNode)
    }
    console.log(JSON.stringify(this.root, null, 2))
  }
  _insertNode (node, newNode) {
    if (newNode.key < node.key) {
      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)
      }
    }
  }
  search (key) {
    this._searchNode(this.root, key)
  }
  _searchNode (node, key) {
    if (node === null) {
      return false
    }

    if (key < node.key) {
      return this._searchNode(node.left, key)
    } else if (key > node.key) {
      return this._searchNode(node.right, key)
    } else {
      return true
    }
  }
  /**
   * 中序遍历；从小到大的顺序遍历节点
   * @param {any} cb 
   * @memberof BinarySearchTree
   */
  inOrderTraverse (cb) {
    this._inOrderTraverseNode(this.root, cb)
  }
  _inOrderTraverseNode (node ,cb) {
    if (node !== null) {
      this._inOrderTraverseNode(node.left, cb)
      cb(node.key)
      this._inOrderTraverseNode(node.right, cb)
    }
  }
  /**
   * 先访问根节点，在访问左节点，最后右节点
   * @param {any} cb 
   * @memberof BinarySearchTree
   */
  preOrderTraverse (cb) {
    this._preOrderTraverseNode(this.root, cb)
  }
  _preOrderTraverseNode(node, cb) {
    if (node !== null) {
      cb(node.key)
      this._preOrderTraverseNode(node.left, cb)
      this._preOrderTraverseNode(node.right, cb)
    }
  }
  postOrderTraverse (cb) {
    this._postOrderTraverseNode(this.root, cb)
  }
  _postOrderTraverseNode (node, cb) {
    if (node !== null) {
      this._postOrderTraverseNode(node.left, cb)
      this._postOrderTraverseNode(node.right, cb)
      cb(node.key)
    }
  }
  min () {
    return this._minNode(this.root)
  }
  _minNode (node) {
    if (node) {
      while (node && node.left !== null) {
        node = node.left
      }
      return node.key
    }
    return null
  }
  max () {
    return this._maxNode(this.root)
  }
  _maxNode (node) {
    if (node) {
      while (node && node.right !== null) {
        node = node.right
      }
      return node.key
    }
    return null
  }
  remove (key) {
    this.root = this._removeNode(this.root, key)
  }
  _removeNode (node, key) {
    if (node === null) {
      return null
    }
    if (key < node.key) {
      node.left = this._removeNode(node.left, key)
      return node
    } else if (key > node.key) {
      node.right = this._removeNode(node.right, key)
      return node
    } else {
      // 一个叶节点
      if (node.left === null && node.right === null) {
        node = null
        return node
      } else if (node.left === null) {
        // 存在右侧子节点，直接当前节点的指针指向子节点，跳过当前节点来移除当前节点
        node = node.right
        return  node
      } else if (node.right === null) {
        // 同上
        node = node.left
        return node
      } else {
        var aux = this.findMinNode(node.right) // 找到右侧最小的节点
        node.key = aux.key // 把要删除的节点的值替换成右侧最小节点的值
        node.right = this._removeNode(node.right, aux.key) // 删除掉右侧的这个节点
        return node
      }
    }
  }
  findMinNode (node) {
    return this._findMinNode(node)
  }
  _findMinNode (node) {
    if (node === null) {
      return null
    }
    while (node && node.left !== null) {
      node = node.left
    }
    return node
  }
}
const tree = new BinarySearchTree()
tree.insert(11)
tree.insert(7)
tree.insert(15)
tree.insert(5)
tree.insert(3)
tree.insert(8)
tree.insert(9)
tree.insert(10)
tree.insert(12)
tree.insert(13)
tree.insert(14)
tree.insert(20)
tree.insert(18)
tree.insert(25)
tree.inOrderTraverse(console.log) // 3 5 7 11 15
tree.remove(15)
tree.inOrderTraverse(console.log)
tree.preOrderTraverse(console.log) // 11 7 5 3 15
tree.postOrderTraverse(console.log) // 11 7 5 3 15

平衡二叉树

平衡因子：BF(T) = hL - hR
其中hL，hR分别为左右子树的高度
平衡二叉树（AVL树）
空树，或者任一节点左右子树高度差绝对值不超过1，即|BF(T)| <= 1

lulusir / my-blog

数据结构--笔记--树 #9

树的表示

儿子兄弟表示法

二叉树和二叉搜索树

平衡二叉树