树

树结点的定义：

1 struct TreeNode
2 {
3     ElementType data;                       // 树结点的数据元素域
4     struct TreeNode *subtree[TREEDEGREE];   // TREEDEGREE为已知的树的度，subtree[index]为指向孩子的指针
5 };

遍历操作：

 1 /*
 2  * 先根遍历
 3  */
 4 void preorderTraverse(struct TreeNode *root)
 5 {
 6     if(root != NULL) {                                      // 若树空则返回
 7         print(root->data);                                  // 访问根结点数据域
 8         for(int index = 0; index < TREEDEGREE; ++index)     // 从左到右依次先根遍历各棵子树
 9             preorderTraverse(root->subtree[index]);
10     }
11 }
12 
13 /*
14  * 后根遍历
15  */
16 void postorderTraverse(struct TreeNode *root)
17 {
18     if(root != NULL) {                                      // 若树空则返回
19         for(int index = 0; index < TREEDEGREE; ++index)     // 从左到右依次后根遍历各棵子树
20             postorderTraverse(root->subtree[index]);
21         print(root->data);                                  // 访问根结点数据域
22     }
23 }
24 
25 /*
26  * 层序遍历
27  */
28 void levelorderTraverse(struct TreeNode *root)
29 {
30     Queue queue;                                            // 定义一个队列
31     initQueue(queue);                                       // 初始化队列
32     if(root != NULL)                                        // 若根结点不空，则将根结点入队
33         enQueue(queue, root);
34     while(!isEmpty(queue)) {                                /* 若队列不空，则继续循环 */
35         struct TreeNode temp = outQueue(queue);             // 队头元素出队列
36         print(temp->data);                                  // 输出刚出队列的结点的数据
37         for(int index = 0; index < TREEDEGREE; ++index)     // 将刚出队列的结点的子树的根结点入队
38             if(root->subtree[index] != NULL)
39                 enQueue(queue, root->subtree[index]);
40     }
41 }

树的简单应用：

 1 /*
 2  * 统计树的结点数
 3  */
 4 int countTreeNodes(struct TreeNode *root) 
 5 {
 6     static int count = 0;                                       // 全局变量count用于统计树的结点数
 7     if(root == NULL) {                                          // 若树根结点root为空，则返回0
 8         return 0;
 9     } else {                                                    // 若树根结点root不为空，则循环递归统计该树的结点数
10         for(int index = 0; index < TREEDEGREE; ++index)
11             count += countTreeNodes(root->subtree[index]);
12         return count + 1;                     　　// 此处需要加 1 ，是因为count此时只统计了root的子树的结点数，并未包括root这一结点
13     }
14 }
15 
16 /*
17  * 计算树的深度
18  */
19 int countTreeDeepth(struct TreeNode *root)
20 {
21     if(root == NULL) {                                          // 若树空，则返回深度0
22         return 0;
23     } else {                                                    // 若树不空则先分别计算出各棵子树的深度，并求出其最大值
24         int maxDeepth = 0;
25         for(int index = 0; index < TREEDEGRE; ++index) {
26             int deepth = countTreeDeepth(root->[index]);
27             if(deepth > maxDeepth)
28                 maxDeepth = deepth;
29         }
30         return maxDeepth + 1;
31     }
32 }
33 
34 /*
35  * 清除树结构
36  */
37 void clearTree(struct TreeNode *root)
38 {
39     if(root != NULL) {                                          // 若树不为空，则需清除树结构
40         for(int index = 0; index < TREEDEGREE; ++index)         // 循环递归清除root的各棵子树
41             clearTree(root->[index]);
42         delete root;                                            // 释放root占用的内存空间
43         root = NULL;                                            // root指针变量置空
44     }
45 }

OK哒！O(∩_∩)O哈！