#

# 二叉树的遍历算法

# 概述

二叉树作为一个基础的数据结构,遍历算法作为一个基础的算法,两者结合当然是经典的组合了。 很多题目都会有 ta 的身影,有直接问二叉树的遍历的,有间接问的。

你如果掌握了二叉树的遍历,那么也许其他复杂的树对于你来说也并不遥远了

二叉数的遍历主要有前中后遍历和层次遍历。 前中后属于 DFS,层次遍历属于 BFS。 DFS 和 BFS 都有着自己的应用,比如 leetcode 301 号问题和 609 号问题。

DFS 都可以使用栈来简化操作,并且其实树本身是一种递归的数据结构,因此递归和栈对于 DFS 来说是两个关键点。

BFS 的关键点在于如何记录每一层次是否遍历完成, 我们可以用一个标识位来表式当前层的结束。

下面我们依次讲解:

# 前序遍历

前序遍历的顺序是根-左-右

思路是:

  1. 先将根结点入栈

  2. 出栈一个元素,将右节点和左节点依次入栈

  3. 重复 2 的步骤

总结: 典型的递归数据结构,典型的用栈来简化操作的算法。

其实从宏观上表现为:自顶向下依次访问左侧链,然后自底向上依次访问右侧链, 如果从这个角度出发去写的话,算法就不一样了。从上向下我们可以直接递归访问即可,从下向上我们只需要借助栈也可以轻易做到。

这种思路解题有点像我总结过的一个解题思路backtrack - 回溯法。这种思路有一个好处就是 可以统一三种遍历的思路. 这个很重要,如果不了解的朋友,希望能够记住这一点。

# 中序遍历

中序遍历的顺序是 左-根-右,根节点不是先输出,这就有一点点复杂了。

  1. 根节点入栈

  2. 判断有没有左节点,如果有,则入栈,直到叶子节点

此时栈中保存的就是所有的左节点和根节点。

  1. 出栈,判断有没有右节点,有则入栈,继续执行 2

值得注意的是,中序遍历一个二叉查找树(BST)的结果是一个有序数组,利用这个性质有些题目可以得到简化。

# 后序遍历

后序遍历的顺序是 左-右-根

这个就有点难度了,要不也不会是 leetcode 困难的 难度啊。

其实这个也是属于根节点先不输出,并且根节点是最后输出。 这里可以采用一种讨巧的做法, 就是记录当前节点状态,如果 1. 当前节点是叶子节点或者 2.当前节点的左右子树都已经遍历过了,那么就可以出栈了。

对于 1. 当前节点是叶子节点,这个比较好判断,只要判断 left 和 right 是否同时为 null 就好。

对于 2. 当前节点的左右子树都已经遍历过了, 我们只需要用一个变量记录即可。最坏的情况,我们记录每一个节点的访问状况就好了,空间复杂度 O(n) 但是仔细想一下,我们使用了栈的结构,从叶子节点开始输出,我们记录一个当前出栈的元素就好了,空间复杂度 O(1), 具体请查看上方链接。

# 层次遍历

层次遍历的关键点在于如何记录每一层次是否遍历完成, 我们可以用一个标识位来表式当前层的结束。

具体做法:

  1. 根节点入队列, 并入队列一个特殊的标识位,此处是 null

  2. 出队列

  3. 判断是不是 null, 如果是则代表本层已经结束。我们再次判断是否当前队列为空,如果不为空继续入队一个 null,否则说明遍历已经完成,我们什么都不不用做

  4. 如果不为 null,说明这一层还没完,则将其左右子树依次入队列。

# 基本知识

# 二叉树

二叉树:二叉树是有限个结点的集合,这个集合或者是空集,或者是由一个根结点和两株互不相交的二叉树组成,其中一株叫根的做左子树,另一棵叫做根的右子树。

二叉树的性质

  • 性质 1:在二叉树中第 i 层的结点数最多为 2^(i-1)(i ≥ 1)
  • 性质 2:高度为 k 的二叉树其结点总数最多为 2^k-1( k ≥ 1)
  • 性质 3:对任意的非空二叉树 T ,如果叶结点的个数为 n0,而其度为 2 的结点数为 n2,则:n0 = n2 + 1

满二叉树:深度为 k 且有 2^k -1 个结点的二叉树称为满二叉树

完全二叉树:深度为 k 的,有 n 个结点的二叉树,当且仅当其每个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应,称之为完全二叉树。(除最后一层外,每一层上的节点数均达到最大值;在最后一层上只缺少右边的若干结点)

  • 性质 4:具有 n 个结点的完全二叉树的深度为 log2n + 1

注意

  • 仅有前序和后序遍历,不能确定一个二叉树,必须有中序遍历的结果

完全二叉树:

function TreeNode() {
  this.parent = {};
  this.children = [];
}

function FindRoot(node, TreeB) {
  let parent = node;
  const breadCrumbs = [];

  // Find root
  while (node.parent) {
    const index = parent.children.indexOf(node);
    breadCrumbs.push(index);
    parent = node.parent;
  }

  let found = TreeB.root;

  for (let i = breadCrumbs.length; i > -1; i--) {
    found = found[breadCrumbs[i]];
  }

  return found;
}

#

如果一棵完全二叉树的任意一个非终端结点的元素都不小于其左儿子结点和右儿子结点(如果有的话) 的元素,则称此完全二叉树为最大堆。

同样,如果一棵完全二叉树的任意一个非终端结点的元素都不大于其左儿子结点和右儿子结点(如果 有的话)的元素,则称此完全二叉树为最小堆。

最大堆的根结点中的元素在整个堆中是最大的;

最小堆的根结点中的元素在整个堆中是最小的。

# 哈弗曼树

  • 定义:给定 n 个权值作为 n 的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman tree)。

  • 构造:

    假设有 n 个权值,则构造出的哈夫曼树有 n 个叶子结点。 n 个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:

    1. 将 w1、w2、…,wn 看成是有 n 棵树的森林(每棵树仅有一个结点);
    2. 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
    3. 从森林中删除选取的两棵树,并将新树加入森林;
    4. 重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。

# 二叉排序树

二叉排序树(Binary Sort Tree)又称二叉查找树(Binary Search Tree),亦称二叉搜索树。

二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:

  1. 若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  2. 若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;
  3. 左、右子树也分别为二叉排序树;
  4. 没有键值相等的节点

二分查找的时间复杂度是 O(log(n)),最坏情况下的时间复杂度是 O(n)(相当于顺序查找)

# 平衡二叉树

平衡二叉树(balanced binary tree),又称 AVL 树。它或者是一棵空树,或者是具有如下性质的二叉树:

  1. 它的左子树和右子树都是平衡二叉树,
  2. 左子树和右子树的深度之差的绝对值不超过 1。

平衡二叉树是对二叉搜索树(又称为二叉排序树)的一种改进。二叉搜索树有一个缺点就是,树的结构是无法预料的,随意性很大,它只与节点的值和插入的顺序有关系,往往得到的是一个不平衡的二叉树。在最坏的情况下,可能得到的是一个单支二叉树,其高度和节点数相同,相当于一个单链表,对其正常的时间复杂度有 O(log(n))变成了 O(n),从而丧失了二叉排序树的一些应该有的优点。

# B-树

B-树:B-树是一种非二叉的查找树, 除了要满足查找树的特性,还要满足以下结构特性:

一棵 m 阶的 B-树:

  1. 树的根或者是一片叶子(一个节点的树),或者其儿子数在 2 和 m 之间。
  2. 除根外,所有的非叶子结点的孩子数在 m/2 和 m 之间。
  3. 所有的叶子结点都在相同的深度。

B-树的平均深度为 logm/2(N)。执行查找的平均时间为 O(logm);

# Trie 树

Trie 树,又称前缀树,字典树, 是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

Trie 树查询和插入时间复杂度都是 O(n),是一种以空间换时间的方法。当节点树较多的时候,Trie 树占用的内存会很大。

Trie 树常用于搜索提示。如当输入一个网址,可以自动搜索出可能的选择。当没有完全匹配的搜索结果,可以返回前缀最相似的可能。

# 例题

# 二叉树的遍历

# 二叉树前中后序遍历

二叉树的前中后序遍历,使用递归算法实现最为简单,以前序遍历(LeetCode 144 (opens new window))为例:

 void preorder(TreeNode *p, vector<int>& result) {
    if (p == NULL) {
        return;
    }

    result.push_back(p->val);
    preorder(p->left, result);
    preorder(p->right, result);
}

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> result;
        if (root == nullptr) {
        return result;
    }

    preorder(root, result);
    return result;
}

二叉树的非递归遍历,主要的思想是使用栈(Stack)来进行存储操作,记录经过的节点。

非递归前序遍历(LeetCode 144 (opens new window)):

vector<int> preorderTraversal(TreeNode* root) {
    TreeNode *p = root;
    vector<int> result;
    if (!p) {
        return result;
    }

    stack<TreeNode *> q;
    while (p || !q.empty()) {
        if (p) {
            result.push_back(p->val);
            q.push(p);
            p = p->left;
        }
        else {
            p = q.top();
            q.pop();
            p = p->right;
        }
    }
    return result;
}

非递归中序遍历(LeetCode 94 (opens new window)):

vector<int> inorderTraversal(TreeNode* root) {
    TreeNode *p = root;
    vector<int> result;
    if (!p) {
        return result;
    }

    stack<TreeNode *> q;
    while (p || !q.empty()) {
        if (p) {
            q.push(p);
            p = p->left;
        }
        else {
            p = q.top();
            result.push_back(p->val);
            q.pop();
            p = p->right;
        }
    }
    return result;
}

非递归遍历中,后序遍历相对更难实现,因为需要在遍历完左右子节点之后,再遍历根节点,因此不能直接将根节点出栈。这里使用一个 last 指针记录上次出栈的节点,当且仅当节点的右孩子为空(top->right == NULL),或者右孩子已经出栈(top->right == last),才将本节点出栈:

非递归后序遍历(LeetCode 145 (opens new window)):

 vector<int> postorderTraversal(TreeNode* root) {
    TreeNode *p = root;
    vector<int> result;
    if (!p) {
        return result;
    }

    TreeNode *top, *last = NULL;
    stack<TreeNode *> q;
    while (p || !q.empty()) {
        if (p) {
            q.push(p);
            p = p->left;
        } else {
            top = q.top();
            if (top->right == NULL || top->right == last) {
                q.pop();
                result.push_back(top->val);
                last = top;
            } else {
                p = top->right;
            }
        }
    }

    return result;
}

# 二叉树层序遍历 LeetCode 102 (opens new window)

二叉树层序遍历有两种方法,分别是深度优先和广度优先:

深度优先(DFS)实现:

void traversal(TreeNode *root, int level, vector<vector<int>> &result) {
    if (!root) {
        return;
    }
    // 保证每一层只有一个vector
    if (level > result.size()) {
        result.push_back(vector<int>());
    }
    result[level-1].push_back(root->val);
    traversal(root->left, level+1, result);
    traversal(root->right, level+1, result);
}

vector<vector<int> > levelOrder(TreeNode *root) {
    vector<vector<int>> result;
    traversal(root, 1, result);
    return result;
}

广度优先(BFS)实现:

vector<vector<int>> levelOrder(TreeNode* root) {
    std:queue<TreeNode *> q;
    TreeNode *p;

    vector<vector<int>> result;
    if (root == NULL) return result;

    q.push(root);

    while (!q.empty()) {
        int size = q.size();
        vector<int> levelResult;

        for (int i = 0; i < size; i++) {
            p = q.front();
            q.pop();

            levelResult.push_back(p->val);

            if (p->left) {
                q.push(p->left);
            }
            if (p->right) {
                q.push(p->right);
            }
        }

        result.push_back(levelResult);
    }

    return result;
}

# 二叉树子树 LeetCode 572 (opens new window)

判断二叉树是否是另一棵二叉树的子树,使用递归实现:

bool isSubtree(TreeNode* s, TreeNode* t) {
    if (!s) return false;
    if (sameTree(s, t)) return true;
    return isSubtree(s->left, t) || isSubtree(s->right, t);
}

bool sameTree(TreeNode* s, TreeNode* t) {
    if (!s && !t) return true;
    if (!s || !t) return false;
    if (s->val != t->val) return false;
    return sameTree(s->left, t->left) && sameTree(s->right, t->right);
}

# 翻转二叉树 LeetCode 226 (opens new window)

交互树的左右儿子节点,使用递归实现:

TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) {
        return nullptr;
    }
    TreeNode *tmp = root->left;
    root->left = root->right;
    root->right = tmp;
    if (root->left) {
        invertTree(root->left);
    }
    if (root->right) {
        invertTree(root->right);
    }
    return root;
}

# 额外

# 那你用过@antv/g6,里面有一个 tree,说说你大学时候接触到的 tree 的数据结构是怎么实现的?

毕业一年多,tree 的结构大概忘记了,我当时是这么回答的:

大学使用的是 C++学的数据结构,是用指针的形式,首先有一个根节点,根节点里有一个指针数组指向它的所有子节点,然后每一个子节点也是,拥有着子节点的指针数组,一层一层往下,直到为叶子节点,指针数组指向为空。

# 还记得二叉树吗?描述二叉树的几种遍历方式?

先序遍历:若二叉树非空,访问根结点,遍历左子树,遍历右子树。 中序遍历:若二叉树非空,遍历左子树;访问根结点;遍历右子树。 后序遍历:若二叉树非空,遍历左子树;遍历右子树;访问根结点。

所有遍历是以递归的形似,直到没有子节点。

# 树的先序后序

https://blog.csdn.net/weixin_38984353/article/details/80393412

# Code

# 前序遍历得到的字符串

let strArr = 'AB#D##C##'.split('');

function BiTree(ele) {
  this.data = ele;
  this.lChild = null;
  this.rChild = null;
}
var newTree = new BiTree('#');

function createBiTree(biTree) {
  if (strArr.length == 0) return;
  let str = strArr.shift();
  if (str == '#') return;
  biTree.data = str;
  if (strArr[0] != '#') {
    biTree.lChild = new BiTree('#');
  }
  createBiTree(biTree.lChild);
  if (strArr[0] != '#') {
    biTree.rChild = new BiTree('#');
  }
  createBiTree(biTree.rChild);
}
createBiTree(newTree);
console.log(newTree);
ProOrderTraverse(newTree);

//前序遍历
function ProOrderTraverse(biTree) {
  if (biTree == null) return;
  console.log(biTree.data);
  ProOrderTraverse(biTree.lChild);
  ProOrderTraverse(biTree.rChild);
}

//中序遍历
function InOrderTraverse(biTree) {
  if (biTree == null) return;
  InOrderTraverse(biTree.lChild);
  console.log(biTree.data);
  InOrderTraverse(biTree.rChild);
}

//后续遍历
function PostOrderTraverse(biTree) {
  if (biTree == null) return;
  PostOrderTraverse(biTree.lChild);
  PostOrderTraverse(biTree.rChild);
  console.log(biTree.data);
}

# 递归式深度遍历 tree

/**
 * 递归式深度遍历tree
 */
function deepTravel(tree, nodeList = []) {
  if (tree) {
    nodeList.push(tree);
    for (let i of Object.keys(tree.children)) {
      deepTravel(tree.children[i], nodeList);
    }
  }
  return nodeList;
}

/**
 * 非递归式 遍历tree
 *
 * 使用:栈
 * 但入栈时是反着把 children 数组 push 入栈的,保证下一次 pop 能拿到左子树元素
 */
function deepTravel(tree) {
  let stack = [];
  let nodeList = [];
  tree && stack.push(tree);
  //注意,这里如果 while(stack) 会死循环
  while (stack.length) {
    let node = stack.pop();
    nodeList.push(node);
    for (let i = node.children.length - 1; i >= 0; i--) {
      stack.push(node.children[i]);
    }
  }
}

深度优先

function initCallbacks(callbacks = {}) {
  // Init empty callbacks object.
  const initiatedCallbacks = {};

  // Empty callback that we will use in case if user didn't provide real callback function.
  const stubCallback = () => {};
  // By default we will allow traversal of every node
  // in case if user didn't provide a callback for that.
  const defaultAllowTraversalCallback = () => true;

  // Copy original callbacks to our initiatedCallbacks object or use default callbacks instead.
  initiatedCallbacks.allowTraversal = callbacks.allowTraversal || defaultAllowTraversalCallback;
  initiatedCallbacks.enterNode = callbacks.enterNode || stubCallback;
  initiatedCallbacks.leaveNode = callbacks.leaveNode || stubCallback;

  // Returned processed list of callbacks.
  return initiatedCallbacks;
}

/**
 * Recursive depth-first-search traversal for binary.
 *
 * @param {BinaryTreeNode} node - binary tree node that we will start traversal from.
 * @param {TraversalCallbacks} callbacks - the object that contains traversal callbacks.
 */
export function depthFirstSearchRecursive(node, callbacks) {
  // Call the "enterNode" callback to notify that the node is going to be entered.
  callbacks.enterNode(node);

  // Traverse left branch only if case if traversal of the left node is allowed.
  if (node.left && callbacks.allowTraversal(node, node.left)) {
    depthFirstSearchRecursive(node.left, callbacks);
  }

  // Traverse right branch only if case if traversal of the right node is allowed.
  if (node.right && callbacks.allowTraversal(node, node.right)) {
    depthFirstSearchRecursive(node.right, callbacks);
  }

  // Call the "leaveNode" callback to notify that traversal
  // of the current node and its children is finished.
  callbacks.leaveNode(node);
}

/**
 * Perform depth-first-search traversal of the rootNode.
 * For every traversal step call "allowTraversal", "enterNode" and "leaveNode" callbacks.
 * See TraversalCallbacks type definition for more details about the shape of callbacks object.
 *
 * @param {BinaryTreeNode} rootNode - The node from which we start traversing.
 * @param {TraversalCallbacks} [callbacks] - Traversal callbacks.
 */
export default function depthFirstSearch(rootNode, callbacks) {
  // In case if user didn't provide some callback we need to replace them with default ones.
  const processedCallbacks = initCallbacks(callbacks);

  // Now, when we have all necessary callbacks we may proceed to recursive traversal.
  depthFirstSearchRecursive(rootNode, processedCallbacks);
}

# 广度优先遍历树

/**
 * 广度优先遍历树
 *
 * 使用: 队列
 */
function widthTravel(tree) {
  let queue = [];
  let nodeList = [];
  tree && queue.push(tree);
  while (queue.length) {
    let node = queue.shift();
    for (let i = 0; i < node.children.length; i++) {
      queue.push(node[i]);
    }
  }
  return nodeList;
}

广度优先

function initCallbacks(callbacks = {}) {
  const initiatedCallback = callbacks;

  const stubCallback = () => {};
  const defaultAllowTraversal = () => true;

  initiatedCallback.allowTraversal = callbacks.allowTraversal || defaultAllowTraversal;
  initiatedCallback.enterNode = callbacks.enterNode || stubCallback;
  initiatedCallback.leaveNode = callbacks.leaveNode || stubCallback;

  return initiatedCallback;
}

/**
 * @param {BinaryTreeNode} rootNode
 * @param {Callbacks} [originalCallbacks]
 */
export default function breadthFirstSearch(rootNode, originalCallbacks) {
  const callbacks = initCallbacks(originalCallbacks);
  const nodeQueue = new Queue();

  // Do initial queue setup.
  nodeQueue.enqueue(rootNode);

  while (!nodeQueue.isEmpty()) {
    const currentNode = nodeQueue.dequeue();

    callbacks.enterNode(currentNode);

    // Add all children to the queue for future traversals.

    // Traverse left branch.
    if (currentNode.left && callbacks.allowTraversal(currentNode, currentNode.left)) {
      nodeQueue.enqueue(currentNode.left);
    }

    // Traverse right branch.
    if (currentNode.right && callbacks.allowTraversal(currentNode, currentNode.right)) {
      nodeQueue.enqueue(currentNode.right);
    }

    callbacks.leaveNode(currentNode);
  }
}

# BinarySearchTree

class Node {
  data: number;

  parent: Node;

  left: Node;

  right: Node;

  constructor(data: number) {
    this.data = data;
  }

  isLeaf(): boolean {
    return !this.left && !this.right;
  }
}

export default class BinarySearchTree {
  root: Node;

  items = [];

  constructor(items: Array<number>) {
    for (const item of items) this.add(item);
  }

  toArray(node?: Node): boolean | void {
    if (!node) node = this.root;

    if (node.isLeaf()) {
      if (node.left) this.items.push(node.left.data);
      this.items.push(node.data);
      if (node.right) this.items.push(node.right.data);
      return true;
    }

    if (node.left) this.toArray(node.left);
    this.items.push(node.data);
    if (node.right) this.toArray(node.right);
  }

  add(element: number, root?: Node): boolean {
    let _root = root;

    if (!this.root) {
      this.root = new Node(element);
      return true;
    }

    if (!_root) _root = this.root;

    if (!_root.data) {
      _root.data = element;
      return true;
    }

    if (_root.data > element) {
      if (!_root.left) {
        _root.left = new Node(element);
        return true;
      }
      return this.add(element, _root.left);
    }

    if (!_root.right) {
      _root.right = new Node(element);
      return true;
    }

    return this.add(element, _root.right);
  }

  remove() {}

  find() {}
}
class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  // O(n), where n is # nodes
  get(value) {
    let node = this.root;
    while (node != null) {
      if (value === node.value) return node.value;
      else if (value < node.value) node = node.left;
      else node = node.right;
    }
    return null;
  }

  // O(n), where n is # nodes
  has(value) {
    return this.get(value) !== null;
  }

  // O(n), where n is # nodes
  add(...values) {
    function _add(value, node) {
      if (node === null) return new Node(value);
      if (value < node.value) {
        node.left = _add(value, node.left);
      } else if (value > node.value) {
        node.right = _add(value, node.right);
      } else {
        node.value = value;
      }
      return node;
    }
    for (let value of values) {
      this.root = _add(value, this.root);
    }
  }

  // O(n), where n is # nodes
  size() {
    let _size = node => (node === null ? 0 : 1 + _size(node.left) + _size(node.right));
    return _size(this.root);
  }

  // Hibbard deletion
  remove(value) {
    function _remove(value, node) {
      if (node === null) return null;
      if (value < node.value) node.left = _remove(value, node.left);
      else if (value > node.value) node.right = _remove(value, node.right);
      else {
        if (node.right === null) return node.left;
        if (node.left === null) return node.right;

        let t = node;
        node = min(t.right);
        node.right = removeMin(t.right);
        node.left = t.left;
      }
      return node;
    }

    function removeMin(node) {
      if (node.left === null) return node.right;
      node.left = removeMin(node.left);
      return node;
    }

    function min(node) {
      let curr = node;
      while (curr.left !== null) curr = curr.left;
      return curr;
    }

    this.root = _remove(value, this.root);
  }
}

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

# BTree

class TreeNode {
  keys: Array<number> = [];

  children: Array<TreeNode> = [];

  parent: TreeNode;

  isLeaf() {
    return this.children.length === 0;
  }

  findMiddleChild() {
    return this.children[Math.ceil(this.children.length / 2)];
  }
}

export default class BTree {
  root: TreeNode = new TreeNode();

  t: number = 3;

  search(value: number, node: TreeNode = this.root) {
    // For each key of the node's keys
    for (let i = 0; i < node.keys.length; i++) {
      // If the value is less than the current key
      if (value === node.keys[i]) {
        return value;
      }
      if (value < node.keys[i]) {
        if (node.children[i].keys.length === 0) {
          return -1;
        }
        return this.search(value, node.children[i]);
      }
    }

    return '';
  }

  insert(value: number, node = this.root): boolean {
    // For each key of the node's keys
    for (let i = 0; i < node.keys.length; i++) {
      // If the value is less than the current key
      if (value === node.keys[i]) {
        return value;
      }
      if (value < node.keys[i]) {
        if (node.children[i].keys.length === 0) {
          return -1;
        }
        return this.search(value, node.children[i]);
      }
    }

    return true;
  }

  split(node: TreeNode) {
    // If the node doesn't need to be split, abort
    if (node.children.length < this.t) {
    } else {
      // Otherwise, Split

      // Find index of 'middle' key
      const middleIndex = Math.ceil(node.keys.length / 2);
    }
  }
}

# 深度列表

深度列表:给定一个二叉树,设计一个算法来创建每个深度上的所有节点的链表(例如,如果树的深度为 0,你将有 0 个链表)

export default function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

Node.prototype.insert = function(value) {
  if (value < this.value) {
    if (!this.left) {
      return (this.left = new Node(value));
    }
    return this.left.insert(value);
  }

  return this.right ? this.right.insert(value) : (this.right = new Node(value));
};

Node.prototype.print = function() {
  const leftstr = this.left ? `${this.left.print()}, ` : '';
  return leftstr + this.value + (this.right ? `, ${this.right.print()}` : '');
};

const root = new Node(0); // start with a node at 0

Node.prototype.listify = function() {
  const lists = [[this.value]];
  let nextQueue = [this.right, this.left];

  let queue;

  while (nextQueue.length !== 0) {
    queue = nextQueue;
    nextQueue = [];
    const newlist = [];
    while (queue.length !== 0) {
      const node = queue.pop();
      if (node) {
        if (node.left) {
          nextQueue.unshift(node.left);
        }
        if (node.right) {
          nextQueue.unshift(node.right);
        }
        newlist.push(node.value);
      }
    }
    lists.push(newlist);
  }

  return lists;
};

root.listify();

# 描述二叉树的几种遍历方式?

先序遍历:若二叉树非空,访问根结点,遍历左子树,遍历右子树。 中序遍历:若二叉树非空,遍历左子树;访问根结点;遍历右子树。 后序遍历:若二叉树非空,遍历左子树;遍历右子树;访问根结点。

所有遍历是以递归的形似,直到没有子节点

单向链表怎么査找有没有环? 数据结构(数组.队列,链表,堆.二叉树,哈希表)

栈和队列的区别?

  • 栈的插入和删除操作都是在一端进行的,而队列的操作却是在两端进行的。
  • 队列先进先出,栈先进后出。
  • 栈只允许在表尾一端进行插入和删除,而队列只允许在表尾一端进行插入,在表头一端进行删除

栈和堆的区别?

  • 栈区(stack)— 由编译器自动分配释放 ,存放函数的参数值,局部变量的值等。
  • 堆区(heap) — 一般由程序员分配释放, 若程序员不释放,程序结束时可能由 OS 回收。
  • 堆(数据结构):堆可以被看成是一棵树,如:堆排序;
  • 栈(数据结构):一种先进后出的数据结构

快速 排序的思想并实现一个快排?

"快速排序"的思想很简单,整个排序过程只需要三步:

  • (1)在数据集之中,找一个基准点
  • (2)建立两个数组,分别存储左边和右边的数组
  • (3)利用递归进行下次比较
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr; //如果数组只有一个数,就直接返回;
  }

  var num = Math.floor(arr.length / 2); //找到中间数的索引值,如果是浮点数,则向下取整

  var numValue = arr.splice(num, 1); //找到中间数的值
  var left = [];
  var right = [];

  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < numValue) {
      left.push(arr[i]); //基准点的左边的数传到左边数组
    } else {
      right.push(arr[i]); //基准点的右边的数传到右边数组
    }
  }

  return quickSort(left).concat([numValue], quickSort(right)); //递归不断重复比较
}

alert(quickSort([32, 45, 37, 16, 2, 87])); //弹出“2,16,32,37,45,87”

二叉树层次遍历

# 按行打印二叉树层级节点值,逗号作为间隔

function fn(root) {
  if (root) {
    var queue = [root];
    var currentLength = queue.length;
    var current = null;
    var currentArr = [];
    while (queue.length) {
      current = queue.shift();
      currentLength--;
      currentArr.push(current.value);
      if (current.left) {
        queue.push(current.left);
      }
      if (current.right) {
        queue.push(current.right);
      }
      if (currentLength === 0) {
        console.log(currentArr.join(', '));
        currentArr.length = 0;
        currentLength = queue.length;
      }
    }
  }
}

# General/PrintKDistance

// Given a string S, and an integer K, rearrange the string such that
// similar characters are at least K distance apart.

// Example:

// S = AAABBBCC, K = 3
// Result : ABCABCABC (all 'A's are 3 distance apart, similarly with
// B's and C's)

// S = AAABC, K=2 : Not possible. (EDIT : k=3 is not possible).

// S = AAADBBCC, K = 2:
// Result: ABCABCDA

function PrintKDistance(string) {
  const chars = Array.from(string);
  const map = new Map();

  for (const char of chars) {
    if (map.has(char)) {
      map.set(char, map.get(char) + 1);
    } else {
      map.set(char, 1);
    }
  }

  let str = '';

  const itr = 1000;
  let i = 0;

  while (map.size > 0) {
    for (const key of map.keys()) {
      str += key;
      // Decrement key
      map.set(key, map.get(key) - 1);
      // If key = 0, remove
      if (map.get(key) === 0) {
        map.delete(key);
      }
    }
    if (i > itr) {
      break;
    }
    i++;
  }

  return str;
}

PrintKDistance('AAABBBCC');