首页 > 代码库 > 二叉树中序遍历 (C语言实现)

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

2024-07-17 15:04:10   221人阅读

     在计算机科学中，树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构。二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”（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 traversal27 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         else37         {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 tree51 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 =http://www.mamicode.com/ 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 =http://www.mamicode.com/ 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             else85                 printf("It‘s the top\n");86         }87     }88 }

 

构造这样一颗二叉树：

程序运行结果为：

 


联系
我们