數(shù)據(jù)結(jié)構(gòu)第六章樹和二叉樹-資料下載頁
2025-05-14 21:43本頁面
【正文】 d。 Visit(pdata)。 // 訪問“右線索”所指后繼結(jié)點 } p = pRchild。 // p 進至其右子樹根 } 線索鏈表的生成 ? void InThreading(BiThrTree p， BiThrTreeamp。 pre) { // 對 p 指向根結(jié)點的二叉樹進行中序遍歷，遍歷過程中進行“中序線索化”。若 p 所指結(jié)點的左指針為空，則將它改為“左線索”，若 pre所指結(jié)點的右指針為空，則將它改為“右線索”。指針 pre 在遍歷過程中緊隨其后，即始終指向 p 所指結(jié)點在中序序列中的前驅(qū)。 if (p) { InThreading(pLchild, pre)。 // 對左子樹進行線索化 if (!pLchild) { pLTag = Thread。 pLchild = pre。 } // 建前驅(qū)線索 if (!preRchild) { preRTag = Thread。 preRchild = p。 } // 建后繼線索 pre = p。 // 保持 pre 指向 p 的前驅(qū) InThreading(pRchild, pre)。 // 對右子樹進行線索化 } } ? void InOrderThreading(BiThrTree amp。Th, BiThrTree BT) { // BT為指向二叉樹根結(jié)點的指針，由此二叉鏈表建立二叉樹的中序線索鏈表， Thead 指向線索鏈表中的頭結(jié)點。 BiThrTree pre。 if (!(Th = new BiThrNode)) exit (1)。 // 存儲分配失敗 ThLTag = Link。 ThRTag =Thread。 // 建頭結(jié)點 ThRchild = Th。 // 右指針回指 if (!BT) ThLchild = Th。 // 若二叉樹空，則左指針回指 else { ThLchild = BT。 pre = Thead。 InThreading(BT, pre)。 // 中序遍歷進行中序線索化 preRchild = Th。 preRTag = Thead。 // 對中序序列中最后一個結(jié)點進行線索化 ThRchild = pre。 // 建非空樹的頭結(jié)點的 右線索 } } 樹和森林的存儲表示 1 樹的雙親表示法 ? const MAX_TREE_SIZE = 100。 ? typedef struct { // 結(jié)點結(jié)構(gòu) ElemType data。 int parent。 // 雙親位置域 } PTNode。 ? typedef struct { // 樹結(jié)構(gòu) PTNode nodes[MAX_TREE_SIZE]。 int r, n。 // 根的位置和結(jié)點數(shù) } PTree。 2 樹的孩子表示法 ? 樹的孩子鏈表存儲表示 typedef struct CTNode { // 孩子結(jié)點 int child。 struct CTNode *next。 } *ChildPtr。 ? typedef struct { ElemType data。 // 結(jié)點的數(shù)據(jù)元素 ChildPtr firstchild。 // 孩子鏈表頭指針 } CTBox。 ? typedef struct { CTBox nodes[MAX_TREE_SIZE]。 int n, r。 // 結(jié)點數(shù)和根結(jié)點的位置 } CTree。 3 樹和森林的孩子兄弟表示法 ? 存儲表示 typedef struct CSNode{ ElemType data。 struct CSNode *firstchild, *nextsibling。 } CSNode, *CSTree。 ? firstchild 指向該結(jié)點的 第一個 子樹根結(jié)點，nextsibling 指向它的 下一個 兄弟結(jié)點。 樹的孩子 兄弟鏈表 森林的孩子 兄弟鏈表 森林和二叉樹的轉(zhuǎn)換 ? 森林－ 二叉樹 ? 二叉樹 ?森林 樹的遍歷 ? 一、先根 (次序 )遍歷樹 若樹不空，則先訪問根結(jié)點，然后依次從左到右先根遍歷根的各棵子樹； ? ABEHIJCDFGK ? 二、后根 (次序 )遍歷樹 若樹不空，則先依次從左到右后根遍歷根的各棵子樹，然后訪問根結(jié)點； ? HIJEBCFKGDA 森林的遍歷 ? 一、先序遍歷森林 若森林不空，則可依下列次序進行遍歷 (1) 訪問森林中第一棵樹的根結(jié)點； (2) 先序遍歷第一棵樹中的子樹森林； (3) 先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。 ? 二、中序遍歷森林 若森林不空，則可依下列次序進行遍歷： (1) 中序遍歷第一棵樹中的子樹森林； (2) 訪問森林中第一棵樹的根結(jié)點； (3) 中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。 求森林的深度 ? 森林的深度 = Max{每一棵樹的深度 } 樹的深度 = 其子樹森林的深度 +1 ? int Depth_Tree( CSTree T ) { // T 是以孩子 兄弟鏈表存儲的森林的頭指針，返回該森林的深度 if (!T) return 0。 else { dep = 0。 // 初始化森林的深度為 0 p = T。 // 指針 p 指向第一棵樹的根 while (p) { d = Depth_Tree(pfirstchild)。 // 返回 *p 的子樹森林的深度 if (d+1dep) dep=d+1。 // 求各棵樹的深度的最大值 p=pnextsibling。 // 指針 p 移向下一棵樹的根 } return dep。 } }
公司管理相關(guān)推薦
鄂ICP備17016276號-1