树树树树树

//先序遍历
void PreOrder(BiTree T){
    if(T!=NULL){
        printf("%c",T->data);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}
//后序遍历
void PostOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        printf("%c",T->data);
    }
}
//中序遍历
void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);
        printf("%c",T->data);
        InOrder(T->rchild);
    }
}
//层序遍历(广度优先遍历)
void LevelOrder(BiTree T){
    LinkQueue Q;//申请一个辅助队列
    InitLinkQueue(Q);//初始化队列
    BiTree t;//用于存储出队的元素
    EnLinkQueue(Q,T);//树中元素入队
    while (!IsEmpty(Q)){
        DeLinkQueue(Q,t);
        putchar(t->data);
        if(t->lchild!=NULL){
            EnLinkQueue(Q,t->lchild);
        }
        if(t->rchild!=NULL){
            EnLinkQueue(Q,t->rchild);
        }
    }
}
int main() {
//层序建树
   BiTree pnew;//申请树的结点
   BiTree tree=NULL;//树根此时是空树
   BiElemType c;//abcdefghij
   ptag_t phead=NULL,ptail=NULL,list_pnew=NULL,pcur;
   //phead为队列头,ptail为队列尾,pcur指向当前结点
    while (scanf("%c",&c)){
        if(c=='\n'){
            break;//读到换行就结束
        }
        //为新结点申请空间
        //calloc申请空间并进行初始化，其空间大小为两个参数的乘积
        pnew=(BiTree) calloc(1,sizeof (BiTNode));
        pnew->data=c;//放数据
        list_pnew=(ptag_t) calloc(1,sizeof (tag_t));
        list_pnew->p=pnew;
        //如果是树的第一个结点
        if(tree==NULL){
            tree=pnew;//根节点
            phead=list_pnew;//均指向第一个结点
            ptail=list_pnew;
            pcur=list_pnew;//pcur指向要进树的父节点
        } else{
            //先让元素入队
            ptail->pnext=list_pnew;
            ptail=list_pnew;
            //接下来把结点放入树中
            if(NULL==pcur->p->lchild){
                pcur->p->lchild=pnew;//左孩子为空,插入左孩子
            } else if(NULL==pcur->p->rchild){
                pcur->p->rchild=pnew;//右孩子为空,插入右孩子
                pcur=pcur->pnext;//当前结点左右孩子已经满了，就指向队列中的下一个结点
            }
        }
    }
    PreOrder(tree);
    printf("----------PreOrder\n");
    PostOrder(tree);
    printf("----------PostOrder\n");
    InOrder(tree);
    printf("----------InOrder\n");
    LevelOrder(tree);
    printf("----------LevelOrder\n");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87