27.txt

一個計算機系教授的上課講義 主要是教導學生使用C語言編寫程序

CS 1355
Introduction to Programming in C
Monday 2006.12.18
Lecture notes (at http://r638-2.cs.nthu.edu.tw/C/notes/27.txt)
Today: Chapter 12 continued, trees (page 490)

Tree data structure

A tree is a recursive data structure.
- usually drawn upside-down
A tree can be
- empty: (no tree)
- single node: (root only)
- a node can have "children"
  - each child is also a tree
- "binary tree": a tree with at most two children
- "ternary tree": a tree with at most three children
- general tree: a tree with any number of children

- A binary tree has (1) a left child and (2) a right child
  either or both children may be null, or can be a whole other tree.

Example: 

  A
 / \     => root at A, children = B, C
B   C

Because a tree is recursive, the right child can actually be a
whole other tree
   A
 /   \
B     C
     /  \
    D    E

For convenience, we use parenthesized syntax instead of drawing trees:
(A, (B, -, -), (C, -, -))
(A, (B, -, -), (C, (D, -, -), (E, -, -)))

How it works:
- every time you see (  => start a new tree
                     )  => end a tree, go up one level
- each () pair contains root, left-child, right-child

How to represent a binary tree data structure?
two ways:
- use separate arrays to keep track of 
  - "key" (the data)
  - left child
  - right child
  (optionally, can keep track of the parent, but not required)
- array is identified by its index
  0 .. N-1 
  -1 as a "nil" or "null" value

Example
#define MAX 20
#define NIL -1
typedef int Tree;
typedef char* Key;

Key  key[MAX] = {""};
Tree left[MAX] = {NIL, NIL, NIL, ...};
Tree right[MAX] = {NIL, NIL, NIL, ...};

Tree
MakeNewNode(Key k, Tree l, Tree r) {
	static n = 0;
	if (n >= MAX) {
		return NIL;
	}
	key[n] = strcpy(malloc(strlen(k)+1), k);
	left[n] = l;
	right[n] = r;
	return n++;
}

----- so, you can make trees this way:
Tree root = MakeNewNode("A", NIL, NIL),
     l = MakeNewNode("B", NIL, NIL);
     r = MakeNewNode("C", NIL, NIL);
     left[root] = l;
     right[root] = r;

Or, a more compact way to say this is simply

Tree root = MakeNewNode("A", MakeNewNode("B", NIL, NIL), 
				MakeNewNode("C", NIL, NIL));

You could also manually initialize the tree
Key key[MAX] = { "A", "B", "C",  };
Tree left[MAX] = { 1, NIL, NIL, };
Tree right[MAX] = { 2, NIL, NIL, };

-------
"Traversal"
Given a tree data structure, you can "traverse" ("visit")
the tree nodes. How??

- pre-order:  root, left-recursively, right-recursively
- in-order:   left-recursively, root, right-recursively
- post-order ("depth-first"):  left-recursively, right-recursively, root
- breadth-first (increasing-depth order): root, 1-deep, 2-deep, 3-deep, ...

Example:
      A
    /   \
   B     C
 /  \   /  \
D    E F    G

- pre-order:     A, B, D, E, C, F, G
- in-order:      D, B, E, A, F, C, G
- post-order:    D, E, B, F, G, C, A
- breadth-order: A, B, C, D, E, F, G

(annotated with parentheses:
- pre-order: root=A, 
             left=(root=B, left=(D), right=(E)), 
             right=(root=C, left=(F), right=(G))

- in-order:  left=(left=(D), root=B, right=(E)),
             root=A,
             right=(left=(F), root=C, right=(G))

- post-order: left=(left=(D), right=(E), root=B),
              right=(left=(F), right=(G), root=C),
              root=A

- breadth-order: 
  depth 1: A
  depth 2: B, C
  depth 3: D, E, F, G

Algorithms for different traversal order:

void PreOrder(Tree t) {
	if (t == NIL) {
		return;
	}
	printf("%s ", key[t]); /* root first */
	PreOrder(left[t]);     /* left recursively */
	PreOrder(right[t]);    /* right recursively */
}

void InOrder(Tree t) {
	if (t == NIL) {
		return;
	}
	InOrder(left[t]);
	printf("%s ", key[t]);
	InOrder(right[t]);
}

void PostOrder(Tree t) {
	if (t == NIL) {
		return;
	}
	PostOrder(left[t]);
	PostOrder(right[t]);
	printf("%s ", key[t]);
}

How to print trees in the parenthesized syntax?
 (A, (B, (D, -, -), (E, -, -)), (C, (F, -, -), (G, -, -)))

- start a new tree: (
- end a tree: )
- nil: print -
- use comma to separate
- print using pre-order

void ParenTree(Tree t) {
	if (t == NIL) {
		printf("-");
		return;
	}
	printf("(%s, ", key[t]);
	ParenTree(left[t]);
	printf(", ");
	ParenTree(right[t]);
	printf(")");
}

What about breadth-first order?
Answer: need a queue!

struct Queue {
	Tree q[MAX];
	int head, tail;
};

struct Queue Q;

void BreadthOrder(Tree t) {
	Queue q;
	Tree  i;
	q.head = q.tail = 0;
	if (t == NIL) {
		return;
	}
	Enqueue(&q, t);
	while ((i = Dequeue(&q)) != NIL) {
		printf("%s ", key[i]);
		if (left[i] != NIL) {
			Euqueue(&q, left[i]);
		}
		if (right[i] != NIL) {
			Enqueue(&q, right[i]);
		}
	}
}

Why it works:
- initially, enqueue the root (depth = 1)
- every time dequeue, add up to two more nodes of depth = d + 1
  all depth d ones are in the queue before all depth d+1
  by queue order

Applications of a binary tree?
Most common application: binary search tree
- elements are in sorted order for in-order traversal
- insert new elements this way
- dynamic data structure: can add new elements over time

Example tree:
- values: ["A", "D", "F", "H", "K", "N", "Q"]
- there are many binary search trees for this sequence!
  - most balanced version is
    (H, (D, (A, -, -), (F, -, -)), (N, (K, -, -), (Q, -, -)))
  - very imbalanced:
    (A, -, (D, -, (F, -, (H, -, (K, -, (N, -, (Q, -, -)))))))
  - there are many more trees

To Find the node with a given key k
- start from the root:
  - base case: tree is NIL, then return NIL to indicate not found.
  - if the key matches k, then return the node
  - if k is smaller, Find recursively in the left child.
  - if k is larger, Find recursively in the right child.

Tree
Find(Tree root, Key k) {
	int cmpResult;
	if (root == NIL) {
		return NIL;
	}
	cmpResult = strcmp(k, key[root]);
	if (cmpResult == 0) {
		return root;
	}
	if (cmpResult < 0) {
		return Find(left[root], k);
	} else {
		return Find(right[root], k);
	}
}

How to add (insert) a new node with key k
- similar to Find(), 
  - find the spot where the node for k is expected to be but is NIL
  - make a new node with the key k and link to it.

void
Insert(Tree* root, Key k) {
	if (root == NULL) {
		fprintf(stderr, "inserting with null *root\n");
		return;
	}
	if (*root == NIL) {
		/* this is the spot */
		*root = MakeNewNode(k, NIL, NIL);
		return;
	}
	if (strcmp(k, key[*root]) < 0) {
		Insert(&left[*root], k);
	} else {
		Insert(&right[*root], k);
	}
}

Try running it:
(http://r638-2.cs.nthu.edu.tw/C/notes/tree.c)
% ./a.out
insert "hello"
("hello", -, -)
insert "world"
("hello", -, ("world", -, -))
insert "abc"
("hello", ("abc", -, -), ("world", -, -))
insert "efg"
("hello", ("abc", -, ("efg", -, -)), ("world", -, -))
insert "zoology"
("hello", ("abc", -, ("efg", -, -)), ("world", -, ("zoology", -, -)))
insert "radiology"
("hello", ("abc", -, ("efg", -, -)), ("world", ("radiology", -, -), ("zoology", -, -)))
find "world"
found node #1
find "efg"
found node #3
find "chocolate"
key "chocolate" not found
inorder
"abc" "efg" "hello" "radiology" "world" "zoology" 
preorder
"hello" "abc" "efg" "world" "radiology" "zoology" 
postorder
"efg" "abc" "radiology" "zoology" "world" "hello" 


--------
Struct representation for tree nodes
- instead of three arrays key[], left[], right[] with the same index,
- use a struct to include key, left, right:

struct treenode {
	char *key;
	struct treenode *left, *right;
};

/* very important: must be *left, *right, not just left, right! 
 * must be pointers
 */

easy translation:
typedef struct treenode *Tree;

Tree
MakeNewNode(Key k, Tree l, Tree r) {
	Tree temp = malloc(sizeof(struct treenode));
	if (temp == NULL) {
		return NULL;
	}
	temp->key = k; /* instead of key[temp] = k */
	temp->left = l; /* intead of left[temp] = l */
	temp->right = r; /* instead of right[temp] = r */
	return temp;
}

void PreOrder(Tree t) { /* struct version */
	if (t == NULL) {
		return;
	}
	printf("%s ", t->key); /* instead of key[t] */
	PreOrder(t->left);     /* instead of left[t] */
	PreOrder(t->right);    /* instead of right[t] */
}

etc

difference: this uses the malloc()/free() way of allocating memory,
instead of managing your own memory using an array.