[工學(xué)]數(shù)據(jù)結(jié)構(gòu)試驗(yàn)-資料下載頁(yè)
2025-08-21 14:22本頁(yè)面
【正文】 二叉樹(shù)，采用二叉鏈表存儲(chǔ)；(2) 前序（或中序、后序）遍歷該二叉樹(shù)。二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)如圖所示。lchilddatarchild圖 二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)二叉鏈表的結(jié)點(diǎn)用C++中的結(jié)構(gòu)類型描述為： template class T struct BiNode ｛ T data； BiNodeT * lchild，*rchild； ｝； 設(shè)計(jì)實(shí)驗(yàn)用二叉鏈表類BiTree，類中包含遍歷操作。 template class T class BiTree ｛ public： BiTree(BiNodeT *root)；//有參構(gòu)造函數(shù),初始化一棵二叉樹(shù)，//其前序序列由鍵盤輸入 ~BiTree（）； //析構(gòu)函數(shù)，釋放二叉鏈表中各結(jié)點(diǎn)的存儲(chǔ)空間 void PreOrder(BiNodeT *root)；//前序遍歷二叉樹(shù) void InOrder(BiNodeT *root)；//中序遍歷二叉樹(shù) void PostOrder(BiNode T＞ *root)； //后序遍歷二叉樹(shù) private： BiNodeT＞ *root； //指向根結(jié)點(diǎn)的頭指針 void Creat(BiNodeT *root)； //有參構(gòu)造函數(shù)調(diào)用 void Release(BiNodeT*root)； //析構(gòu)函數(shù)調(diào)用 ｝；設(shè)計(jì)構(gòu)造函數(shù)，建立一棵二叉樹(shù)的二叉鏈表存儲(chǔ)。將二叉樹(shù)中每個(gè)結(jié)點(diǎn)的空指針引出一個(gè)虛結(jié)點(diǎn)，其值為一特定值如＃，以標(biāo)識(shí)其為空，把這樣處理后的二叉樹(shù)稱為原二叉樹(shù)的擴(kuò)展二叉樹(shù)。擴(kuò)展二叉樹(shù)的一個(gè)遍歷序列就能惟一確定一棵二叉樹(shù)。假設(shè)擴(kuò)展二叉樹(shù)的前序遍歷序列由鍵盤輸人，root為指向根結(jié)點(diǎn)的指針，二叉鏈表的建立過(guò)程是：首先輸人根結(jié)點(diǎn)，若輸人的是一個(gè)＃字符，則表明該二叉樹(shù)為空樹(shù)，即root =NULL；否則輸人的字符應(yīng)該賦予root data，之后依次遞歸建立它的左子樹(shù)和右子樹(shù)。建立二叉鏈表的遞歸算法如下：二叉樹(shù)的構(gòu)造函數(shù)算法BiTreetemplateclass TBiTree :: BiTree (BiNodeT *root){root = creat( )。}template class TBiNodeT * BiTree :: Creat( ){Cinch。if (ch = =’’) return NULL。 //建立一棵空樹(shù) else{ root = new BiNodeT。 //生成一個(gè)結(jié)點(diǎn) root data = ch。 root lchild = Creat( )。 //遞歸建立左子樹(shù) root rchile = Creat( )。 //遞歸建立右子樹(shù)}}
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1