怎样输出二叉树的所有路径(按字典序)?

 #返回上一级

@Author: 张海拔

@Update: 2014-01-30

@Link: http://www.cnblogs.com/zhanghaiba/p/3536534.html

 

二叉树的路径这里定义为:从树根到叶子的路径。

输出二叉树的所有路径,与“求n的全排列”如出一辙,都是使用回溯法的典范。

 

首先,先屏蔽掉“按字典序”输出的要求,看看怎样输出二叉树的所有路径。

print_all_path()函数,采用深度遍历(也是先序遍历)二叉树,当发现叶子节点意味着找到了一条路径,此时保存叶子的item到path,并输出path[]。

整个函数代码核心是cnt变量,代码要维护cnt,让它始终指向着path数组(可以看做栈)的下一个空闲位置(栈顶)。

所以哪里有回溯(退栈),哪里就需要执行cnt--;,以维护cnt变量。

 

现在,已经可以输出二叉树的所有路径了。

按字典序输出,在DFS选择扩展节点时,分三种情况处理就很清晰了:

若(1)左子树为空,则遍历右子树;

否则若(2)右子树为空,则遍历左子树;

否则(3),即左右子树均不为空,则判断左子树与右子树的根:若左根小则先遍历左子树后遍历右子树,否则先遍历右子树后遍历左子树。

以上面的思路改进print_all_path(),很容易写出print_all_path_dict_order()函数

 

下面的是完整代码实现及测试示范:

怎样输出二叉树的所有路径(按字典序)?
  1 /*
  2  *Author: ZhangHaiba
  3  *Date: 2014-1-30
  4  *File: print_all_path_of_binary_tree.c
  5  *
  6  *a demo shows how to print all path of binary tree in dictionary order
  7  */
  8 
  9 #include <stdio.h>
 10 #include <stdlib.h>
 11 #include <limits.h>
 12 #define LEN 1024
 13 #define CMD_LEN 128
 14 #define MOD 100
 15 
 16 typedef struct node * link;
 17 typedef struct node {
 18     int item;
 19     link left;
 20     link right;
 21 }node;
 22 
 23 
 24 //public
 25 link NODE(int item, link left, link right);
 26 link bt_create_by_random(int n);
 27 void bt_show_by_tree(link root);
 28 void print_all_path(link root);
 29 void print_all_path_dict_order(link root);
 30 
 31 //private
 32 void tree_print(link root, FILE *fd);
 33 link bt_create_by_random_core(int n);
 34 
 35 //private
 36 int path[LEN];
 37 int cnt = 0;
 38 
 39 int main(void)
 40 {
 41     int n;
 42 
 43     scanf("%d", &n);
 44     link bt_tree_a = bt_create_by_random(n);
 45     bt_show_by_tree(bt_tree_a);
 46     printf("print all path in DFS order:\n");
 47     print_all_path(bt_tree_a);
 48     printf("print all path in dictionary order:\n");
 49     print_all_path_dict_order(bt_tree_a);
 50     return 0;
 51 }
 52 
 53 
 54 void print_all_path(link root)
 55 {
 56     if (root == NULL)
 57         return;
 58     if (root->left == NULL && root->right == NULL) {
 59         path[cnt++] = root->item;
 60         int i;
 61         for (i = 0; i < cnt; ++i)
 62             printf(i == cnt-1 ? "%d\n" : "%d ", path[i]);
 63         cnt--;
 64         return;
 65     }
 66     path[cnt++] = root->item;
 67     print_all_path(root->left);
 68     print_all_path(root->right);
 69     cnt--;
 70 }
 71 
 72 void print_all_path_dict_order(link root)
 73 {
 74     if (root == NULL)
 75         return;
 76     if (root->left == NULL && root->right == NULL) {
 77         path[cnt++] = root->item;
 78         int i;
 79         for (i = 0; i < cnt; ++i)
 80             printf(i == cnt-1 ? "%d\n" : "%d ", path[i]);
 81         cnt--;
 82         return;
 83     }
 84     path[cnt++] = root->item;
 85     if (root->left == NULL)
 86         print_all_path_dict_order(root->right);
 87     else if (root->right == NULL)
 88         print_all_path_dict_order(root->left);
 89     else {
 90         if (root->left->item < root->right->item) {
 91             print_all_path_dict_order(root->left);
 92             print_all_path_dict_order(root->right);
 93         } else {
 94             print_all_path_dict_order(root->right);
 95             print_all_path_dict_order(root->left);
 96         }
 97     }
 98     cnt--;
 99 }
100 
101 
102 link NODE(int item, link left, link right)
103 {
104     link born = malloc( sizeof (node) );
105     born->item = item;
106     born->left = left;
107     born->right = right;
108     return born;
109 }
110 
111 link bt_create_by_random(int n)
112 {
113     srand( (unsigned)time(NULL) );
114     return bt_create_by_random_core(n);
115 }
116 
117 link bt_create_by_random_core(int n)
118 {
119     if (n <= 0)
120         return NULL;
121     if (n == 1)
122         return NODE(rand()%MOD, NULL, NULL);
123     link root = NODE(rand()%MOD, NULL, NULL);
124     int left_n = rand()%(n-1)+1, right_n = (n-1) - left_n;
125     root->left = bt_create_by_random_core(left_n);
126     root->right = bt_create_by_random_core(right_n);
127     return root;    
128 }
129 
130 
131 void bt_show_by_tree(link root)
132 {
133     char cmd[CMD_LEN];
134 
135     sprintf(cmd, "rm -f ./tree_src.txt");
136     system(cmd);
137 
138     FILE *fd = fopen("./tree_src.txt", "a+");
139     fprintf(fd, "\n\t\\tree");
140     tree_print(root, fd);
141     fprintf(fd, "\n\n");
142     fclose(fd);
143 
144     sprintf(cmd, "cat ./tree_src.txt | ~/tree/tree");
145     system(cmd);
146 }
147 
148 void tree_print(link root, FILE *fd)
149 {    
150     fprintf(fd, "(");
151     if (root != NULL) {
152         fprintf(fd, "%d", root->item);
153         tree_print(root->left, fd);
154         tree_print(root->right, fd);
155     }
156     fprintf(fd, ")");
157 }
怎样输出二叉树的所有路径(按字典序)?

 

测试示范:

怎样输出二叉树的所有路径(按字典序)?
ZhangHaiba-MacBook-Pro:code apple$ ./a.out
15

                     57
             ________|________
             |               |
             76              98
            _|__        _____|_____
            |  |        |         |
            49          0         78
         ___|___     ___|___     _|__
         |     |     |     |     |  |
         24    10    96    22    97
        _|__  _|__  _|__  _|__  _|__
        |  |  |  |  |  |  |  |  |  |
              29    86    79
             _|__  _|__  _|__
             |  |  |  |  |  |
                   73
                  _|__
                  |  |

print all path in DFS order:
57 76 49 24
57 76 49 10 29
57 98 0 96 86 73
57 98 0 22 79
57 98 78 97
print all path in dictionary order:
57 76 49 10 29
57 76 49 24
57 98 0 22 79
57 98 0 96 86 73
57 98 78 97
ZhangHaiba-MacBook-Pro:code apple$ ./a.out
15

                    85
            ________|_________
            |                |
            27               38
         ___|___       ______|______
         |     |       |           |
         75    81      64          39
        _|__  _|__    _|__      ___|___
        |  |  |  |    |  |      |     |
              28      27        50    28
             _|__  ___|___     _|__  _|__
             |  |  |     |     |  |  |  |
                   44    30    73
                  _|__  _|__  _|__
                  |  |  |  |  |  |
                  0
                 _|__
                 |  |

print all path in DFS order:
85 27 75
85 27 81 28
85 38 64 27 44 0
85 38 64 27 30
85 38 39 50 73
85 38 39 28
print all path in dictionary order:
85 27 75
85 27 81 28
85 38 39 28
85 38 39 50 73
85 38 64 27 30
85 38 64 27 44 0
ZhangHaiba-MacBook-Pro:code apple$ ./a.out
20

                    55
            ________|_________
            |                |
            81               39
         ___|___       ______|______
         |     |       |           |
         93    7       76          14
        _|__  _|__  ___|___     ___|___
        |  |  |  |  |     |     |     |
              79    24    98    41    20
             _|__  _|__  _|__  _|__  _|__
             |  |  |  |  |  |  |  |  |  |
                                     43
                                 ____|____
                                 |       |
                                 22      92
                              ___|____  _|__
                              |      |  |  |
                              28     16
                           ___|___  _|__
                           |     |  |  |
                           15    46
                          _|__  _|__
                          |  |  |  |
                          71
                         _|__
                         |  |

print all path in DFS order:
55 81 93
55 81 7 79
55 39 76 24
55 39 76 98
55 39 14 41
55 39 14 20 43 22 28 15 71
55 39 14 20 43 22 28 46
55 39 14 20 43 22 16
55 39 14 20 43 92
print all path in dictionary order:
55 39 14 20 43 22 16
55 39 14 20 43 22 28 15 71
55 39 14 20 43 22 28 46
55 39 14 20 43 92
55 39 14 41
55 39 76 24
55 39 76 98
55 81 7 79
55 81 93
怎样输出二叉树的所有路径(按字典序)?

 

  #返回上一级

怎样输出二叉树的所有路径(按字典序)?

上一篇:【wikioi】1282 约瑟夫问题


下一篇:VS2008快捷键