這是什麼？

延續昨天的話題，Binary Tree 是 Tree 的約束版本，限制每個節點的子節點數量（最多左右兩個子節點），避免記憶體過度浪費。

用 Array 實作

基本上，不太建議用 Array 實作，根本原因在於 Tree 屬於 Linked List 的衍生家族。如果是數量固定的情況下，用 Array 是可以實踐的。最常見的應用是前幾天介紹的 Heap Sort，利用 Tree 的特性進行 Sort。

來源

JS

/**
 * @param {number[]} tree
 * @param {number} root
 */
const root = (tree, root) => {
  if (tree[0] !== null) {
    console.log("Tree already has root");
  } else {
    tree[0] = root;
  }
};

/**
 * @param {number[]} tree
 * @param {number} key
 * @param {number} parent
 */
const setLeft = (tree, key, parent) => {
  if (tree[parent] === null) {
    console.log(`Can't set child at ${(parent * 2) + 1}, no parent found`);
  } else {
    tree[(parent * 2) + 1] = key;
  }
};

/**
 * @param {number[]} tree
 * @param {number} key
 * @param {number} parent
 */
const setRight = (tree, key, parent) => {
  if (tree[parent] === null) {
    console.log(`Can't set  child at ${(parent * 2) + 2}, no parent found`);
  } else {
    tree[(parent * 2) + 2] = key;
  }
};

/**
 * @param {number[]} tree
 */
const printTree = (tree) => {
  let resultMessage = '';

  for (let i = 0; i < tree.length; i++) {
    if (tree[i] !== null) {
      resultMessage += tree[i];
    } else {
      resultMessage += '-';
    }
  }

  console.log(resultMessage);
};

let arr = new Array(10);
arr.fill(null);

root(arr, 'A');
setLeft(arr, 'B', 0);
setRight(arr, 'C', 0);
setLeft(arr, 'D', 1);
setRight(arr, 'E', 1);
setLeft(arr, 'F', 2);
printTree(arr);

Java

public class BinaryTreeByArray {
    public static void main(String[] args) {
        ArrayImplement arr = new ArrayImplement();
        arr.Root("A");
        arr.setLeft("B", 0);
        arr.setRight("C", 0);
        arr.setLeft("D", 1);
        arr.setRight("E", 1);
        arr.setLeft("F", 2);
        arr.printTree();
    }
}

public class ArrayImplement {
    static int root = 0;
    static String[] str = new String[10];

    public void Root(String key) {
        str[0] = key;
    }

    public void setLeft(String key, int root) {
        int t = (root * 2) + 1;

        if (str[root] == null) {
            System.out.printf("Can't set child at %d, no parent found\n", t);
        } else {
            str[t] = key;
        }
    }

    public void setRight(String key, int root) {
        int t = (root * 2) + 2;

        if (str[root] == null) {
            System.out.printf("Can't set child at %d, no parent found\n", t);
        } else {
            str[t] = key;
        }
    }

    public void printTree() {
        for (int i = 0; i < 10; i++) {
            if (str[i] != null) {
                System.out.print(str[i]);
            } else {
                System.out.print("-");
            }
        }
    }
}

C

#include <stdio.h>
#include <stdlib.h>

void root(char *tree, char root)
{
    if (tree[0] != '\0')
    {
        printf("Tree already has root\n");
    }
    else
    {
        tree[0] = root;
    }
}

void set_left(char *tree, char key, int parent)
{
    if (tree[parent] == '\0')
    {
        printf("Can't set child at %d, no parent found\n", (parent * 2) + 1);
    }
    else
    {
        tree[(parent * 2) + 1] = key;
    }
}

void set_right(char *tree, char key, int parent)
{
    if (tree[parent] == '\0')
    {
        printf("Can't set child at %d, no parent found\n", (parent * 2) + 2);
    }
    else
    {
        tree[(parent * 2) + 2] = key;
    }
}

void print_tree(char *tree, int tree_size)
{
    int i;

    for (i = 0; i < 10; i++)
    {
        if (tree[i] != '\0')
        {
            printf("%c", tree[i]);
        }
        else
        {
            printf("-");
        }
    }
}

int main()
{
    char tree[10];
    root(tree, 'A');
    set_left(tree, 'B', 0);
    set_right(tree, '0', 0);
    set_left(tree, 'D', 1);
    set_right(tree, 'E', 1);
    set_left(tree, 'F', 2);
    print_tree(tree, 10);
    return 0;
}

搜尋節點的方式 - Traversal

因為 Binary Tree 每個節點有兩個選擇：向左、向右，那如何拜訪每一個節點，就成為一個問題。目前有三種走法

• Inorder（中序）：左->中->右 or B->A->C
• Preorder（前序）：中->左->右 or A->B->C
• Postorder（後序）：左->右->中 or B->C->A

出個複雜題目

三種走法的順序分別是：

• Inorder: D->B->E->A->H->F->C->I->G->J
• Preorder: A->B->D->E->C->F->H->G->I->J
• Postorder: D->E->B->H->F->I->J->G->C->A

用 JS 實作

const inorder = (node) => {
  if (node !== null) {
    inorder(node.left);
    console.log(node.val);
    inorder(node.right);
  }
};

const preorder = (node) => {
  if (node !== null) {
    console.log(node.val);
    preorder(node.left);
    preorder(node.right);
  }
};

const postorder = (node) => {
  if (node !== null) {
    postorder(node.left);
    postorder(node.right);
    console.log(node.val);
  }
};

用 Java 實作

public void inorder(BinaryTree Node) {
    if (Node != null) {
        inorder(Node.left);
        System.out.print(Node.val);
        inorder(Node.right);
    }
}

public void preorder(BinaryTree Node) {
    if (Node != null) {
        System.out.print(Node.val);
        preorder(Node.left);
        preorder(Node.right);
    }
}

public void postorder(BinaryTree Node) {
    if (Node != null) {
        postorder(Node.left);
        postorder(Node.right);
        System.out.print(Node.val);
    }
}

用 C 實作

void inorder(BinaryTree tree)
{
    if (tree != NULL)
    {
        inorder(tree->left);
        printf("%d", tree->val);
        inorder(tree->right);
    }
}

void preorder(BinaryTree tree)
{
    if (tree != NULL)
    {
        printf("%d", tree->val);
        preorder(tree->left);
        preorder(tree->right);
    }
}

void postorder(BinaryTree tree)
{
    if (tree != NULL) {
        postorder(tree->left);
        postorder(tree->right);
        printf("%d", tree->val);
    }
}

刷題：94. Binary Tree Inorder Traversal

題目

連結

Given the root of a binary tree, return the inorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]

Constraints:

* The number of nodes in the tree is in the range [0, 100].
* -100 <= Node.val <= 100

思考

這題只是考會不會 Inorder 的觀念。

解題

JS

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
const inorderTraversal = (root) => {
  let output = [];
  helper(root, output);
  return output;
};

/**
 * @param {TreeNode} root
 * @param {number[]} output
 */
const helper = (root, output) => {
  if (root !== null) {
    helper(root.left, output);
    output.push(root.val);
    helper(root.right, output);
  }
};

Java

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> output = new ArrayList<Integer>();
        helper(root, output);
        return output;
    }

    public void helper(TreeNode root, List<Integer> output) {
        if (root != null) {
            helper(root.left, output);
            output.add(root.val);
            helper(root.right, output);
        }
    }
}

C

void helper(struct TreeNode *root, int *output, int *index)
{
    if (root != NULL)
    {
        helper(root->left, output, index);
        output[(*index)++] = root->val;
        helper(root->right, output, index);
    }
}

int *inorderTraversal(struct TreeNode *root, int *returnSize)
{
    *returnSize = 0;
    int *output = malloc(sizeof(int) * 100);
    helper(root, output, returnSize);
    return output;
}

看法

C 的處理比較麻煩，在於 Array 的長度，參考題目的限制，直接宣告一個長度為 100 的 Array 會比較好處理。再來用 returnSize 控制目前陣列的 index。

缺點很明顯，佔用過多的記憶體空間，有著優化的空間。

有了 Inorder，當然也有 Preorder & Postorder 的考題：

• 144. Binary Tree Preorder Traversal
• 145. Binary Tree Postorder Traversal

解法跟這題幾乎一樣，只要調整什麼時候要 push 即可。

結論

礙於時間有限，今天先講解一下 Binary Tree 的基本概念，明天則要關注在新增、移除節點的方法。