// 广度优先遍历
breadthRirstSearch() {
    // 初始化用于广度优先遍历的队列
    let queue = new Queue();
    console.log('根节点', this[ROOT]);

    let arr = [];
    let root = this[ROOT];
    if (!root) return;

    queue.enqueue(root);

    while (queue.size()) {
        let queueFirst = queue.dequeue();
        arr.push(queueFirst.key);
        queueFirst.lchild && queue.enqueue(queueFirst.lchild);
        queueFirst.rchild && queue.enqueue(queueFirst.rchild);
    }

    return arr;
}

// 栈结构 用来辅助非递归遍历
class Stack {
  constructor() {
    this.items = [];
  }
  push(data) {
    this.items.push(data);
  }
  pop() {
    return this.items.pop();
  }
  peek() {
    return this.items[this.items.length - 1];
  }
  size() {
    return this.items.length;
  }
}

preOrderTraversal() {
    console.log('先序遍历');
    let root = this[ROOT];
    // 初始化辅助遍历存储的栈
    let stack = new Stack();

    let arr = []; // 用于存储先序遍历的顺序

    stack.push(root);

    // 如果栈不为空 则一直走
    while (stack.size()) {
        let stackTop = stack.pop();

        // 访问栈顶元素
        arr.push(stackTop.key);
        stackTop.rchild && stack.push(stackTop.rchild);
        stackTop.lchild && stack.push(stackTop.lchild);
    }

    return arr;
}