前言

記錄實(shí)驗(yàn)，同時也是記錄常見數(shù)據(jù)結(jié)構(gòu)算法的實(shí)現(xiàn)。

---

廣州大學(xué)學(xué)生實(shí)驗(yàn)報(bào)告

開課實(shí)驗(yàn)室：計(jì)算機(jī)科學(xué)與工程實(shí)驗(yàn)（電子樓416A）
學(xué)院 計(jì)算機(jī)科學(xué)與網(wǎng)絡(luò)工程學(xué)院
實(shí)驗(yàn)課程 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)
實(shí)驗(yàn)項(xiàng)目 實(shí)驗(yàn)二 二叉樹的操作與實(shí)現(xiàn)

• 一、實(shí)驗(yàn)?zāi)康?#xff1a;
  1、二叉樹的基本操作算法實(shí)現(xiàn)
  2、二叉樹的各種遍歷算法實(shí)現(xiàn)
  3、線索二叉樹的遍歷
  4、構(gòu)造哈夫曼樹和哈夫曼編碼的算法實(shí)現(xiàn)
• 二、使用儀器、器材
  微機(jī)一臺
  操作系統(tǒng)：Win10
  編程軟件：C++
• 三、實(shí)驗(yàn)內(nèi)容及原理
  1、二叉樹的基本操作算法實(shí)現(xiàn) （返回目錄🖱）

#include <iostream> using namespace std;int leave_counts = 0;//-----二叉樹的二叉鏈表表示----- typedef struct BiTNode {char data;BiTNode* lchild, * rchild; }BiTNode, *BiTree;//-----先序遍歷建立二叉樹----- void CreatBiTNode(BiTree& T,const char *str) {BiTNode* ParentTNode[20], * p = NULL;int top = -1, k=0, j = 0;char ch;T = NULL;ch = str[j];while (ch != '\0'){switch (ch){case'(':top++; ParentTNode[top] = p; k = 1; break;case')':top--; break;case',':k = 2; break;default: p = new BiTNode;p->data = ch;p->lchild = NULL;p->rchild = NULL;if (T == NULL) T = p;switch (k){case 1:ParentTNode[top]->lchild = p; break;case 2:ParentTNode[top]->rchild = p; break;}}j++;ch = str[j];} }//-----查找某節(jié)點(diǎn)----- BiTNode* FindTNodeChild(BiTree T, char ch) {BiTNode* p;if (T == NULL) return NULL;else if (T->data == ch)return T;else{p = FindTNodeChild(T->lchild, ch);if ( p!= NULL)return p;elsereturn FindTNodeChild(T->rchild, ch);} }//-----先序遍歷輸出二叉樹----- void ShowBiTree(BiTree T) {if (T){cout << T->data;ShowBiTree(T->lchild);ShowBiTree(T->rchild);} }//-----輸出二叉樹的結(jié)點(diǎn)個數(shù)----- int NodeCount(BiTree &T) {if (T == NULL) return 0;else return NodeCount(T->lchild) + NodeCount(T->rchild)+1; }//-----輸出二叉樹的度----- int DegreeCount(BiTree T) {return NodeCount(T) - 1; }//-----輸出二叉樹的葉子數(shù)----- int LeaveCount(BiTree T) {if (T != NULL){if (T->lchild == NULL && T->rchild == NULL)leave_counts ++;LeaveCount(T->lchild);LeaveCount(T->rchild);return leave_counts;} }//-----輸出二叉樹的深度----- int DepthOfTree(BiTree T) {if (T == NULL) return 0;else{int depth_l = DepthOfTree(T->lchild);int depth_r = DepthOfTree(T->rchild);if (depth_l <= depth_r) return depth_r + 1;else return depth_l + 1;} }int main() {BiTree T = new BiTNode;const char* ch = "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))\0";CreatBiTNode(T,ch);//先序遍歷輸出cout << "先序遍歷輸出：";ShowBiTree(T);//輸出A的左右孩子BiTNode* p = FindTNodeChild(T,'A');if (p->lchild != NULL && p->rchild != NULL) cout << "\n結(jié)點(diǎn)A的左孩子：" << p->lchild->data << "\t右孩子：" << p->rchild->data<<endl;else if (p->lchild != NULL && p->rchild == NULL)cout << "結(jié)點(diǎn)A的左孩子：" << p->lchild->data;else if(p->lchild == NULL && p->rchild != NULL) cout << "結(jié)點(diǎn)A的右孩子：" << p->lchild->data;//結(jié)點(diǎn)數(shù)cout << "結(jié)點(diǎn)數(shù): " << NodeCount(T) << endl;//葉子數(shù)cout << "葉子數(shù): " << LeaveCount(T) << endl;//度cout << "度: " << DegreeCount(T) << endl;//深度cout << "深度" << DepthOfTree(T) << endl; }

2、二叉樹的各種遍歷算法實(shí)現(xiàn) （返回目錄🖱）

#include <iostream> using namespace std;int leave_counts = 0;//-----二叉樹的二叉鏈表表示----- typedef struct BiTNode {char data;BiTNode* lchild, * rchild; }BiTNode, * BiTree;//-----用棧來實(shí)現(xiàn)二叉鏈表的非遞歸----- typedef struct BiTNodeStack {BiTNode* data;BiTNodeStack* next; }BiTNodeStack,*BiTStack; //-----初始化棧----- void InitStack(BiTStack& s) {s = new BiTNodeStack;s->data = NULL;s->next = NULL; } //-----彈出----- BiTNode* Pop(BiTStack s) {BiTNodeStack* p = new BiTNodeStack;p = s->next;s->next = p->next;return p->data; } //-----放入----- void Push(BiTStack &s,BiTNode *p) {BiTNodeStack* sp = new BiTNodeStack;sp->data = p;sp->next = s->next;s->next = sp; }//-----先序遍歷建立二叉樹----- void CreatBiTNode(BiTree& T, const char* str) {BiTNode* ParentTNode[20], * p = NULL;int top = -1, k = 0, j = 0;char ch;T = NULL;ch = str[j];while (ch != '\0'){switch (ch){case'(':top++; ParentTNode[top] = p; k = 1; break;case')':top--; break;case',':k = 2; break;default: p = new BiTNode;p->data = ch;p->lchild = NULL;p->rchild = NULL;if (T == NULL) T = p;switch (k){case 1:ParentTNode[top]->lchild = p; break;case 2:ParentTNode[top]->rchild = p; break;}}j++;ch = str[j];} }//-----遞歸先序遍歷輸出二叉樹----- void ShowBiTree_preorder(BiTree T) {if (T){cout << T->data;ShowBiTree_preorder(T->lchild);ShowBiTree_preorder(T->rchild);} } //-----非遞歸先序遍歷輸出二叉樹----- void ShowBiTree_preorder_0(BiTree T) {BiTNode* p = new BiTNode;p = T;BiTStack s;InitStack(s);while (p || s->next != NULL){while (p){cout << p->data;Push(s, p);p = p->lchild;}if (s->next != NULL){p = Pop(s);p = p->rchild;}} } //-----遞歸中序遍歷輸出二叉樹----- void ShowBiTree_inorder(BiTree T) {if (T){ShowBiTree_inorder(T->lchild);cout << T->data;ShowBiTree_inorder(T->rchild);} } //-----非遞歸中序遍歷輸出二叉樹----- void ShowBiTree_inorder_0(BiTree T) {BiTNode* p = new BiTNode;p = T;BiTStack s ;InitStack(s);while (p || s->next != NULL){if (p){Push(s, p);p = p->lchild;}else{BiTNode* q = new BiTNode;q = Pop(s);cout << q->data;p = q->rchild;}} }//-----遞歸后序遍歷輸出二叉樹----- void ShowBiTree_postorder(BiTree T) {if (T){ShowBiTree_postorder(T->lchild);ShowBiTree_postorder(T->rchild);cout << T->data;} } //-----非遞歸后序遍歷輸出二叉樹----- void ShowBiTree_postorder_0(BiTree T) {BiTNode* p = new BiTNode;p = T;BiTStack s1,s2;InitStack(s1);InitStack(s2);while (p || s1->next != NULL){while (p){Push(s2, p);Push(s1, p);p = p->rchild;}if (s1->next != NULL){p = Pop(s1);p = p->lchild;}}while (s2->next != NULL){p = Pop(s2);cout << p->data;} }int main() {BiTree T = new BiTNode;const char* ch = "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))\0";CreatBiTNode(T, ch);//遞歸先序遍歷輸出cout << "先序遍歷輸出：";ShowBiTree_preorder(T);cout <<" (遞歸)"<<endl;//非遞歸先序遍歷輸出cout << "先序遍歷輸出：";ShowBiTree_preorder_0(T);cout << " (非遞歸)" << endl<<"----------------"<<endl;//遞歸中序遍歷輸出cout << "中序遍歷輸出：";ShowBiTree_inorder(T);cout << " (遞歸)" << endl;//非遞歸中序遍歷輸出cout << "中序遍歷輸出：";ShowBiTree_inorder_0(T);cout << " (非遞歸)" << endl << "----------------" << endl;//遞歸后序遍歷輸出cout << "后序遍歷輸出：";ShowBiTree_postorder(T);cout << " (遞歸)" << endl;//非遞歸后序遍歷輸出cout << "后序遍歷輸出：";ShowBiTree_postorder_0(T);cout << " (非遞歸)" << endl;}

3、線索二叉樹的遍歷 （返回目錄🖱）

#include<iostream> using namespace std;//-----線索二叉樹----- typedef struct BiThrNode {char data;BiThrNode* lchild, * rchild;int LTag, RTag; }BiThrNode,*BiThrTree;BiThrNode* pre = new BiThrNode; // 全局變量pre //-----先序遍歷建立二叉樹----- void CreatBiTNode(BiThrTree& T, const char* str) {BiThrNode* ParentTNode[20], * p = NULL;int top = -1, k = 0, j = 0;char ch;T = NULL;ch = str[j];while (ch != '\0'){switch (ch){case'(':top++; ParentTNode[top] = p; k = 1; break;case')':top--; break;case',':k = 2; break;default: p = new BiThrNode;p->data = ch;p->lchild = NULL;p->rchild = NULL;if (T == NULL) T = p;switch (k){case 1:ParentTNode[top]->lchild = p; break;case 2:ParentTNode[top]->rchild = p; break;}}j++;ch = str[j];} }//-----中序線索化二叉樹----- void InThreading(BiThrTree p) {pre->LTag = 0;pre->RTag = 0;pre->rchild = NULL;if (p){InThreading(p->lchild);if (!p->lchild){p->LTag = 1;p->lchild = pre;}else p->LTag = 0;if (!pre->rchild){pre->RTag = 1;pre->rchild = p;}else pre->RTag = 0;pre = p;InThreading(p->rchild);} }//-----帶頭結(jié)點(diǎn)的二叉樹中序線索化----- void InOrderThreading(BiThrTree& Thrt, BiThrTree T) {Thrt = new BiThrNode;Thrt->LTag = 0;Thrt->RTag = 1;Thrt->rchild = Thrt;if (!T) Thrt->lchild = Thrt;else{Thrt->lchild = T; pre = Thrt;InThreading(T);pre->rchild = Thrt;pre->RTag = 1;Thrt->rchild = pre;} }//-----先序遍歷輸出二叉樹----- void ShowBiTree(BiThrTree T) {if (T){cout << T->data;ShowBiTree(T->lchild);ShowBiTree(T->rchild);} }int main() {BiThrTree T = new BiThrNode;const char* ch = "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";//先序遍歷構(gòu)造二叉樹CreatBiTNode(T, ch);//二叉樹中序線索化BiThrTree Thrt = new BiThrNode;InOrderThreading(Thrt, T);//輸出根節(jié)點(diǎn)的前驅(qū)和后繼/*中序線索化時引入了頭結(jié)點(diǎn)，所以根節(jié)點(diǎn)的前驅(qū)即為頭結(jié)點(diǎn)*/cout << "根結(jié)點(diǎn)的前驅(qū)：" << Thrt << "（Thrt）"<<endl;cout << "根結(jié)點(diǎn)的后繼：" << Thrt->lchild->rchild->data;}

4、構(gòu)造哈夫曼樹和哈夫曼編碼的算法實(shí)現(xiàn)（返回目錄🖱）

#include"stdio.h" #include"string.h" #include"malloc.h" #include"iostream" using namespace std; typedef struct HTNode {unsigned int weight;unsigned int parent, lchild, rchild; }HTNode, * HuffTree; typedef char** HuffCode;//------選擇權(quán)值最小的兩個結(jié)點(diǎn)的下標(biāo)----- void Select(HuffTree& Ht, int m, int& S1, int& S2) {S1 = 0;S2 = 0;for (int j = 1; j <= m; j++){if (Ht[j].parent == 0 && Ht[j].weight != 0){if (Ht[j].weight < Ht[S1].weight)S1 = j;}}for (int j = 1; j <= m; j++){if (Ht[j].parent == 0 && j != S1 && Ht[j].weight != 0){if (Ht[j].weight < Ht[S2].weight)S2 = j;}}cout <<S1 << " " << S2 << endl;; }//-----哈夫曼編碼函數(shù)----- void HuffmanCoding(HuffTree& Ht, HuffCode& Hc, int n, char text[]) { if (n <= 1)return;int m, i, s1, s2;HuffTree p;m = 2 * n - 1;Ht = (HuffTree)malloc((m + 1) * sizeof(HTNode));for (p = Ht + 1, i = 1; i <= m; ++i, ++p) { //初始化哈夫曼樹各個值 p->weight = 0;p->parent = 0;p->lchild = 0;p->rchild = 0;}//讀入一段文本 for (int i = 0; text[i] != '\0'; i++) {Ht[text[i] - 'a' + 1].weight++; //當(dāng)文本還沒有結(jié)束時，統(tǒng)計(jì)各個字符的權(quán)值 }//構(gòu)建哈夫曼樹for (i = n + 1; i <= m; ++i) { Select(Ht, i - 1, s1, s2);Ht[s1].parent = i; Ht[s2].parent = i;Ht[i].lchild = s1; Ht[i].rchild = s2;Ht[i].weight = Ht[s1].weight + Ht[s2].weight;}// -------從葉子到根逆向求每個字符的哈夫曼編碼------Hc = (HuffCode)malloc((n + 1) * sizeof(char*)); //貌似不能用new，所以使用c語言的動態(tài)申請char* cd = (char*)malloc((n) * sizeof(char));cd[n - 1] = '\0'; //編碼結(jié)束符 int start;for (i = 1; i <= n; ++i) {start = n - 1;int parent = 0; //暫存父節(jié)點(diǎn)下標(biāo)int c = 0;for (c = i, parent = Ht[i].parent; parent != 0; c = parent, parent = Ht[parent].parent){if (Ht[parent].lchild == c)cd[--start] = '0';else cd[--start] = '1';}//cd[n-1]='\0';Hc[i] = new char[26];//動態(tài)申請某字母哈夫曼編碼的空間strcpy(Hc[i], &cd[start]);}free(cd);}//------輸出哈夫曼編碼------ void show(HuffCode& Hc, int n) {cout << "\n輸出哈夫曼編碼:\n"; for (int i = 1; i <= n; i++){cout <<char(i-1+'a')<<"："<< Hc[i];cout << "\n";}} int main() {HuffTree ht;HuffCode hc;int n;char text[] = "The Chinese official said he viewed the TrumpPresidency not as an aberration but as the product of a failing political system. This jibes with other accounts. The Chinese leadership believes that the United States, and Western democracies in general, haven’t risen to the challenge of a globalized economy, which necessitates big changes in production patterns, as well as major upgrades in education and public infrastructure. In Trump and Trumpism, the Chinese see an inevitable backlash to this failure";char* text_transform = strlwr(text); //全部轉(zhuǎn)化為小寫 HuffmanCoding(ht, hc, 26, text_transform);show(hc, 26); }

四、實(shí)驗(yàn)過程原始數(shù)據(jù)記錄
1、二叉樹的基本操作算法實(shí)現(xiàn)

2、二叉樹的各種遍歷算法實(shí)現(xiàn)

3、線索二叉樹的遍歷

4、構(gòu)造哈夫曼樹和哈夫曼編碼的算法實(shí)現(xiàn)

五、實(shí)驗(yàn)結(jié)果及分析
在二叉樹的操作當(dāng)中，有許多步驟的思路是一樣的，所以遞歸在二叉樹中的使用會更加廣泛。我覺得遞歸的思想能在二叉樹的操作中得到很好的鍛煉。二叉樹在數(shù)據(jù)壓縮等方面以其的特性而廣泛被應(yīng)用，所以我覺得掌握二叉樹在某些實(shí)際應(yīng)用中的實(shí)現(xiàn)方法也是特別重要的。

總結(jié)

以上是生活随笔為你收集整理的实验二 二叉树的操作与实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。