二叉树

1、新建+各种遍历

//API:
//insert添加一个子树，传值Number
//bulkInsert批量添加子树，传值Array
//showTree返回二叉树对象

class BinaryTree {
  constructor(tree = []) {
    this.root = null; //树根
    this.Node = (key) => {
      //生成一个新的子树
      let _obj = Object.create(null, {});
      _obj.key = key;
      _obj.left = null;
      _obj.right = null;
      return _obj;
    };

    //初始化二叉树
    if (typeof tree === 'number') {
      this.insert(tree);
    } else if (Array.isArray(tree)) {
      this.bulkInsert(tree);
    } else {
      console.error('请输入Number类型或者Array类型的参数');
    }
  }

  insert(key) {
    //添加一个新子树
    let newNode = this.Node(key);
    let _insertNode = (node, newNode) => {
      //判断新二叉树的值和原有节点的值
      if (newNode.key < node.key) {
        if (node.left === null) {
          //判断左节点是否为空
          node.left = newNode;
        } else {
          _insertNode(node.left, newNode);
        }
      } else {
        if (node.right === null) {
          //判断右节点是否为空
          node.right = newNode;
        } else {
          _insertNode(node.right, newNode);
        }
      }
    };

    if (this.root === null) {
      //如果没有根节点，那么把传入的值当根节点
      this.root = newNode;
    } else {
      //如果有根节点，那么把传入的值插到二叉树上
      _insertNode(this.root, newNode);
    }
  }

  bulkInsert(nodes) {
    nodes.forEach((key) => {
      //遍历数组，插入子树
      this.insert(key);
    });
  }

  showTree() {
    //返回二叉树对象
    return this.root;
  }

  inOrderTraverse(fn) {
    //中序遍历，传入一个回调函数
    // 左根右
    let inOrderTraverseNode = (node, callback) => {
      if (node !== null) {
        inOrderTraverseNode(node.left, callback);
        callback(node.key);
        inOrderTraverseNode(node.right, callback);
      }
    };
    inOrderTraverseNode(this.root, fn);
  }

  // 前序遍历非递归实现
  preOrderTraverse() {
    const preOrderTraverseNode = (root) => {
      var arr = [],
        res = [];
      if (root != null) {
        arr.push(root);
      }
      while (arr.length != 0) {
        var temp = arr.pop();
        res.push(temp.key);
        if (temp.right != null) {
          arr.push(temp.right);
        }
        if (temp.left != null) {
          arr.push(temp.left);
        }
      }
      return res;
    };
    return preOrderTraverseNode(this.root);
  }

  preOrderTraverse(fn) {
    //先序遍历，传入一个回调函数
    // 根左右
    let preOrderTraverseNode = (node, callback) => {
      if (node !== null) {
        callback(node.key);
        preOrderTraverseNode(node.left, callback);
        preOrderTraverseNode(node.right, callback);
      }
    };
    preOrderTraverseNode(this.root, fn);
  }

  postOrderTraverse(fn) {
    //后序遍历，传入一个回调函数
    // 左右根
    let postOrderTraverseNode = (node, callback) => {
      if (node !== null) {
        postOrderTraverseNode(node.left, callback);
        postOrderTraverseNode(node.right, callback);
        callback(node.key);
      }
    };
    postOrderTraverseNode(this.root, fn);
  }
}

let nodes = [8, 3, 6, 4, 9, 11, 2, 5, 7];
let binaryTree = new BinaryTree(nodes);
let arr1 = [],
  arr2 = [],
  arr3 = [];

console.log(binaryTree);

binaryTree.inOrderTraverse((key) => {
  arr1.push(key); //中序遍历[2, 3, 4, 5, 6, 7, 8, 9, 11]
});
binaryTree.preOrderTraverse((key) => {
  arr2.push(key); //先序遍历[8, 3, 2, 6, 4, 5, 7, 9, 11]
});
binaryTree.postOrderTraverse((key) => {
  arr3.push(key); //后序遍历[2, 5, 4, 7, 6, 3, 11, 9, 8]
});

console.log(binaryTree, arr1, arr2, arr3);

2、示例

image.png