二叉树的建立与遍历操作

1、（1） 二叉树的建立 先序中序遍历建立二叉树： 二叉树前序遍历序列中，第一个元素总是树的根节点的值。中序遍历序列中，左子树的节点的值位于根节点的值的左边，右子树的节点的值位 于根节点的值的右边。 递归解法： （1）如果前序遍历为空或中序遍历为空或节点个数小于等于0，返回NULL。 （2）创建根节点。前序遍历的第一个数据就是根节点的数据，在中序遍历中找到根节点的位置，可分别得知左子树和右子树的前序和中序遍 历序列，重建左右子树。

2、中序后序遍历建立二叉树： 二叉树中序遍历序列中，左子树的节点的值位于根节点的值的左边，右子树的节点的值位于根节点的值的右边。后序遍历序列中，左子树的节点的值位于右子树节点的值的左边，右子树的节点的值位于根节点的值的左边。

递归解法： （1）如果中序遍历为空或后序遍历为空或节点个数小于等于0，返回NULL。 （2）创建根节点。后序遍历的最后一个数据就是根节点的数据，在中序遍历中找到根节点的位置，可分别得知左子树和右子树的中序和后序遍 历序列，重建左右子树。

（2） 二叉树的遍历 先序遍历： a. 如果二叉树为空，空操作 b. 如果二叉树不为空，访问根节点，前序遍历左子树，前序遍历右子树 中序遍历： a. 如果二叉树为空，空操作。 b. 如果二叉树不为空，中序遍历左子树，访问根节点，中序遍历右子树 后序遍历： a.如果二叉树为空，空操作 b. 如果二叉树不为空，后序遍历左子树，后序遍历右子树，访问根节点 层序遍历：   相当于广度优先搜索，使用队列实现。   队列初始化，将根节点压入队列。当队列不为空，进行如下操作：弹出  一个节点，访问，若左子节点或右子节点不为空，将其压入队列。    之前照着书上描写的通过递归建立二叉树后发现在输入时是死循环，便认为是自己程序出错后面发现自己的程序并没有出错，而是自己对于二叉树的定义理解不深刻。        在程序中  输入要严格按照正确的顺序才能结束.这里要用到二叉树的一个性质,就是说对于有n个节点的二叉树,就有n+1个空域,在这里即为如果你输入了n个元素,那么一定要有n+1个#才会结束迭代过程. 例如abcd#####才能完全结束输入，递归调用程序非常简洁，在程序小且效率要求不高的情况下，适当使用递归不置可否。

3、#include"stdio.h"#include"stdlib.h"#include"conio.h"#define ElemType char/*writer Liu*/typedef struct Node{        char data;        struct Node* Lchild;        struct Node* Rchild;        struct Node* parent;    }BiTNode,*BiTree;BiTree CreateBiTree(){    char ch;    BiTree T;    scanf("%c",&ch);//  getchar();    if(ch=='#') T=NULL;         /*这里的输入要严格按照正确的顺序才能结束.这里要用到二叉树的一个性质,就是说对于有n个节点的二叉树,就有n+1个空域,在这里即为如果你输入了n个元素,那么一定要有n+1个#才会结束迭代过程.*/     else                        /*例如1234#####才能成功！*/     {        T =(BiTree)malloc(sizeof(BiTNode));        T->data = ch;        T->Lchild = CreateBiTree();        T->Rchild = CreateBiTree();    }    return T;//return root node }//先序遍历二叉树 void PreOrderTraverse(BiTree T) {    if(T)    {        printf("%c",T->data);        PreOrderTraverse(T->Lchild);        PreOrderTraverse(T->Rchild);     } } //中序遍历二叉树 void InOrderTraverse(BiTree T) {    if(T)    {        InOrderTraverse(T->Lchild);        printf("%c",T->data);        InOrderTraverse(T->Rchild);     }  }   //后序遍历二叉树  void PostOrderTraverse(BiTree T)  {    if(T)    {        PostOrderTraverse(T->Lchild);        PostOrderTraverse(T->Rchild);        printf("%c",T->data);      }   } int main() {    BiTree T;    T = CreateBiTree();    PreOrderTraverse(T);    printf("\n");    InOrderTraverse(T);     printf("\n");     PostOrderTraverse(T); }