数据结构之二叉树基本操作

节点与二叉树的数据结构

class Node {
  constructor (data, left, right) {
    this.data = data
    this.left = left
    this.right = right
  }
  show () {
    console.log(this.data)
  }
}

class Tree {
  constructor () {
    this.root = null
  }
}

二叉树中插入节点

Tree.prototype.insert = function (data) {
  let node = new Node(data, null, null)
  if (!this.root) {
    this.root = node
    return
  }
  let current = this.root
  while (current) {
    if (data < current.data) {
      if (!current.left) {
        current.left = node
        return
      }
      current = current.left
    } else {
      if (!current.right) {
        current.right = node
        return
      }
      current = current.right
    }
  }
}

二叉树先序遍历

Tree.prototype.preOrder = function (node = this.root) {
  if (!node) return
  node.show()
  this.preOrder(node.left)
  this.preOrder(node.right)
}

二叉树中序遍历

Tree.prototype.middleOrder = function (node = this.root) {
  if (!node) return
  this.middleOrder(node.left)
  node.show()
  this.middleOrder(node.right)
}

二叉树后序遍历

Tree.prototype.postOrder = function (node = this.root) {
  if (!node) return
  this.postOrder(node.left)
  this.postOrder(node.right)
  node.show()
}

二叉树获取最小值

Tree.prototype.getMin = function () {
  let current = this.root
  while (current.left) {
    current = current.left
  }
  current.show()
}

二叉树获取最大值

Tree.prototype.getMax = function () {
  let current = this.root
  while (current.right) {
    current = current.right
  }
  current.show()
}

二叉树查找节点

Tree.prototype.getNode = function (data, node = this.root) {
  if (!node) return 'not found'
  if (data === node.data) return node
  else if (data > node.data) return this.getNode(data, node.right)
  else return this.getNode(data, node.left)
}

二叉树获取深度

Tree.prototype.getDeep = function (node = this.root, deep) {
  deep = deep || 0
  if (!node) return deep
  deep++
  let ldeep = this.getDeep(node.left, deep)
  let rdeep = this.getDeep(node.right, deep)
  return ldeep > rdeep ? ldeep : rdeep
}

测试代码

let myTree = new Tree()
myTree.insert(5)
myTree.insert(1)
myTree.insert(2)
myTree.insert(7)
myTree.insert(9)
myTree.insert(4)
myTree.insert(6)
myTree.insert(3)
myTree.insert(8)
myTree.preOrder(myTree.root)
myTree.middleOrder(myTree.root)
myTree.postOrder(myTree.root)
myTree.getMin()
myTree.getMax()
console.log(myTree.getDeep())
console.log(myTree.getNode(3))
除特殊说明外本人博客均属原创,转载请注明出处:http://blog.johnhan.cn/blog_1094.html
京ICP备19044523号-1