二叉树的存储及遍历

一、二叉树顺序存储实现：

1.存储结构：（数组）
···
/* 0号单元存储根结点 */
typedef CElemType SqBiTree[MAX_TREE_SIZE];
typedef struct {
int level; //结点层
int order; //本层的序号(按照满二叉树给定序号规则)
}Position;

2.遍历方式：
层次遍历：T 为存储数组

    int i = MAX_TREE_SIZE-1;
    
    //找到最后一个非空结点的序号
    while (T[i] == Nil) i--;
    
    //从根结点起,按层序遍历二叉树
    for (int j = 0; j <= i; j++)
        //只遍历非空结点
        if (T[j] != Nil)
            visit(T[j]);
    
    printf("\n");

前序遍历二叉树：

void PreTraverse(SqBiTree T,int e){
    
    //打印结点数据
    visit(T[e]);
    
    //先序遍历左子树
    if (T[2 * e + 1] != Nil) {
        PreTraverse(T, 2*e+1);
    }
    //最后先序遍历右子树
    if (T[2 * e + 2] != Nil) {
        PreTraverse(T, 2*e+2);
    }
}

Status PreOrderTraverse(SqBiTree T){
    
    //树不为空
    if (!BiTreeEmpty(T)) {
        PreTraverse(T, 0);
    }
    printf("\n");
    return  OK;
}

中序遍历

void InTraverse(SqBiTree T, int e){
    
    /* 左子树不空 */
    if (T[2*e+1] != Nil)
        InTraverse(T, 2*e+1);
    
    visit(T[e]);
    
    /* 右子树不空 */
    if (T[2*e+2] != Nil)
        InTraverse(T, 2*e+2);
}

Status InOrderTraverse(SqBiTree T){
    
    /* 树不空 */
    if (!BiTreeEmpty(T)) {
        InTraverse(T, 0);
    }
    printf("\n");
    return OK;
}

后序遍历

void PostTraverse(SqBiTree T,int e)
{   

     //左子树不空 
    if(T[2*e+1]!=Nil)
        PostTraverse(T,2*e+1);
    /* 右子树不空 */
    if(T[2*e+2]!=Nil)
        PostTraverse(T,2*e+2);
    
    visit(T[e]);
}
Status PostOrderTraverse(SqBiTree T)
{

    if(!BiTreeEmpty(T)) /* 树不空 */
        PostTraverse(T,0);
    printf("\n");
    return OK;
}

输出：
二叉树T的存储： 1 2 3 4 5 6 7 8 9 10
二叉树T层序遍历:1 2 3 4 5 6 7 8 9 10
二叉树T先序遍历:1 2 4 8 9 5 10 3 6 7
二叉树T中序遍历:8 4 9 2 10 5 1 6 3 7
二叉树T后序遍历:8 9 4 10 5 2 6 7 3 1

二、链式存储 （链表）

// 结点结构 
typedef struct BiTNode  {

    CElemType data;        //结点数据
    struct BiTNode *lchild,*rchild; //左右孩子指针
}BiTNode,*BiTree;

前序递归遍历T
 初始条件:二叉树T存在;
 操作结果: 前序递归遍历T

void PreOrderTraverse(BiTree T)
{

    if(T==NULL)
        return;
    printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
    PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */
    PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */
}
中序递归遍历T
 初始条件:二叉树T存在;
 操作结果: 中序递归遍历T

void InOrderTraverse(BiTree T)
{

    if(T==NULL)
        return ;
    InOrderTraverse(T->lchild); /* 中序遍历左子树 */
    printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
    InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */
}
 后序递归遍历T
 初始条件:二叉树T存在;
 操作结果: 中序递归遍历T

void PostOrderTraverse(BiTree T)
{

    if(T==NULL)
        return;
    PostOrderTraverse(T->lchild); /* 先后序遍历左子树  */
    PostOrderTraverse(T->rchild); /* 再后序遍历右子树  */
    printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
}