二维数据结构

二叉树遍历

  1. 前序: 根-左-右
  1.     def preorder(self, root)
  2.         if(root): 
  3.             self.traverse_path.append(root.val)
  4.             self.preorder(root.left)
  5.             self.preorder(root.right)
  1. 中序: 左-根-右
  1.     def inorder(self, root)
  2.         if(root): 
  3.             self.inorder(root.left)
  4.             self.traverse_path.append(root.val)
  5.             self.inorder(root.right)
  1. 后序: 左-右-根
  1.     def postorder(self, root)
  2.         if(root): 
  3.             self.postorder(root.left)
  4.             self.postorder(root.right)
  5.             self.traverse_path.append(root.val)

二叉搜索树

空树或者具有以下性质的二叉树

  1. 左子树上的所有节点的值均小于它的根节点的值
  2. 右子树上的所有节点的值均大于它的根节点的值
  3. 左、右子树也分别为二叉搜索树
  4. 中序遍历：升序遍历

查询、插入、删除O(logN)

堆 Heap

find-max: O(1)
delette-max: O(logN)
insert(create): O(logN) or O(1)

二叉堆的实现细节

i left 2i+1
i right 2i+2
i parent floor((i-1)/2)

  1. const d = 2;
  2. function heap() {
  3.     this.heap = []
  4. }
  5. function parent(i) {
  6.     return Math.floor((i - 1) / d);
  7. }
  8. function kthChild(i, k) {
  9.     return d * i + k;
  10. }
  11. function heapifyUp(heap, i) {
  12.     var insertValue = heap[i];
  13.     while (i > 0 && insertValue > heap[parent(i)]) {
  14.         heap[i] = heap[parent(i)];
  15.         i = parent(i);
  16.     }
  17.     heap[i] = insertValue;
  18. }
  19. function heapifyDown(heap, i) {
  20.     var child,temp = heap[i];
  21.     while (kthChild(i, 1) < heap.length) {
  22.         child = maxChild(i);
  23.         if (temp >= heap[child]) {
  24.             break;
  25.         }
  26.         heap[i] = heap[child];
  27.         i = child;
  28.     }
  29.     heap[i] = temp;
  30. }
  31. function maxChild(i) {
  32.     var leftChild = kthChild(i, 1);
  33.     var rightChild = kthChild(i, 2);
  34.     return heap[leftChild] > heap[rightChild] ? leftChild : rightChild;
  35. }
  36. heap.prototype.insert = function(x) {
  37.     this.heap.push(x)
  38.     heapifyUp(this.heap, this.heap.length - 1)
  39. }
  40. heap.prototype.delete = function(x) {
  41.     var maxElement = this.heap[x];
  42.     this.heap[x] = this.heap[this.heap.length - 1];
  43.     heapifyDown(this.heap, x);
  44.     return maxElement;
  45. }

图的属性和分类

  • Graph(V, E)
  • V - vertex 点
    1. 度-入度和出度
    2. 点与点之间联通与否
  • E - edge 边
    1. 有向和无向（单行线）
    2. 权重（边长）

泛型递归、树的递归

  1. function recursion(level, param) {
  2.     // 终结条件
  3.     if(MAX_LEVEL < level) {
  4.         return process_result
  5.     }
  6.     // 处理当前层逻辑
  7.     process(level, data)
  8.     // 进入下一层
  9.     recursion(level + 1, p)
  11.     // 清理当前层
  12. }

分治、回溯

  1. function  divide_conquer(problem, param1, param2, ...) {
  2.     // recursion terminator 
  3.     if(problem is None) {
  4.         return
  5.     } 
  6.     // prepare data 
  7.     var data = prepare_data(problem) 
  8.     var subproblems = split_problem(problem, data) 
  9.     // conquer subproblems 
  10.     var subresult1 = self.divide_conquer(subproblems[0], p1, ...) 
  11.     var subresult2 = self.divide_conquer(subproblems[1], p1, ...) 
  12.     var subresult3 = self.divide_conquer(subproblems[2], p1, ...) 
  13.     ...
  14.     // process and generate the final result 
  15.     var result = process_result(subresult1, subresult2, subresult3, …)
  16.     // revert the current level states
  17. }