二叉树2静态二叉树

数据结构之二叉树

• 二叉树的先序、中序、后序遍历
• 动态二叉树转化成静态二叉树

代码

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR -1
#define MAX 100

typedef int Status;
typedef char ElementType;

typedef struct BiTnode{
    ElementType data;
    struct BiTnode *lchild,*rchild;
}BiTnode,*Node_p;

typedef struct Bilir{
    ElementType data;
    int lchild,rchild;
}Bilir,*Bilir_p;

Status CreateBiTree(Node_p &T){
    ElementType item;
    printf("请输入结点的值(空格代表结束):\n");
    item = getchar();
    if(item==' '){
        T = NULL;
        return OK;
    }
    T = (Node_p) malloc(sizeof(BiTnode));
    if(!T) return ERROR;
    T->data = item;
    printf("%c 的左孩子:\n",item);
    getchar();
    CreateBiTree(T->lchild);
    printf("%c 的右孩子:\n",item);
    getchar();
    CreateBiTree(T->rchild);
}

Status PreOrderTraverse(Node_p T) {
    if(T) {
        printf("%c ",T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
    return OK;
}

Status InOrderTraverse(Node_p T) {
    if(T) {
        InOrderTraverse(T->lchild);
        printf("%c ",T->data);
        InOrderTraverse(T->rchild);
    }
    return OK;
}

Status PostOrderTraverse(Node_p T) {
    if(T) {
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        printf("%c ",T->data);
    }
    return OK;
}

int turnTo(Node_p T,Bilir a[],int *index){
    int temp = *index;
    a[temp].data = T->data;
    if(T->lchild){
        *index = *index+1;
        a[temp].lchild = turnTo(T->lchild,a,index);
    } else{
        a[temp].lchild = -1;
    }
    if (T->rchild){
        *index = *index+1;
        a[temp].rchild = turnTo(T->rchild,a,index);
    } else{
        a[temp].rchild = -1;
    }
    return temp;
}

Status ReadBirlr(Bilir a[],int length){
    printf("\n");
    for (int i = 0; i <= length; ++i) {
        printf("%2d ",a[i].lchild);
    }
    printf("\n");
    for (int i = 0; i <= length; ++i) {
        printf("%2c ",a[i].data);
    }
    printf("\n");
    for (int i = 0; i <= length; ++i) {
        printf("%2d ",a[i].rchild);
    }
}

int main() {
    Node_p Tree;
    Bilir a[MAX];
    int index = 0;
    CreateBiTree(Tree);
    PreOrderTraverse(Tree);
    printf("\n");
    InOrderTraverse(Tree);
    printf("\n");
    PostOrderTraverse(Tree);
    turnTo(Tree,a,&index);
    ReadBirlr(a,index);
    return 0;
}

二叉树用例

输入

请输入结点的值(空格代表结束):
e
e 的左孩子:
请输入结点的值(空格代表结束):
g
g 的左孩子:
请输入结点的值(空格代表结束):
t
t 的左孩子:
请输入结点的值(空格代表结束):
 
t 的右孩子:
请输入结点的值(空格代表结束):
 
g 的右孩子:
请输入结点的值(空格代表结束):
 
e 的右孩子:
请输入结点的值(空格代表结束):
k
k 的左孩子:
请输入结点的值(空格代表结束):
y
y 的左孩子:
请输入结点的值(空格代表结束):
 
y 的右孩子:
请输入结点的值(空格代表结束):
 
k 的右孩子:
请输入结点的值(空格代表结束):
 

输出

e g t k y 
t g e y k 
t g y k e 
 1  2 -1  4 -1 
 e  g  t  k  y 
 3 -1 -1 -1 -1