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

     在计算机科学中,树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构。二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”(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 }

 

构造这样一颗二叉树:

程序运行结果为:

 

二叉树中序遍历 (C语言实现),古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。