Content
目录#

• Binary Trees
  二叉树
• Recursive techniques with trees
  基于树的递归技术
• Traversals
  遍历

What is a Tree (Graph Theory)?
什么是树（图论）#

• In graph theory, a tree is an undirected graph that contains no cycles (i.e. no paths that take you back to the node on which you started).
  在图论中，树是一种不包含环的无向图（即不存在一条路径能让你回到起始节点）。

What is a Tree (Computer Science)?
什么是树（计算机科学）#

• In computer science we generally think of trees as being rooted trees.
  在计算机科学中，我们通常讨论的是有根树。
  • One node is designated as the root.
    其中一个节点被指定为根节点。
  • The nodes adjacent to it are the roots of its subtrees
    与其相邻的节点分别是其子树的根。

Example#

Binary trees
二叉树#

• Binary trees have two sub-trees:
  二叉树有两个子树：

Which is Binary tree?
哪个是二叉树？

Basic Terminology for Binary Trees
二叉树基础术语#

Terminology 术语

Root: 根节点

Left-subtree: 左子树

Right-subtree: 右子树

leaves: 叶子节点

How do we represent binary trees?
如何表示二叉树呢？#

• A (binary) tree is
  （二叉）树可以定义为：
  • either empty, 
    要么是空树，
  • or consists of a node, containing some data, along with references to two sub-trees, known as the left and right sub trees. 
    要么由一个包含数据的节点组成，并带有指向两棵子树的引用，分别称为 left 和 right 子树。

⬆️
Note the recursive definition.
注意这个递归定义。

Represent Binary Trees of Integers
用整数表示二叉树#

1
public class BinaryTree {
2
    public Member data;
3
    public BinaryTree left; //null if there is no left subtree
4
    public BinaryTree right; //null if there is no right subtree
5
    public BinaryTree(Member val) {
6
        data = val;
7
        left = null;
8
        right = null;
9
    }
10
}
11
BinaryTree t;
12
// A tree can be represented by a reference to its root.
13
// This reference is null if the tree is empty.

Recursive Tree Algorithms
递归树算法#

Since trees are defined recursively, it is often simplest to process them using recursive algorithms. Here is an example:
由于树本身是递归定义的，通常使用递归算法处理它最简单。示例如下：

1
/** Count the number of nodes in a binary tree **/
2
public static int count(BinaryTree t) {
3
    if (t == null) {
4
        return 0;
5
    } else {
6
        return 1 + count(t.left) + count(t.right);
7
    }
8
}

Traversals
遍历#

Traverse 遍历

• A traversal is a systematic way of going through all the data in a data structure.
  遍历是系统化地访问数据结构中全部数据的一种方式。
• So, for example, for a list of type ArrayList<String>, this is a traversal:
  例如，对于 ArrayList<String> 类型的列表，下面就是一次遍历：

1
for (String s : list) {
2
    // makes s successively each value in list
3
    ............
4
}

• For trees there are several traversals, including:
  对树而言，常见遍历方式包括：
  • pre-order traversal
    先序遍历
  • in-order traversal
    中序遍历
  • post-order traversal
    后序遍历

1
public static void preOrderTraversal(BinaryTree t) {
2
    if (t != null) {
3
        System.out.println(t.data);
4
        preOrderTraversal(t.left);
5
        preOrderTraversal(t.right);
6
    }
7
}

1
public static void inOrderTraversal(BinaryTree t) {
2
    if (t != null) {
3
        inOrderTraversal(t.left);
4
        System.out.println(t.data);
5
        inOrderTraversal(t.right);
6
    }
7
}

1
public static void postOrderTraversal(BinaryTree t) {
2
    if (t != null) {
3
        postOrderTraversal(t.left);
4
        postOrderTraversal(t.right);
5
        System.out.println(t.data);
6
    }
7
}

Requirements for this week
本周学习要求#

You should achieve by the end of this week’s work:
完成本周学习后，你应当能够：

• understand binary trees
  理解二叉树
• able to store data in binary trees
  能够在二叉树中存储数据
• understand pre-order, post-order and in-order traversals on binary trees
  理解二叉树的先序、后序和中序遍历
• able to write recursive functions on trees.
  能够在树结构上编写递归函数。

A Binary Search Tree
二叉搜索树示例#

• This is an example of Binary Search Tree
  这是一个二叉搜索树示例。
• What property does it have that makes it a binary tree?
  它具备什么性质使它成为二叉树？
• What additional property does it have?
  它还具备什么额外性质？
• Why might that property be useful?
  这个额外性质为什么有用？

Binary Search Trees
二叉搜索树#

• These are a special kind of binary tree
  它是二叉树的一种特殊类型。
  • the data they contain must be a comparable type (where you can do <, >, ==, .equals comparisons), e.g. int, char, String
    (.compareTo)
    其中存储的数据必须是可比较类型（可进行 <、>、==、.equals 比较），如 int、char、String（可用 .compareTo）。
  • The data at the root node is greater than all the data in the left subtree
    根节点数据大于左子树中所有数据
  • The data at the root node is less than all data in the right subtree
    根节点数据小于右子树中所有数据
  • … and so on, all the way down the tree (recursive definition)
    该性质在整棵树上递归成立（递归定义）

• Usually binary search trees represent a set of values
  二叉搜索树通常表示一组集合值。
  • there are no duplicate values in the tree
    树中没有重复值
  • Of course, any binary search tree is also a binary tree
    当然，任何二叉搜索树也都是二叉树

Invented by P.F. Windley, A.D. Booth, A.J.T. Colin, and T.N. Hibbard in 1960 (Wikipedia)
由 P.F. Windley、A.D. Booth、A.J.T. Colin 和 T.N. Hibbard 于 1960 年提出（Wikipedia）。

Is this a Binary Search Tree?
这是二叉搜索树吗？#

Datatype Invariants
数据类型不变式#

• A datatype invariant is a property of an abstract data type which holds for all objects of that type.
  数据类型不变式是某个抽象数据类型中对所有对象都成立的性质。
• The datatype invariant for binary search trees is:
  二叉搜索树的数据类型不变式是：
  • The data at the root node is greater than all the data in the left sub-tree
    根节点数据大于左子树所有数据
  • The data at the root node is less than all the data in the right sub-tree
    根节点数据小于右子树所有数据
  • … and so on, all the way down the tree
    该性质在整棵树中逐层递归成立
  • no duplicate values in the tree - so any implementation of such a tree is also an implementation of the concept of a set with operations union-with-singleton and membership.
    树中无重复值，因此这类树本质上也实现了集合概念（支持单元素并集与成员判断）。

A Search Tree class (for integers)
一个搜索树类（用于整数）#

1
public class SearchTree {
2
    public int data; // or whatever
3
    public SearchTree left;
4
    public SearchTree right;
5
    // Reminder:
6
    // reference-type fields are initialized to null by default.
7
    public SearchTree(int data) {
8
        this.data = data;
9
    }
10
}

Insertion into a Search Tree
插入到搜索树中#

1
public SearchTree insert( SearchTree tree, int val) {
2
    if (tree == null) {
3
        tree = new SearchTree(val);
4
    } else if (val > tree.data) {
5
        tree.right = insert(tree.right, val);
6
    } else if (val < tree.data) {
7
        tree.left = insert(tree.left, val);
8
    } // do nothing -- val is already in tree
9
  return tree;
10
}

Does it use recursive method?
它是否使用了递归方法？

What is the base case?
它的递归基线条件是什么？

1
public SearchTree insert( SearchTree tree, int val) {
2
    if (tree == null) {
3
        tree = new SearchTree(val);
4
    } else if (val > tree.data) {
5
        tree.right = insert(tree.right, val);
6
    } else if (val < tree.data) {
7
        tree.left = insert(tree.left, val);
8
    }
9
  return tree;
10
}

1
public SearchTree insert( SearchTree tree, int val) {
2
    if (tree == null) {
3
        tree = new SearchTree(val);
4
    } else if (val > tree.data) {
5
        tree.right = insert(tree.right, val);
6
    } else if (val < tree.data) {
7
        tree.left = insert(tree.left, val);
8
    }
9
  return tree;
10
}

1
public SearchTree insert( SearchTree tree, int val) {
2
    if (tree == null) {
3
        tree = new SearchTree(val);
4
    } else if (val > tree.data) {
5
        tree.right = insert(tree.right, val);
6
    } else if (val < tree.data) {
7
        tree.left = insert(tree.left, val);
8
    }
9
  return tree;
10
}

1
public SearchTree insert( SearchTree tree, int val) {
2
    if (tree == null) {
3
        tree = new SearchTree(val);
4
    } else if (val > tree.data) {
5
        tree.right = insert(tree.right, val);
6
    } else if (val < tree.data) {
7
        tree.left = insert(tree.left, val);
8
    }
9
  return tree;
10
}

1
public SearchTree insert( SearchTree tree, int val) {
2
    if (tree == null) {
3
        tree = new SearchTree(val);
4
    } else if (val > tree.data) {
5
        tree.right = insert(tree.right, val);
6
    } else if (val < tree.data) {
7
        tree.left = insert(tree.left, val);
8
    }
9
  return tree;
10
}

1
public SearchTree insert( SearchTree tree, int val) {
2
    if (tree == null) {
3
        tree = new SearchTree(val);
4
    } else if (val > tree.data) {
5
        tree.right = insert(tree.right, val);
6
    } else if (val < tree.data) {
7
        tree.left = insert(tree.left, val);
8
    }
9
  return tree;
10
}

1
public SearchTree insert( SearchTree tree, int val) {
2
    if (tree == null) {
3
        tree = new SearchTree(val);
4
    } else if (val > tree.data) {
5
        tree.right = insert(tree.right, val);
6
    } else if (val < tree.data) {
7
        tree.left = insert(tree.left, val);
8
    }
9
  return tree;
10
}

1
public SearchTree insert( SearchTree tree, int val) {
2
    if (tree == null) {
3
        tree = new SearchTree(val);
4
    } else if (val > tree.data) {
5
        tree.right = insert(tree.right, val);
6
    } else if (val < tree.data) {
7
        tree.left = insert(tree.left, val);
8
    }
9
  return tree;
10
}

1
public SearchTree insert( SearchTree tree, int val) {
2
    if (tree == null) {
3
        tree = new SearchTree(val);
4
    } else if (val > tree.data) {
5
        tree.right = insert(tree.right, val);
6
    } else if (val < tree.data) {
7
        tree.left = insert(tree.left, val);
8
    }
9
  return tree;
10
}

1
public SearchTree insert( SearchTree tree, int val) {
2
    if (tree == null) {
3
        tree = new SearchTree(val);
4
    } else if (val > tree.data) {
5
        tree.right = insert(tree.right, val);
6
    } else if (val < tree.data) {
7
        tree.left = insert(tree.left, val);
8
    }
9
  return tree;
10
}

1
public SearchTree insert( SearchTree tree, int val) {
2
    if (tree == null) {
3
        tree = new SearchTree(val);
4
    } else if (val > tree.data) {
5
        tree.right = insert(tree.right, val);
6
    } else if (val < tree.data) {
7
        tree.left = insert(tree.left, val);
8
    }
9
  return tree;
10
}

Searching a Search Tree
搜索一个搜索树#

1
public static boolean contains(SearchTree tree, int val) {
2
    if (tree == null) {
3
        return false;
4
    } else if (val > tree.data) {
5
        return contains(tree.right, val);
6
    } else if (val < tree.data) {
7
        return contains(tree.left, val);
8
    } else { // tree.data==val
9
        return true;
10
    }
11
}

Does it use recursive method?
它是否使用了递归方法？

What is the base case?
它的递归基线条件是什么？

Exercise#

• Sketch out the tree that would be produced by inserting the values 4, 5, 10, 25, 39 in that order, using the insert method shown earlier.
  使用前面给出的 insert 方法，按顺序插入 4、5、10、25、39，画出最终生成的树。
• Using the search method shown earlier, how many method calls do you need to make in order to find out whether 39 is in the resulting tree?
  使用前面的查找方法，要判断结果树中是否存在 39，需要调用多少次方法？
• How many method calls do you need to make to find out whether 100 is in the tree?
  若判断 100 是否在树中，需要调用多少次方法？

Special situation with binary search trees
二叉搜索树的特殊情况#

If a tree
is lopsided,
a search can still
take up to n steps,
for a tree with n nodes.
Said to have degenerated into a linked list.
如果一棵树
是偏斜的，
那么查找仍可能
需要最多 n 步，
（对于有 n 个节点的树）。
这种情况称为退化为链表。

Best to make the class contain a tree, not be one
最好让类“包含”一棵树，而不是“本身就是”一棵树#

• Make a class BinarySearchTree contain a class Node.
  让 BinarySearchTree 类内部“包含” Node 类。
• BinarySearchTree can then have as fields:
  BinarySearchTree 可包含如下字段：
  • root - a Node
    root - 一个节点引用
  • numEntries - an integer
    numEntries - 整数计数

A Search Tree class (for integers)
一个搜索树类（用于整数）#

1
public class BinarySearchTree {
2

3
    private class Node {
4
        private int data;
5
        private Node left;
6
        private Node right;
7

8
        public Node(int data) {
9
            this.data = data;
10
        }
11
    }
12

13
    private Node root;
14
    private int numEntries;
15

16
    public BinarySearchTree() {
17
        root = null;
18
        numEntries = 0;
19
    }
20
…

1
public Node addNode(Node tree, int val) {
2
    if (tree == null) {
3
        tree = new Node(val);
4
    } else if (val > tree.data) {
5
        tree.right = addNode(tree.right, val);
6
    } else if (val < tree.data) {
7
        tree.left = addNode(tree.left, val);
8
    } // val is already in tree; take action
9
    return tree;
10
}

1
public void insert (int val) {
2
    root = addNode(root, val);
3
    numEntries++;
4
} // BinarySearchTree.insert

1
public void addNode(int key, String name) { // does not use recursive way
2
    Node p, parent;
3
    p = root;
4
    while (p != null && p.key != key) {
5
        parent = p;
6
        if (key < p.key) p = p.left; else p = p.right;
7
    }
8
    if (p == null) {
9
        Node newNode = new Node(key, name);
10
        if (p == root) root = newNode;
11
        else if (p == parent.left) parent.left = newNode;
12
        else parent.right = newNode;
13
        numEntries++;
14
    }
15
    else // p != null - duplicate node detected! Take appropriate action
16
}

1
public void insert (int val) {
2
    addNode(val);
3
} // BinarySearchTree.insert

Perfectly balanced trees
完全平衡树#

A perfectly balanced tree with $2^{(k+1)} - 1$ nodes, will have $depth \times (height)~k$ so searches take at most $k$ steps
对于一个包含 $2^{(k+1)} - 1$ 个节点的完全平衡树，其深度（高度）为 $k$，因此查找最多只需 $k$ 步。

• The depth of a tree defined to be
  树的深度定义为：
  • the length of the longest path from the root to a leaf,
    从根到叶子最长路径的长度；
  • so a tree consisting only of the root node has a depth of 0.
    因此只有根节点的树深度为 0；
  • The depth of an empty tree can be taken to be -1.
    空树深度可定义为 -1。

A perfectly balanced tree
一棵完全平衡树

For n nodes, searches take no more than $\underline{\textcolor{red}{(1 + log~n)}}$ steps.
对于 n 个节点，查找步数不超过 $\underline{\textcolor{red}{(1 + log~n)}}$。

• This is described as a $\textcolor{red}{O(log~n)}$ algorithm and it is a lot faster than an algorithm with $n$ steps, which would be $O(n)$.
  这被称为 $\textcolor{red}{O(log~n)}$ 级别算法，明显快于需要 $n$ 步的 $O(n)$ 算法。

Self-balancing trees
自平衡树#

• A balanced tree offers better access time, but re-balancing a tree takes time, so it is a trade-off.
  平衡树查询更快，但维护平衡本身也需要成本，这是一种权衡。
• This has led to a variety of engineering solutions for self-balancing trees.These include:
  因此工程上出现了多种自平衡树方案，包括：
  • “AVL” trees: G. M. Adelson-Velskii and E. M. Landis, 1962
    “AVL 树”：G. M. Adelson-Velskii 与 E. M. Landis（1962）
  • “Red-black” trees: Rudolf Bayer (1972).
    “红黑树”：Rudolf Bayer（1972）
  • “Symmetric binary B-Trees: Data structure and maintenance algorithms”. Acta Informatica. 1 (4): 290-306
    “对称二叉 B 树：数据结构与维护算法”，发表于 Acta Informatica 1(4): 290-306

TreeMap#

• The provided Java collection class TreeMap implements the interface Map.
  Java 提供的集合类 TreeMap 实现了 Map 接口。
• It uses a Red-Black tree and offers $\textcolor{red}{O(log~n)}$ access time.
  它基于红黑树，访问复杂度为 $\textcolor{red}{O(log~n)}$。
  • Note: HashMap can offer $\textcolor{orange}{O(1)}$ access time.
    注意：HashMap 访问可达 $\textcolor{orange}{O(1)}$ 级别。
• But it is possible to iterate through a TreeMap accessing the values in order; this is not possible with a HashMap.
  但 TreeMap 可以按有序顺序迭代访问值，而 HashMap 通常无法做到这一点。

Access Time
访问时间#

• Searching is faster in a binary search tree, just as binary search in a sorted array is faster than linear search.
  在二叉搜索树中查找通常更快，正如有序数组中的二分查找快于线性查找。
• There is a trade-off: cost of keeping tree balanced versus cost of searches.
  存在权衡：维护平衡的代价与查找代价之间需要取舍。
• It is easy to sort numbers using a binary search tree - why and how?
  用二叉搜索树做排序很自然，为什么？怎么做？

Requirements#

• What you want to achieve by the end of this week’s work:
  本周结束时你应达成：
  • understand binary trees
    理解二叉树
  • understand binary search trees
    理解二叉搜索树
  • know the difference!
    明确两者差异
  • be able to write recursive functions on trees.
    能在树结构上编写递归函数