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

淩亂°似流年 2021-12-22 10:29 243阅读 0赞

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

构造这样一颗二叉树：

![141654477334730.png][]

程序运行结果为：

![141659041551635.png][]

转载于:https://www.cnblogs.com/Jerryli/p/3912995.html

[141654477334730.png]: /images/20211220/b0f813de94874053a2a85ddf09937c50.png
[141659041551635.png]: /images/20211220/032a6aa94dd745699197ff646f8ff8de.png