---
tags: 提升程式設計師的面試力
---

# 樹和圖

### 二元堆積 (最大堆積和最小堆積)

二元堆積（英語：binary heap）是一種特殊的堆積，二元堆積是完全二元樹或者是近似完全二元樹。二元堆積滿足堆積特性：父節點的鍵值總是保持固定的序關係於任何一個子節點的鍵值，且每個節點的左子樹和右子樹都是一個二元堆積。

當父節點的鍵值總是大於或等於任何一個子節點的鍵值時為「最大堆積」。當父節點的鍵值總是小於或等於任何一個子節點的鍵值時為「最小堆積」。

(然而, 同一層的子節點則無須理會其大小關係)

所以大概長得像這樣(Min heap):

                           ４ - s
                          / \
                         /   \
                        50    7
                      /   \  / 
                     55   90 87 

Step 1 
                           ４
                          / \
                         /   \
                        50    7
                      /   \  / \
                     55   90 87 2

Step 2 
                           ４
                          / \
                         /   \
                        50    2
                      /   \  / \
                     55   90 87 7

Step 3 
                           2
                          / \
                         /   \
                        50    4
                      /   \  / \
                     55   90 87 7

https://clu.gitbook.io/data-structure-note/heap-tree

### 線索樹 (字首樹)

線索二元樹(引線二元樹) 的定義如下:

「一個二元樹通過如下的方法「穿起來」：所有原本為空的右(孩子)指針改為指向該節點在中序序列中的後繼，所有原本為空的左(孩子)指針改為指向該節點的中序序列的前驅。」

線索二元樹能線性地遍歷二元樹，從而比遞歸的 中序遍歷更快。使用線索二元樹也能夠方便的找到一個節點的父節點，這比顯式地使用父親節點指針或者棧效率更高。這在棧空間有限，或者無法使用存儲父節點的棧時很有作用（對於通過深度優先搜索來查找父節點而言)。

()
/ \ \
/ \ \
/ \ \
/ \ \
a r n
/ \ \ \
h x o o
/ \ \ \
null i l null
\ \
null null

https://zh.wikipedia.org/wiki/%E7%BA%BF%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91
https://www.youtube.com/watch?v=jpCJgD0kusM

### 圖

Graph 中文翻做「圖」。此處談及的「圖」並不是指圖片或者圖形。「圖」是一種用來記錄關聯、關係的東西。

一張圖由數個點（ vertex ）以及數條邊（ edge ）所構成。點與點之間，得以邊相連接，表示這兩點有關聯、關係。

Graph 資料結構 :
Adjacency Matrix

| | 0 | 1 | 2 |
| --| --| --|-- |
| 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 2 | 1 | 1 | 0 |

Graph 資料結構 :
Adjacency Lists

0:2
1:2
2:0,1

http://web.ntnu.edu.tw/~algo/Graph.html

範例使用圖
https://docs.google.com/presentation/d/13Omtj7zGZkR8j485XO3pow1CGNUxbtF-9P1aL_iu0qw/edit#slide=id.g117efa2c41c_0_41

4.7 建構順序： 你將得到一個專案列表和一個依賴專案列表。在一個專案開始建構之前，必須建構好該專案所有的依賴的專案。請找到一個能讓專案順利建構的順序。如果找不到有效的建構順序，則回傳錯誤。

專案： a,b c,d,e,f

依賴專案順序：(a,b),(f,b),(b,d),(f,a),(d,c)


Graph.prototype.findNodeWithNoChildren = function() {
  for (var node in this.nodes) {
    if (Object.keys(this.nodes[node]).length === 0) {
      return node;
    }
  }
  return undefined;
};

var buildOrder = function(projects, dependencies) {
  var graph = new Graph();
  projects.forEach(project => {
    graph.addNode(project);
  });
  dependencies.forEach(dependency => {
    graph.addEdge(dependency[1], dependency[0]);
  });
  var answer = [];
  var currNode = graph.findNodeWithNoChildren();
  while (currNode !== undefined) {
    answer.push(currNode);
    graph.removeNode(currNode);
    currNode = graph.findNodeWithNoChildren();
  }
  if (answer.length === projects.length) {
    return answer;
  } else {
    throw Error;
  }
};

/* TEST */
var projects = ['a', 'b', 'c', 'd', 'e', 'f'];
var dependencies = [['a', 'd'], ['f', 'b'], ['b', 'd'], ['f', 'a'], ['d', 'c']];

console.log(buildOrder(projects, dependencies));

4.8 第一個共同祖先： 請設計一個演算法並撰寫程式碼，搜尋二元樹中兩個節點的第一個共同祖先。請避免在資料結構中儲存額外的節點。

var BinaryTree = function(value) {
  this.value = value;
  this.left = null;
  this.right = null;
  this.parent = null;
};

BinaryTree.prototype.isAncestor = function(node2) {
  if (this === node2) {
    return true;
  } else {
    var answer1 = false;
    var answer2 = false;
    if (this.left !== null) {
      answer1 = this.left.isAncestor(node2);
    }
    if (this.right !== null) {
      answer2 = this.right.isAncestor(node2);
    }
    return false || answer1 || answer2;
  }
};

var firstCommonAncestor = function(node1, node2) {
  var currNode = node1;
  while (!currNode.isAncestor(node2)) {
    if (currNode === null) {
      throw Error;
    } else {
      currNode = currNode.parent;
    }
  }
  return currNode.value;
};

/* TEST */
var a = new BinaryTree('a');
var b = new BinaryTree('b');
var c = new BinaryTree('c');
var d = new BinaryTree('d');
var e = new BinaryTree('e');
var f = new BinaryTree('f');
var g = new BinaryTree('g');
var h = new BinaryTree('h');
var i = new BinaryTree('i');
var j = new BinaryTree('j');
var k = new BinaryTree('k');
var l = new BinaryTree('l');

a.left = b; b.parent = a;
a.right = c; c.parent = a;
b.left = d; d.parent = b;
d.left = g; g.parent = d;
d.right = h; h.parent = d;
h.right = k; k.parent = h;
k.left = l; l.parent = k;
c.left = e; e.parent = c;
c.right = f; f.parent = c;
f.left = i; i.parent = f;
f.right = j; j.parent = f;

console.log(firstCommonAncestor(g, k), 'd');
console.log(firstCommonAncestor(b, i), 'a');

4.9

var BST = require('./../util/BST');

var bstSequences = function(bst) {
  var sequences = [];
  var recurse = function(nodes, travelled) {
    var noChild = true;
    nodes.forEach((node) => {
      if (node.left !== null && travelled[node.left.value] === undefined) {
        noChild = false;
        travelled[node.left.value] = true;
        recurse(nodes.concat([node.left]), travelled);
        delete travelled[node.left.value];
      }
      if (node.right !== null && travelled[node.right.value] === undefined) {
        noChild = false;
        travelled[node.right.value] = true;
        recurse(nodes.concat([node.right]), travelled);
        delete travelled[node.right.value];
      }
    });
    if (noChild) {
      sequences.push(nodes.map(node => node.value));
    }
  };
  var startTravelled = {};
  startTravelled[bst.value] = true;
  recurse([bst], startTravelled);
  return sequences;
};

/* TEST */

/* 1, 2, 3, 4, 5, 6, 7 */

var b = new BST(4);
b.insert(2);
b.insert(6);
b.insert(1);
b.insert(3);
b.insert(5);
b.insert(7);

console.log(bstSequences(b));