二叉树建立与遍历

二叉树建立与遍历

本算法主要是利用扩展先序遍历法创建二叉树，再用先序遍历遍历二叉树，最后按照树形输出整个二叉树：

#include <stdio.h> 
#include <stdlib.h> 
#include <conio.h> 
 
typedef int DataType; 
 
typedef struct Node { 
    DataType data; 
    struct Node *LChild; 
    struct Node *RChild; 
}BiNode,*BiTree; 
 
void CreateBiTree(BiTree *bt) //扩展先序遍历法建造BiTree 
{ 
    char ch; 
    ch = getchar(); 
    if ('.' == ch) 
        *bt = NULL; 
    else 
    { 
        *bt = (BiTree)malloc(sizeof(BiNode)); 
        (*bt)->data = ch; 
        CreateBiTree(&((*bt)->LChild)); 
        CreateBiTree(&((*bt)->RChild)); 
    } 
}//CreateBitTree 
 
void Visit(char ch) 
{ 
    printf("%c ",ch); 
}//Visit 
 
void PreOrder(BiTree root) 
{ 
    if (NULL != root) 
    { 
        Visit(root->data); 
        PreOrder(root->LChild); 
        PreOrder(root->RChild); 
    } 
} //PreOrder 
 
void PrintTree(BiTree Boot,int nLayer) 
{ 
    int i; 
    if (NULL == Boot) 
        return; 
    PrintTree(Boot->RChild,nLayer+1); 
    for (i=0; i<nLayer; ++i) 
    { 
        printf(" "); 
    } 
    printf("%c\n",Boot->data); 
    PrintTree(Boot->LChild,nLayer+1); 
} //PrintTree 
 
int main() 
{ 
    BiTree T; 
    int layer = 0; 
    printf("以扩展先序遍历序列输入,其中.代表空子树:\n"); 
    CreateBiTree(&T); 
    printf("PreOrder:"); 
    PreOrder(T); 
    printf("\n"); 
    PrintTree(T,layer); 
    return 0; 
}  //main 

实例结果：