二叉树创建、先序遍历、中序遍历、后序遍历、树深度-蒲公英云

二叉树创建、先序遍历、中序遍历、后序遍历、树深度

一、概念：

     二叉树遍历：按指定的某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。
    根节点N，按照先遍历左子树L再遍历右子树R的原则，常见的有三种：先序(NLR)、中序(LNR)、后序(LRN)。其中，序是指根节点什么时候被访问。

有时还有提到层序(按层遍历访问)

    例如：下图

20160930224150099

       显然 深度为 4
       求先序遍历：    A(以A为根的左子树)(以A为根的右子树)——A(B)(以C为根的先序遍历)——ABC（E、F、G）——A B C D E F G
          同理中序：中间访问根节点：B A D C F E G
          后序遍历：B D F G E C A

二、算法实现

先序遍历操作过程：（递归）

               如果二叉树为空，什么也不做。
               否则：
               （1）访问根节点
               （2）先序遍历左子树
               （3）先序遍历右子树
                递归注意结束条件
//先序遍历递归
int PreOrder(BiTree T){
    if(T!=NULL){
        Visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
    return 0;
}

中序遍历操作过程：（递归）

               如果二叉树为空，什么也不做。
               否则：
               （1）中序遍历左子树
               （2）访问根节点
               （3）中序遍历右子树
                递归注意结束条件
//中序遍历递归
int InOrder(BiTree T){
    if(T!=NULL){        
        InOrder(T->lchild);
        Visit(T);
        InOrder(T->rchild);
    }
    return 0;
}

后序遍历操作过程：（递归）

               如果二叉树为空，什么也不做。
               否则：
               （1）后序遍历左子树
               （2）后序遍历右子树
               （3）访问根节点
                递归注意结束条件
//后序遍历递归
int PostOrder(BiTree T){
    if(T!=NULL){        
        PostOrder(T->lchild);        
        PostOrder(T->rchild);
        Visit(T);
    }
    return 0;
}
           三种时间复杂度O（n）
             最坏情况下，n个结点深度为n的斜树
             层序遍历（  使用队列）
             完整代码：
#include<stdio.h>
#include<stdlib.h>
typedef char ElemType;//结点数据类型
//二叉树结点
typedef struct BiTNode{
    ElemType data;//数据
    struct BiTNode *lchild; //左子树指针
    struct BiTNode *rchild; //右子树指针
}BiTNode,*BiTree;
//先序输入创建二叉树
int CreatBiTre(BiTree &T){
    ElemType x;//输入结点值
    scanf("%c",&x);
    if(x=='#') T=NULL;//空结点输入空格
    else{
        T=(BiTree)malloc(sizeof(BiTNode));
        if(T==NULL){
            printf("OVERFLOW!\n");
            exit(1);            
        }
        T->data=x;
        CreatBiTre(T->lchild);
        CreatBiTre(T->rchild);        
    }
    return 0;
}
void Visit(BiTree T){
    if(T->data!='#')
        printf("%c ",T->data);    
}
//先序遍历递归
int PreOrder(BiTree T){
    if(T!=NULL){
        Visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
    return 0;
}
//中序遍历递归
int InOrder(BiTree T){
    if(T!=NULL){        
        InOrder(T->lchild);
        Visit(T);
        InOrder(T->rchild);
    }
    return 0;
}
//后序遍历递归
int PostOrder(BiTree T){
    if(T!=NULL){        
        PostOrder(T->lchild);        
        PostOrder(T->rchild);
        Visit(T);
    }
    return 0;
}
//树的深度递归
int TreeHeight(BiTree T){
    int height,left,right;
    if(T==NULL)        
        return 0;    
    left=TreeHeight(T->lchild);
    right=TreeHeight(T->rchild);
    height=(left>right)?left:right;
    return height+1;    //算上根结点一层
}
void main(){
    BiTree T=NULL;
    CreatBiTre(T);
    int height;
    height=TreeHeight(T);
    printf("树的深度： %d\n",height);
    printf("先序遍历： ");
    PreOrder(T);
    printf("\n");
    printf("中序遍历： ");
    InOrder(T);
    printf("\n");
    printf("后序遍历： ");
    PostOrder(T);
    printf("\n");
}
    截图：