二叉树中序遍历 (C语言实现)

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

在计算机科学中，树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构。二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

如下是实现创建二叉树和二叉树中序遍历的代码：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <memory.h>
 4 
 5 typedef struct _tree_node{
 6     char data;
 7     struct _tree_node * left;
 8     struct _tree_node * right;
 9     struct _tree_node * father;
10 }tree_node;
11 
12 void createTree(tree_node * root);
13 void inorderTraverseTree(tree_node * pRoot);
14 
15 int main()
16 {
17     tree_node root;
18     memset(&root, 0 , sizeof(tree_node));
19     printf("Please create the tree: \n");
20     createTree(&root);
21     printf("The inorder traverse result is: \n");
22     inorderTraverseTree(&root);
23     return 0;
24 }
25 
26 //inorder traversal
27 void inorderTraverseTree(tree_node * pRoot)
28 {
29     tree_node * pCur = pRoot;
30     if(pCur != NULL)
31     {
32         if(pCur->left != NULL)
33         {
34             inorderTraverseTree(pCur->left);
35         }
36         else
37         {
38             printf("%c ", pCur->data);
39             return;
40         }
41         printf("%c ", pCur->data);
42 
43         if(pCur->right != NULL)
44         {
45             inorderTraverseTree(pCur->right);
46         }
47     }
48 }
49 
50 //Create the binary tree
51 void createTree(tree_node * pRoot)
52 {
53     char ch = 0;
54     tree_node * pCur = pRoot;
55     while((ch = getchar())!= ‘e‘)
56     {
57         //printf("%c" , ch);
58         tree_node * pNewNode = (tree_node *)malloc(sizeof(tree_node));
59         pNewNode->left = NULL;
60         pNewNode->right = NULL;
61         pNewNode->father = NULL;
62         if(ch == ‘L‘)
63         {
64             //printf("Input L\n");
65             pNewNode->data = getchar();
66             pNewNode->father = pCur;
67             pCur->left = pNewNode;
68             pCur = pNewNode;
69         }
70         else if(ch == ‘R‘)
71         {
72             //printf("Input R\n");
73             pNewNode->data = getchar();
74             pNewNode->father = pCur;
75             pCur->right = pNewNode;
76             pCur = pNewNode;
77         }
78         else if(ch == ‘B‘)
79         {
80             //printf("Input B\n");
81             free(pNewNode);
82             if(pCur->father != NULL)
83                 pCur = pCur->father;
84             else
85                 printf("It‘s the top\n");
86         }
87     }
88 }