原题如下:

(1) Prove that for any nonempty binary tree, n0 = n2 + 1 where n0 is the number of leaf nodes and n2 the number of nodes of degree 2.

(2) Using linked representation following to create a binary tree. The program you implemented should accept the data to ‘data’ field from input.

typedef struct node *tree_ptr;

typedef struct node

{

int data;

tree_ptr left_child,right_child;

}

Implement the program of inorder traversal, preorder traversal and postorder traversal. And analyze their time complexity.

(3) Consider a message comprised only of the following symbols: {C, A, T, P}, assume message is: CCT PAT TTP CTP CPA, use the Huffman algorithm to encode the symbols by frequency.Implement the program to create this tree.

滴水之恩 当泉涌相报