C语言二叉树的建立与遍历

浏览数：13 / 时间：2015年06月08日

二叉树的建立和遍历都要用到递归，先暂时保存一下代码，其中主要是理解递归的思想，其它的就都好理解了。这里是三种遍历方式，其实理解一种，其它的几个就都理解了，就是打印出来的顺序不一样而已。建立和遍历的方式差不多。也分好几种方式建立，这里就写一种，就是先序建立

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 typedef struct TreeNode{
 5     char ch;
 6     struct TreeNode *lchild, *rchild;
 7 }Tree, *PTree;//定义树节点的结构体
 8 void createBiTree(PTree *p)//建立二叉树
 9 {
10     char ch;
11     scanf("%c", &ch);
12     getchar();//此时%c读取的是单个字符，所以用那个getchar来接收一下
13     if(ch == ‘#‘)
14          *p = NULL;
15     else
16     {
17         *p = (PTree)malloc(sizeof(Tree));
18         (*p) -> ch = ch;
19         printf("请输入%c的左子树\n", ch);
20         createBiTree(&(*p) -> lchild);
21         printf("请输入%c的右子树\n", ch);
22         createBiTree(&(*p) -> rchild);
23     }
24 
25 }
26 void preOrderTraverse(PTree p)//前序遍历
27 {
28     if(p == NULL)
29         return ;
30     printf("%c ", p -> ch);
31     preOrderTraverse(p -> lchild);
32     preOrderTraverse(p -> rchild);
33 }
34 void InOrderTraverse(PTree p)//中序遍历
35 {
36     if(p == NULL)
37         return;
38     InOrderTraverse(p -> lchild);
39     printf("%c ", p -> ch);
40     InOrderTraverse(p -> rchild);
41 }
42 void BackOrderTraverse(PTree p)//后续遍历
43 {
44     if(p == NULL)
45         return ;
46     BackOrderTraverse(p -> lchild);
47     BackOrderTraverse(p -> rchild);
48     printf("%c ", p -> ch);
49 }
50 int main()
51 {
52     PTree pt;
53     createBiTree(&pt);
54     preOrderTraverse(pt);
55     printf("\n");
56     InOrderTraverse(pt);
57     printf("\n");
58     BackOrderTraverse(pt);
59     printf("\n");
60     return 0;
61 }