數(shù)據結構中二叉樹基本操作學習

谷歌瀏覽器2016(Chrome)v50.0.2661.75 官方正式版

• 類型：瀏覽器類大小：43.2M語言：中文 評分：6.0
• 標簽：

立即下載

近日受人所托，搞了點二叉樹的程序，順便回顧了下二叉樹的一些基本知識，特此總結。

二叉樹的基本操作，可能包括：

創(chuàng)建，遍歷，轉化，復制，刪除等。

遍歷：前中后三種順序的遍歷，已經是各數(shù)據結構與算法教程的最基礎內容，在此不重復。

創(chuàng)建：大多數(shù)據結構教程當中的二叉樹創(chuàng)建程序，都是采用的遞歸方式，遞歸方式創(chuàng)建的二叉樹與遍歷的過程相似，所創(chuàng)建的二叉樹，也是采用左右子節(jié)點方式，后續(xù)進行遍歷操作十分方便。

轉化：直覺上，最簡單的二叉樹存儲方式其實是如下圖的數(shù)組：

*此圖出自某高校數(shù)據結構ppt，但實在難以查證是哪個學校，無法直接感謝，請諒解。

首先，提供個滿二叉樹大小的數(shù)組，然后其中數(shù)值按完全二叉樹存儲。顯然，此種順序存儲方法：第i號（這里編號指對應的完全二叉樹的位序）結點的左右孩子一定保存在第2i及2i+1號單元中。故此，為兼顧存儲的直觀與遍歷等操作的方便，從順序數(shù)組向左右子節(jié)點存儲方式的轉化也就十分重要。

1-轉化方法

分為幾個步驟：

（1）準備原始數(shù)組

（2）分析數(shù)組中的有效值，對應二叉樹節(jié)點非空；

（3）創(chuàng)建二叉樹節(jié)點；

（4）計算除最后一層子節(jié)點外，構造節(jié)點間父子關系時的循環(huán)次數(shù)；

（5）構造二叉樹節(jié)點間的父子關系；

（6）確實二叉樹根節(jié)點；

主要代碼：

（1）準備原始數(shù)組

//原始數(shù)組
    int intBiTreeInit[ARR_COUNT];

   
    //初始化原始數(shù)組至無效值
    for(int i=0;i<=ARR_COUNT-1;i++)
 intBiTreeInit[i]=NVALUE;

    //本if條件確保ARR_COUNT是否是的乘方-1
    if(0==(ARR_COUNT & (ARR_COUNT+1)))
    {
 for(int i=0;i<=ARR_COUNT-1;i++)
     intBiTreeInit[i]=2*(i+1);
    }
    else
 return RET_ERR;

    //使最后兩數(shù)為無效值
    intBiTreeInit[ARR_COUNT-1]=NVALUE;
    intBiTreeInit[ARR_COUNT-2]=NVALUE;

（2）分析數(shù)組中的有效值

    //開始獲得數(shù)組中有效值位置
    int intRel=0;
    int intArr=0;
    for(intArr=0;intArr<=intCount-1;intArr++)
    {
 if(elemArr[intArr]!=elemNValue)
 {
     intRel++;
     vecIntEffPos.push_back(intArr);
 }
 }

（3）創(chuàng)建二叉樹節(jié)點

    //數(shù)組中有效值對應創(chuàng)建節(jié)點
    //同時初始化父子節(jié)點為NULL
    for(intArr=0;intArr<=intRel-1;intArr++)
    {
 pBiTreeTemp=(PBiTreeNode)malloc(sizeof(BiTreeNode));;
 
 if(NULL==pBiTreeTemp)    //判斷是否有足夠的內存空間
 {
     cout<<"Memory alloc failure"<<endl;
     return RET_ERR;
 }

 //將有效值賦予節(jié)點
 pBiTreeTemp->BiTreeData=elemArr[vecIntEffPos[intArr]];
 
 //初始化左右子節(jié)點為null,便于后續(xù)的遍歷
 pBiTreeTemp->leftChild=NULL;
 pBiTreeTemp->rightChild=NULL;

 //先存節(jié)點值
 vecPBiTree.push_back(pBiTreeTemp);
　　　}

（4）計算除最后一層子節(jié)點外，構造節(jié)點間父子關系時的循環(huán)次數(shù)

//生成父子關系時最后一層不必遍歷,故理論循環(huán)上限可優(yōu)化

    int intSubLast=0;
    intSubLast=intCount-(intCount+1)/2;

（5）構造二叉樹節(jié)點間的父子關系

    for(intArr=0;intArr<=intSubLast-1;intArr++)
    {
 //左右節(jié)點若存儲有效值則同時創(chuàng)建父子關系
 if(elemArr[intArr*2+1]!=elemNValue)
     vecPBiTree[intArr]->leftChild=vecPBiTree[intArr*2+1];
     
 if(elemArr[intArr*2+2]!=elemNValue)
     vecPBiTree[intArr]->rightChild=vecPBiTree[intArr*2+2];
　　}

（6）確實二叉樹根節(jié)點

pBiTree=vecPBiTree[0];

轉化為左右子節(jié)點方式存儲后，則各種遍歷操作按大多數(shù)教程的常規(guī)方式處理即可，如前序遍歷函數(shù)：

int BiTreePreTrace(PBiTreeNode &pBiTree)
{
    //條件為非空樹
    if(pBiTree)
    {
 cout<<"Node value="<<(pBiTree->BiTreeData)<<endl;
 
 BiTreePreTrace(pBiTree->leftChild);    //遍歷左子樹
 BiTreePreTrace(pBiTree->rightChild);    //遍歷右子樹
    }
    return RET_OK;
}

完整程序，請見附件文件。

*上述程序在Windows7x64，vs2008環(huán)境編譯運行通過。