二叉树遍历的应用

二叉树遍历的应用。

求二叉树结点个数

//求二叉树结点个数
int Size(BinaryTreeNode *t){
    if(!t) return 0;
    return Size(t->LChild) + Size(t->RChild) + 1;
}

求二叉树叶子结点个数

//求二叉树叶子结点个数
int Leaf(BinaryTreeNode *t){
    if(t==NULL) return 0;
    if((t->LChild == NULL) && (t->RChild == NULL)) return 1;
    return Leaf(t->LChild) + Leaf(t->RChild);
}

求二叉树的高度

//求二叉树的高度
int Depth(BinaryTreeNode *t){
    if(!t) return 0;
    // else return (1 + Depth(t->LChild) > Depth(t->RChild) ? Depth(t->LChild) : Depth(t->RChild));
    else return 1 + max(Depth(t->LChild) , Depth(t->RChild));
}

交换二叉树

//交换二叉树
void Exch(BinaryTreeNode *t){
    if(t){
        BinaryTreeNode *q = t->LChild;
        t->LChild = t->RChild;
        t->RChild = q;
        Exch(t->LChild);
        Exch(t->RChild);
    }
}

求二叉树度为 1 结点数

//求二叉树度为 1 结点数
int Count1(BinaryTreeNode *t){
    if(t == NULL) return 0;
    if((t->LChild == NULL && t->RChild != NULL) || (t->LChild != NULL && t->RChild == NULL))
        return 1;
    return Count1(t->LChild) + Count1(t->RChild);
}

求二叉树度为 2 结点数

//求二叉树度为 2 结点数
int Count2(BinaryTreeNode *t){
    if(t == NULL) return 0;
    else if((t->LChild == NULL) && (t->RChild == NULL)) return 0;
    else if((t->LChild == NULL) && (t->RChild != NULL)) Count2(t->RChild);
    else if((t->LChild != NULL) && (t->RChild == NULL)) Count2(t->LChild);
    else return Count2(t->LChild) + Count2(t->RChild) + 1;
}

//法二
int NumberOfTwoDegree(BinaryTreeNode *t){
    if(t == NULL) return 0;
    else if(t->LChild != NULL && t->RChild != NULL)
        return NumberOfTwoDegree(t->LChild) + NumberOfTwoDegree(t->RChild) + 1;
    else return NumberOfTwoDegree(t->LChild) + NumberOfTwoDegree(t->RChild);
}

二叉树复制

//二叉树复制
BinaryTreeNode *Copy(BinaryTreeNode *p){
    if(!p) return NULL;
    BinaryTreeNode *q = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
    q->Data = p->Data;
    q->LChild = Copy(p->LChild);
    q->RChild = Copy(p->RChild);
    return q;
}

删除一棵二叉树

//删除一棵二叉树
void Clear(BinaryTreeNode *t){
    if(t){
        Clear(t->LChild);
        Clear(t->RChild);
        free(t);
    }
}

层次遍历二叉树

//层次遍历二叉树
//好像有问题
void BreadthFirstSearch(BinaryTreeNode *t){
    Queue Q;
    BinaryTreeNode * node;
    EnQueue(&Q, t->data);
    while(!IsEmpty(&Q)){
        Front(&Q, node);
        DeQueue(&Q);
        printf("%d", node->LChild);
        if(node->LChild) EnQueue(&Q, node->LChild);
        if(node->RChild) EnQueue(&Q, node->RChild);
    }
}

//法二
//好像也有问题
void Levelorder(BinaryTreeNode *t){
    BinaryTreeNode *p;
    Queue *Q;
    Create(&Q, 100);
    if(t != NULL){
        EnQueue(&Q, t);
        while(!IsEmpty(&Q)){
            Front(&Q, p);
            DeQueue(Q);
            printf("%c",p->data);
            if(p->LChild) EnQueue(&Q, p->LChild);
            if(p->RChild) EnQueue(&Q, p->RChild);
        }
    }
}

判断两棵二叉树是否相等

//判断两棵二叉树是否相等
bool Compare(BinaryTreeNode *t, BinaryTreeNode *p){
    if(t && p){
        if(t->Data != p->Data)
            return FALSE;
        return Compare(t->LChild, p->LChild) && Compare(t->RChild, p->RChild);
    }
    else if(t || p)
        return FALSE;
    return TRUE;
}