概念

树是n个节点的有限集

• 若n=0 称为空树

• 若n>0 则它满足如下几个条件

• 有且仅有一个特定的称为根的节点

• 其余节点可分为m个互不相交的有限集T1,T2,T3.....其中每一个集合本身又是一棵树，并且称为根的子树

顺序树

typedef TElemType SqBiTree[MAXQSIZE];
SqBiTree bt;

链式树

typedef struct BiNode{
    TElemType data;
    struct BiNode *lchild,*rchild;
}BiNode,*BiTree;

三叉链表

typedef struct TriTNode{
    TElemType data;
    struct TriTNode *lchild,*parent,*rchild;
}TriTNode,*TriTree;

操作

遍历

先序遍历

根-左-右

void Pre(BiTree T){
    if(T!=NULL){
        printf("%d\t",T->data);
        Pre(T->lchild);
        Pre(T->rchild);
    }
}

具体原理我们使用王卓老师的课件，非常的浅显易懂

中序遍历

左-根-右

void InOrder(BiTree t){
    if(t!=NULL){
        InOder(t->lchild);
        printf("%d\t",t->data);
        InOder(t->rchild);
    }
}

非遍历方法

Status InOrder_A(BiTree t){
    BiTree p,q;
    SqStack s;
    InitStack(&s);
    p=t;
    while(p!=NULL||s.base!=s.top){ 
        if(p!=NULL){
            Push(&s,p);
            p=p->lchild;
        }else{
            Pop(&s,q);
            printf("%c",q->data);
            p=q->rchild;
        }
    }
    return OK;
}

后序遍历

左-右-根

void PostOrder(BiTree t){
    if(t!=NULL){
        PostOrder(t->lchild);
        PostOrder(t->rchild);
        printf("%d\t",t->data);
    }
}

层次遍历

void LevelOrder(BiNode *b){
    BiNode *p;
    SqQueue *qu;
    InitQueue(qu);
    EntryQueue(qu,b);
    while(qu->front!=qu->rear){
        OutQueue(qu,p);
        printf("%c",p->data);
        if(p->lchild!=NULL){
            EntryQueue(qu,p->lchild);
        }
        if(p->rchild!=NULL){
            EntryQueue(qu,p->rchild);
        }
    }
}

建立二叉树

Status CreateBiiTree(BiTree *T){
    char ch =scanf(&ch);
    if(ch=='#'){
        *T=NULL;
    }else{
        if((T=(BiNode *)malloc(sizeof(BiNode)))!=NULL){
            return OVERFLOW;
        }
        (*T)->data=ch;
        CreateBiiTree(&(*T)->lchild);
        CreateBiiTree(&(*T)->rchild);
    }
    return OK;

}

复制二叉树

void Copy(BiTree *Tnew, const BiTree T) {
    if (!T) {
        *Tnew = NULL;
        return;
    } else {
        *Tnew = (BiTree)malloc(sizeof(BiNode));
        (*Tnew)->data = T->data;
        Copy(&(*Tnew)->lchild, T->lchild);
        Copy(&(*Tnew)->rchild, T->rchild);
    }
}