DinS          Written on 2017/4/27

1. Visually, what is a binary tree(二叉树)?

See featured image above.

Unlike vector and list, tree is a semi-linear structure(半线性结构). In binary tree, each tree node has a parent pointer, a left child pointer, a right child pointer and real data. Tree nodes interconnect through these pointers to form a tree. We can also think several nodes form a subtree, and subtrees together form a whole tree.

Binary tree has a huge family. The most fundamental one is just binary tree. An improved one is binary search tree (B.S.T.); it can guarantee O(height) for search, insert and delete operations. An still improved one is balanced binary search tree (B.B.S.T.); it can control the height of tree to O(logn), thus guarantee O(logn) for search, insert and delete operations. In this page I’ll just discuss basic operations for binary tree.

2. Add and remove a tree node

This operation is similar to adding and removing a list node in list. It’s all about rewire.

First we have an existing tree node and a new tree node.

Second we rewire the parent of the new node to point to existing node, and the left child of existing node to point to the new node.

3. Preorder traversal(先序遍历)

Traversal is an important operation in tree. Since tree doesn’t have a natural order, we need to make a rule of order. Preorder traversal follows this order of visit: root(V) -> left child(L) -> right child(R).

Using recursive method we can easily come up with these pseudo codes:

|    travPre (treenode, visit)

|    {

|             if (!Exist(treenode)) return

|             visit(treenode->data)

|             travPre (treenode->lc, visit)

|             travPre (treenode->rc, visit)

|    }

A more general picture looks like this:

4. Postorder traversal(后序遍历)

Preorder traversal follows this order of visit: left child(L) -> right child(R) -> root(V).

Pseudo codes:

|    travPost (treenode, visit)

|    {

|             if (!Exist(treenode)) return

|             travPost (treenode->lc, visit)

|             travPost (treenode->rc, visit)

|             visit(treenode->data)

|    }

A more general picture looks like this:

5. Inorder traversal(中序遍历)

Inorder traversal follows this order of visit: left child(L) -> root(V) -> right child(R).

Pseudo codes:

|    travIn (treenode, visit)

|    {

|             if (!Exist(treenode)) return

|             travIn (treenode->lc, visit)

|             visit(treenode->data)

|             travIn (treenode->rc, visit)

|    }

A more general picture looks like this:

6. Level-order traversal(层次遍历)

The order of this traversal can be summarized as “from top to bottom, from left to right”.

A general picture looks like this:

Using a queue we can easily accomplish this goal.

Pseudo codes:

|    travLevel (treenode, visit)

|    {

|             Queue Q

|             Q.enqueue(treenode)

|             while(!Q.empty())

|             {

|                      x= Q.dequeue

|                       visit(x->data)

|                       if (hasLeftChild(x)) Q.enqueue(x->lc)

|                       if (hasRightChild(x)) Q.enqueue(x->rc)

|             }

|    }