二叉树创建前序中序后序遍历

二叉树的建立，遍历。 #include"stdio.h" #include"stdlib.h" typedef struct BiTNode {char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; BiTree CreateBiTree() {char p; BiTree T; scanf("%c",&p); if(p==' ') T=NULL; else {T=(BiTNode*)malloc(sizeof(BiTNode)); T->data=p; T->lchild=CreateBiTree(); T->rchild=CreateBiTree(); } 根据给定的文件信息，我们可以总结出以下关于二叉树创建及遍历的相关知识点： ### 一、二叉树的基本概念 二叉树是一种非线性的数据结构，它由节点组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树在计算机科学中有广泛的应用，如搜索算法、排序算法等。 ### 二、二叉树的结构定义 在给定的代码中，二叉树节点的结构体定义如下： ```c typedef struct BiTNode { char data; // 节点存储的数据 struct BiTNode *lchild; // 左子节点指针 struct BiTNode *rchild; // 右子节点指针 } BiTNode, *BiTree; ``` 这里使用了`typedef`来简化结构体类型的名称，其中`BiTNode`代表二叉树节点类型，而`BiTree`则代表指向二叉树节点的指针类型。每个节点包含一个字符数据`data`以及指向左右子节点的指针`lchild`和`rchild`。 ### 三、二叉树的创建 二叉树的创建主要通过递归的方式实现。创建函数`CreateBiTree()`的实现如下： ```c BiTree CreateBiTree() { char p; BiTree T; scanf("%c", &p); // 读取一个字符作为节点数据 if (p == ' ') T = NULL; // 如果读入的是空格，则返回空指针表示此节点为空 else { T = (BiTNode *)malloc(sizeof(BiTNode)); // 分配内存空间 T->data = p; // 设置节点数据 T->lchild = CreateBiTree(); // 递归创建左子树 T->rchild = CreateBiTree(); // 递归创建右子树 } return T; // 返回根节点 } ``` 这个创建过程是通过输入一系列字符来构建二叉树，当输入为`' '`时，表示该位置的节点为空；否则，创建一个新的节点，并继续递归地创建其左右子树。 ### 四、二叉树的遍历 二叉树的遍历是指按照某种顺序访问二叉树中的所有节点的过程。常见的遍历方法包括：前序遍历、中序遍历和后序遍历。 #### 4.1 前序遍历 前序遍历的顺序是先访问根节点，然后递归地进行左子树的前序遍历，最后递归地进行右子树的前序遍历。实现代码如下： ```c void Preoder(BiTree T) { if (T != NULL) { printf("%c", T->data); // 访问根节点 Preoder(T->lchild); // 递归遍历左子树 Preoder(T->rchild); // 递归遍历右子树 } } ``` #### 4.2 中序遍历 中序遍历的顺序是递归地进行左子树的中序遍历，然后访问根节点，最后递归地进行右子树的中序遍历。实现代码如下： ```c void Inoder(BiTree T) { if (T != NULL) { Inoder(T->lchild); // 递归遍历左子树 printf("%c", T->data); // 访问根节点 Inoder(T->rchild); // 递归遍历右子树 } } ``` #### 4.3 后序遍历 后序遍历的顺序是递归地进行左子树的后序遍历，然后递归地进行右子树的后序遍历，最后访问根节点。实现代码如下： ```c void Postoder(BiTree T) { if (T != NULL) { Postoder(T->lchild); // 递归遍历左子树 Postoder(T->rchild); // 递归遍历右子树 printf("%c", T->data); // 访问根节点 } } ``` ### 五、程序运行流程 主函数`main()`中调用了创建二叉树的函数`CreateBiTree()`并将其结果赋值给`Ta`。随后，分别调用三种遍历方式输出二叉树的信息。 ```c void main() { BiTree Ta; Ta = CreateBiTree(); printf("\n"); Preoder(Ta); printf("\n"); Inoder(Ta); printf("\n"); Postoder(Ta); printf("\n"); } ``` 这段代码实现了二叉树的创建与遍历过程，并通过具体的遍历函数将二叉树的信息打印出来，便于理解和分析。