二叉樹(shù)的幾種運(yùn)算方法

2019-11-17 05:36:21

字體：大中小

供稿：網(wǎng)友

1.二叉樹(shù)的前序遍歷
先訪問(wèn)根結(jié)點(diǎn),再訪問(wèn)左子樹(shù),最后訪問(wèn)右子樹(shù)的次序訪問(wèn)二叉樹(shù)中所有的結(jié)點(diǎn),且每個(gè)結(jié)點(diǎn)僅訪問(wèn)一次.
void PReorder(BTree *p)
{
    if(p!=NULL)
    {   printf("%d",p->data);
        preorder(p->left);
        preorder(p->right);
    }
}2.二叉樹(shù)的中序遍歷
先訪問(wèn)左子樹(shù),再訪問(wèn)根結(jié)點(diǎn),最后訪問(wèn)右子樹(shù)的次序訪問(wèn)二叉樹(shù)的所有結(jié)點(diǎn),且每個(gè)結(jié)點(diǎn)僅訪問(wèn)一次.
void inorder(btree *p)
{
    if(p!=NULL)
    {   inorder(p->left);
        printf("%d",p->data);
        inorder(p->right);
    }
}3.后序遍歷
先訪問(wèn)左子樹(shù),再訪問(wèn)右子樹(shù),最后訪問(wèn)根結(jié)點(diǎn)的次序訪問(wèn)二叉樹(shù)中所有的結(jié)點(diǎn),且每個(gè)結(jié)點(diǎn)僅訪問(wèn)一次
void postorder(btree *p)
{
    if(p!=NULL)
    {   postorder(p->left);
        postorder(p->right);
        printf("%d",p->data);
    }
}4.輸出二叉樹(shù)
首先輸出根結(jié)點(diǎn),然后再輸出它的左子樹(shù)和右子樹(shù).依次輸出的左,右子樹(shù)要至少有一個(gè)不能為空.
void print(btree *b)
{
    if(b!=NULL)
    {   printf("%d",b->data);
        if(b->left!=NULLb->right!=NULL)
        {   printf("(");
            printf(b->left);
            if(b->right!=NULL)printf(",");
            printf(b->right);
            printf(")");
        }
    }
}5.求二叉樹(shù)的深度
若一棵二叉樹(shù)為空,則其深度為0,否則其深度等于左子樹(shù)和右子樹(shù)的最大深度加1,即有如下遞歸模型:
depth(b)=0                                  /*假如b=NULL*/
depth(b)=max(depth(b->left,b->right)+1      /*其它*/
因此求二叉樹(shù)深度的遞歸函數(shù)如下:
int depth(btree *b)
{
    int dep1,dep2;
    if(b==NULL)return(0);
    else
    {   dep1=depth(b->left);
        dep2=depth(b->right);
        if(dep1>dep2)return(dep1+1);
        else return(dep2+1);
    }
}

上一篇：多文件內(nèi)核模塊

下一篇：第四篇：達(dá)到目標(biāo)必經(jīng)的路之二