二叉树的遍历（深度优先）

深度优先法、

这种方法基于递归的思想，先查看完一棵字数上的全部结点后再查看另一棵子树上的结点。按照对左子树、根结点、右子树的查看顺序，划分了4种不同的遍历顺序：先根顺序、后根顺序、左子树优先、右子树优先。

程序示例（先根顺序、左子树优先顺序）、

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 struct TreeNode {
 5     int val;
 6     TreeNode *Left, *Right;
 7 }; //建立二叉树结点数据类型。
 8 
 9 TreeNode * insertTree(TreeNode * root, int val) { //想二叉树中添加新的结点。
10     TreeNode * newNode;
11     if(root == NULL) {
12         newNode = new TreeNode;
13         newNode -> val = val;
14         newNode -> Left = NULL;
15         newNode -> Right = NULL;
16         return newNode;
17     }
18         if(val <= root -> val)
19             root -> Left = insertTree(root -> Left, val) ;
20         else
21             root -> Right = insertTree(root -> Right, val);
22         return root;
23 }
24 
25 void delTree(TreeNode * root) { //删除二叉树占用的存储空间。
26     if(root -> Left != NULL) delTree(root -> Left);
27     if(root -> Right != NULL) delTree(root -> Right);
28     delete root;
29     return;
30 }
31 
32 void LFRTraverse(TreeNode * root) { //采用左子树优先的顺序遍历二叉树，每访问一个结点时，就输出该结点的值。
33     if(root -> Left != NULL) LFRTraverse(root -> Left);
34     printf("%d", root -> val);
35     if(root -> Right != NULL) LFRTraverse(root -> Right);
36     return;
37 }
38 
39 void FLRTraverse(TreeNode * root) { //采用先根顺序遍历二叉树，每访问一个结点时，就输出该结点的值。
40     printf("%d", root -> val);
41     if(root -> Left != NULL) FLRTraverse(root -> Left);
42     if(root -> Right != NULL) FLRTraverse(root -> Right);
43     return;
44 }
45 
46 int main()
47 {
48     FILE * fin;
49     TreeNode * root;
50     int val;
51     char inFile[30];
52     printf("input the data file's name: ");
53     scanf("%s", inFile);
54     fin = fopen("data.txt", "r"); //从输入文件中读入数据，建立一个二叉树。
55     root = NULL;
56     while(fscanf(fin, "%d", &val) != EOF) root = insertTree(root, val);
57     fclose(fin);
58     printf("traversing left sub - tree firstly, then root,  and right sub - tree lastly: 
");
59     LFRTraverse(root); printf("
");
60     printf("traversing root firstly, then left sub - tree, and right sub - tree lastly: 
");
61     FLRTraverse(root); printf("
");
62     delTree(root);
63     return 0;
64 }

View Code