二叉树

/***
 * 二叉查找树
 */
class TreeNode {
  constructor(value, leftNode, rightNode) {
    this.value = value;
    this.leftNode = leftNode;
    this.rightNode = rightNode;
  }
}

/**
 * 二叉搜索树
 * 1、创建  create(){}
 * 2、插入  insert(){}
 * 3、遍历  display(){}
 * 4、查找  find(){}
 * 5、删除  remove(){}
 */
class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  //创建二叉树
  create() {
    let length = 10;
    for (let i = 0; i < length; i++) {
      let value = Math.trunc(Math.random() * 10);
      this.root = this.insert(this.root, value);
    }
  }

  //插入新的节点
  insert(root, value) {
    if (root == null) {
      return new TreeNode(value, null, null);
    }

    //判断新增节点为左子树的节点
    if (root.value >= value) {
      root.leftNode = this.insert(root.leftNode, value);
    }

    //判断新增节点为右子树的节点
    if (root.value < value) {
      root.rightNode = this.insert(root.rightNode, value);
    }

    return root;
  }

  //遍历
  display(root) {
    if (root == null) {
      return;
    }

    this.display(root.leftNode);
    console.log(root.value);
    this.display(root.rightNode);
  }

  //查找
  find(root, value) {
    if (root == null) {
      return null;
    }

    //去左子树上去找
    if (root.value > value) {
      return this.find(root.leftNode, value);
    }

    //去右子树上找
    if (root.value < value) {
      return this.find(root.rightNode, value);
    }

    if (root.value == value) {
      console.log("找到节点:" + root.value);
      return root;
    }

    return null;
  }

  //删除
  remove(root, value) {
    //先查找到节点
    if (root == null) {
      return null;
    }

    if (root.value > value) {
      root.leftNode = this.remove(root.leftNode, value);
      return root;
    }

    if (root.value < value) {
      root.rightNode = this.remove(root.rightNode, value);
      return root;
    }

    //找到了要删除的节点。
    if (!root.leftNode && !root.rightNode) {
      return null;
    } else if (!root.leftNode) {
      return root.rightNode;
    } else if (!root.rightNode) {
      return root.leftNode;
    } else {
      //左右子树都存在的情形
      let node = root.rightNode;
      while (node.leftNode) {
        node = node.leftNode;
      }
      root.value = node.value;
      //再删除node节点
      root.rightNode = this.remove(root.rightNode, node.value);
      return root;
    }
  }
}

const binarySearchTree = new BinarySearchTree();
binarySearchTree.create();
binarySearchTree.display(binarySearchTree.root);

let findValue = 3;
let node = binarySearchTree.find(binarySearchTree.root, findValue);
if (node) {
  console.log(`存在值为${findValue}的节点`);
  binarySearchTree.remove(binarySearchTree.root, findValue);
  binarySearchTree.display(binarySearchTree.root);
} else {
  console.log(`不存在值为${findValue}的节点`);
}

module.exports.tree = binarySearchTree.root;
# 二叉树

二叉树
