数据结构-实验二 二叉树的操作与实现 1、二叉树的基本操作算法实现 (1) 利用(广义表)二叉树字符串“A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”创建二叉树 的二叉链式存储结构;(请勿根据扩展二叉树进行创建)
(2) 输出该二叉树(中序遍历序列);
(3) 输出‘H’结点的左、右孩子结点值;
(4) 输出该二叉树的结点个数、叶子结点个数、二叉树的度和高度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 #include <iostream> #include <string> #include <algorithm> #include <math.h> using namespace std;typedef struct Tree { char data; struct Tree * leftchild, * rightchild; }tree,*treenode; typedef struct Stack { tree* data; struct Stack * next; }stack,*stacknode; stacknode createstack () { stacknode root = new stack; root->data = NULL ; root->next = NULL ; return root; } void addstack (stacknode root, tree* data) { stack* node = new stack; node->data = data; node->next = root->next; root->next = node; } tree* popstack (stacknode& root) { if (root->next == NULL ) { return NULL ; }else { stack* node = root->next; root->next = node->next; tree* data = node->data; delete node; return data; } } tree* topstack (stacknode& root) { if (root->next == NULL ) { return NULL ; } else { stack* node = root->next; return node->data; } } bool empty (stacknode root) { if (root->next == NULL ) { return true ; } return false ; } void createTree (treenode &root,string& stringdata) { stacknode stackroot = createstack (); tree* current = NULL ; bool isleft = true ; for (char it : stringdata) { if (it == '(' ) { addstack (stackroot, current); isleft = true ; continue ; } else if (it == ')' ) { popstack (stackroot); } else if (it == ',' ) { isleft = false ; } else { treenode node = new tree; node->data = it; node->leftchild = NULL ; node->rightchild = NULL ; if (empty (stackroot)) { root = node; }else { tree* parent = topstack (stackroot); if (isleft) { parent->leftchild = node; } else { parent->rightchild = node; } } current = node; } } } void inorder (treenode& root) { if (root == NULL ) { return ; } else { inorder (root->leftchild); cout << root->data << "---" ; inorder (root->rightchild); } } int returnlength (treenode root) { return root == NULL ? 0 : max (returnlength (root->leftchild),returnlength (root->rightchild)) + 1 ; } int returngeshu (treenode root) { return root == NULL ? 0 : returngeshu (root->leftchild) + returngeshu (root->rightchild) + 1 ; } int returnyezishu (treenode root) { if (root == NULL ) { return 0 ; } if (root->leftchild == NULL && root->rightchild == NULL )return 1 ; return returnyezishu (root->leftchild) + returnyezishu (root->rightchild); } void printChildren (treenode root, char target) { if (root == NULL ) { return ; } if (root->data == target) { cout << "结点 " << target << " 的孩子: " ; if (root->leftchild) { cout << "左孩子: " << root->leftchild->data << " " ; }else { cout << "左孩子: NULL " ; } if (root->rightchild) { cout << "右孩子: " << root->rightchild->data << endl; }else { cout << "右孩子: NULL" << endl; } return ; } printChildren (root->leftchild, target); printChildren (root->rightchild, target); } int maxDegree (treenode root) { return (returngeshu (root) - returnyezishu (root)) * 2 + returnyezishu (root); } int main () { cout << "请输入二叉树的广义表的表示形式:" << endl; string stringdata; cin >> stringdata; treenode root; createTree (root, stringdata); inorder (root); cout << "输入任意结点,我会返回他的的左、右孩子结点值" << endl; char target; cin >> target; printChildren (root, target); cout << "这个二叉树的节点个数为:" << returngeshu (root) << endl; cout << "这个二叉树的叶子节点个数为:" << returnyezishu (root) << endl; cout << "这个二叉树的高度为:" << returnlength (root) << endl; cout << "这个二叉树的度为:" << maxDegree (root) << endl; return 0 ; }
2.参考数据: 1 A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))
3.参考结果: 1 2 3 4 5 6 7 8 9 请输入二叉树的广义表的表示形式: A (B (D,E (H (J,K (L,M (,N))))),C (F,G (,I)))D---B---J---H---L---K---M---N---E---A---F---C---G---I---输入任意结点,我会返回他的的左、右孩子结点值 N 结点 N 的孩子: 左孩子: NULL 右孩子: NULL 这个二叉树的节点个数为:14 这个二叉树的叶子节点个数为:6 这个二叉树的高度为:7 这个二叉树的度为:22
2、二叉树的各种遍历算法实现 实现上述二叉树的先序、中序和后序遍历的递归和非递归算法。
1.先序,中序的非递归遍历 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 #include <stdlib.h> #include <iostream> using namespace std;typedef struct Tree { char data; struct Tree * leftchild; struct Tree * rightchild; }tree, * treelist; typedef struct stacknode { tree* data; struct stacknode * next; }node, * stack; void createTree (treelist& app) { char ch; cin >> ch; if (ch == '#' ) { app = NULL ; } else { app = new Tree; app->data = ch; createTree (app->leftchild); createTree (app->rightchild); } } void initstack (stack root) { root->data = NULL ; root->next = NULL ; } void pushstack (stack root, tree* app) { node* stackapp = (node*)malloc (sizeof (node)); stackapp->data = app; stackapp->next = root->next; root->next = stackapp; } bool isempty (stack root) { if (root->next == NULL ) { return true ; } else { return false ; } } node* popstack (stack root) { if (isempty (root)) { return NULL ; } else { node* app = root->next; root->next = app->next; return app; } } void preorder (treelist app) { treelist APP = app; stack stackAPP = new node; initstack (stackAPP); while (APP || !isempty (stackAPP)) { if (APP) { cout << APP->data << "---" ; pushstack (stackAPP, APP); APP = APP->leftchild; } else { APP = popstack (stackAPP)->data; APP = APP->rightchild; } } } void inorder (treelist app) { treelist APP = app; stack stackAPP = new node; initstack (stackAPP); while (APP || !isempty (stackAPP)) { if (APP) { pushstack (stackAPP, APP); APP = APP->leftchild; } else { APP = popstack (stackAPP)->data; cout << APP->data << "---" ; APP = APP->rightchild; } } } int main () { treelist app; cout << "请输入二叉树的数据" << endl; createTree (app); cout << "先序遍历:" ; preorder (app); cout << "end" << endl; cout << "中序遍历:" ; inorder (app); cout << "end" << endl; return 0 ; }
就是借用了栈的用法,先序遍历就是先把左边的输出出来,同时伴随着入栈操作,到后面左子树为空的时候就出栈搞右子树的内容输出出来,右子树空了就再出栈…….;
中序遍历: 基本思想就是到左子树遍历到null的时候就出栈,打印出数据,只要为空就打印出栈中的数据
2.后序遍历的非递归的方法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 #include <iostream> using namespace std;typedef struct tree { char data; struct tree * lefttree, * righttree; bool flage; }; typedef struct stack { tree* data; struct stack * next; }*stacknode; void createtree (tree*& app) { char data; cin >> data; if (data == '#' ) { app = NULL ; } else { app = new tree; app -> data = data; app->flage = false ; createtree (app->lefttree); createtree (app->righttree); } } void initstack (stacknode &app) { app->data = NULL ; app->next = NULL ; } void addstack (stacknode& app, tree* data) { stacknode node = new stack; node->data = data; node->next = app->next; app->next = node; } tree* popstack (stacknode& app) { tree* data = app->next->data; stacknode number = app->next; app->next = number->next; delete number; return data; } tree* checkstack (stacknode& app) { return app->next->data; } bool isempty (stacknode& app) { if (app->next == NULL ) { return true ; } else { return false ; } } void postorder (tree* app) { tree* APP = app; stacknode stackdata = new stack; initstack (stackdata); while (APP || !isempty (stackdata)) { if (APP) { addstack (stackdata, APP); APP = APP->lefttree; } else { tree* top = checkstack (stackdata); if (top->righttree && top->righttree->flage == false ) { top = top->righttree; addstack (stackdata, top); APP = top->lefttree; } else { tree* topdata = popstack (stackdata); cout << topdata->data << "---" ; topdata->flage = true ; } } } } int main () { tree* app; createtree (app); cout << "后序遍历二叉树采用非递归的方法:" ; postorder (app); cout << "end" << endl; return 0 ; }
这里与上面的两个遍历有一点不一样,这个借助了一个flag来判断右子树有没有被访问过,如果没有就入栈,直到为NULL的时候出栈;如果右子树被访问过,那么就是不入栈……,依此不断重复…
3、线索二叉树的遍历 中序线索化上述二叉树并找出根结点的前驱和后继。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 #include <stdio.h> #include <stdlib.h> #include <iostream> using namespace std;typedef struct BiThrNode { char data; struct BiThrNode * leftchild; struct BiThrNode * rightchild; int LTag; int RTag; }BiThrNode, * BiThrTree; BiThrNode* pre = NULL ; void createTree (BiThrTree& app) { char ch; cin >> ch; if (ch == '#' ) { app = NULL ; } else { app = new BiThrNode; app->data = ch; app->LTag = 0 ; app->RTag = 0 ; createTree (app->leftchild); createTree (app->rightchild); } } void middleTree (BiThrTree &app) { if (app) { middleTree (app->leftchild); if (!app->leftchild) { app->LTag = 1 ; app->leftchild = pre; } if (pre != NULL && pre->rightchild == NULL ) { pre->RTag = 1 ; pre->rightchild = app; } pre = app; middleTree (app->rightchild); } } void middleprintf (BiThrTree& app) { BiThrNode* current = app; while (current && current->LTag == 0 ) { current = current->leftchild; } while (current) { cout << current->data << "---" ; if (current->RTag == 1 ) { current = current->rightchild; } else { current = current->rightchild; while (current && current->LTag == 0 ) { current = current->leftchild; } } } } int main () { BiThrTree app; createTree (app); middleTree (app); cout << "线索化中序二叉树的遍历为:" ; middleprintf (app); cout << "end" << endl; return 0 ; }
在这里的话就是使用递归的操作,加上了使用rTag与lTag两个标志,为0的时候表示的是左右子树,为1的时候就是表示有前驱或者后继,如果遍历到一个子树没有左子树的时候就指向他的前驱,右子树同理:指向后继……….;
线索化这个二叉树相当于就是重新对这个二叉树进行一个遍历以及对他的是否指向前驱或者后继还是左右子树进行一个修饰的过程;后面就是遍历线索二叉树,易于理解
4、构造哈夫曼树HT、哈夫曼编码HC、哈夫曼译码的算法实现。 在发送端,统计下面一段英文的不同字符个数和每个字符的出现频率,利用统 计数据构造构造哈夫曼树和哈夫曼编码;在接收端,将接收到的 0-1 序列恢复成英 文段落。
The Chinese official said he viewed the Trump Presidency 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 #include <iostream> #include <string> #include <map> using namespace std;map<char , int >dataweight; map<char , string>datacode; map<string, char >codedatainformation; #define max_size 9999 string stargeinformation; typedef struct { int weight; int parent; int leftchild; int rightchild; }Huffmannode,*HuffmanTree; void getweight (string& app) { for (auto spp : app) { dataweight[spp]++; } } HuffmanTree CreateHuffmanTree (int length) { int totallength = length * 2 - 1 ; HuffmanTree tree = (HuffmanTree)malloc (sizeof (Huffmannode) * (totallength)); for (int i = 0 ;i < totallength;i++) { tree[i].weight = 0 ; tree[i].leftchild = -1 ; tree[i].rightchild = -1 ; tree[i].parent = -1 ; } int index = 0 ; for (auto it : dataweight) { tree[index++].weight = it.second; } for (int i = length;i < totallength;i++) { int minnumber1 = -1 ; int minnumber2 = -1 ; for (int j = 0 ;j < i;j++) { if (tree[j].parent == -1 ) { if (minnumber1 == -1 || tree[minnumber1].weight > tree[j].weight) { minnumber2 = minnumber1; minnumber1 = j; } else if (minnumber2 == -1 || tree[minnumber2].weight > tree[j].weight) { minnumber2 = j; } } } tree[i].weight = tree[minnumber1].weight + tree[minnumber2].weight; tree[i].leftchild = minnumber1; tree[i].rightchild = minnumber2; tree[minnumber1].parent = i; tree[minnumber2].parent = i; } return tree; } void codehafuman (HuffmanTree& tree) { int stroenumber = 0 ; for (auto app : dataweight) { char datachar = app.first; string codedata = "" ; int current = stroenumber; int parent = tree[current].parent; while (parent != -1 ) { if (tree[parent].leftchild == current) { codedata = "0" + codedata; }else { codedata = "1" + codedata; } current = parent; parent = tree[current].parent; } datacode[datachar] = codedata; stroenumber++; } } string encoding (string stargeinformation) { string codedata = "" ; for (auto app : stargeinformation) { codedata += datacode[app]; } return codedata; } string skillcodehafuman (string& codedata,HuffmanTree&tree) { for (auto app : datacode) { codedatainformation[app.second] = app.first; } string stringdata = "" ; string datanumber = "" ; int number = dataweight.size () * 2 - 2 ; for (auto it : codedata) { if (it == '0' ) { number = tree[number].leftchild; datanumber += it; } else { number = tree[number].rightchild; datanumber += it; } if (tree[number].leftchild == -1 && tree[number].rightchild == -1 ) { stringdata += codedatainformation[datanumber]; number = dataweight.size () * 2 - 2 ; datanumber = "" ; } } return stringdata; } int main () { cout << "请输入文章内容:" << endl; string line; while (true ) { getline (cin, line); if (line.empty ()) { break ; } stargeinformation += line + "\n" ; } getweight (stargeinformation); HuffmanTree tree = CreateHuffmanTree (dataweight.size ()); codehafuman (tree); string codedata = encoding (stargeinformation); cout << codedata << endl; cout << endl; string relute = skillcodehafuman (codedata, tree); cout << relute << endl; free (tree); return 0 ; }
在这次的构造哈夫曼树编码的实验代码中,我使用3个map容器辅助存储字符的权值大小,以及存储单个字符的二进制编码,还有一个是逆序存储了二进制编码对应的字符;
基本思路就是书上的思路:这里数组来存储哈夫曼树,刚开始使用map的键值对存储输入字符的出现次数,接着利用map容器自带的size()表示长度,也就是叶子节点个数(有效存储信息的节点),往后就是依次储存到数组里面去;
后面在长度为n,在区间(n-n-2)里面存储度为二的父亲节点中依顺序在前n个节点依次找到两个权值最小的两个节点作为那个父亲节点的两个孩儿,依次往复,直到没有;
接着就是编码,从叶子节点往上面去编码左子树为0,右子树为1,直到根节点(根节点的parent为-1,这个判断是不是根节点),保存二进制到map容器中,键为字符,值为二进制编码,直到把所有的n个节点搞完;
然后又是利用循环对刚开始输入的文章进行循环,通过map存储的二进制数据对每一个字符进行编码;
最后就是译码了,,,从根节点出发一直到叶子节点,左子树为0,右子树为1,判断结束条件就是叶子节点的没有左右子树节点(leftchild==rightchile==-1),这样把这个二进制存下来,又通过最前面我提到的第三个map容器,他的作用就体现出来了,键存储的是之前的二进制编码,值就是字符,通过如此循环,再通过字符串的拼接就能译码成功了,就能重新搞出来一个刚才一样的文章了(^_^)
2.参考数据: 1 2 3 4 5 6 7 The Chinese official said he viewed the Trump Presidency 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.
3.参考结果: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 请输入文章内容: The Chinese official said he viewed the Trump Presidency 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. 000101000000111101000000000101101100010111001111110010101000101001011110001011101010011111011110101011010011110000001111100100010110011001001001010011111000000000111100010111011000110101111101011111001010111101100101111011010010010110110000100001111011011001100011110100111111101001101110100011010110100001110111101110101000101111001011011111010000011100011110100111111100000000011111101011101111001010010001111000100011111001010100111101011101010010101011100111011011001010111111010111001100111011100010111100010101001111101110100001011110000010101110101101111000101000010110111111010110011011110100001011111110010011011100000001111100110000000001110111110100011010110001100011001000110110100001110101101111000101000000111101000000000101101100010111001111100110011010010010011101101110000101111010111111010000110011101100110010000010111111100000001010100011110000000001111100101101011010111000001010011111001011001000101010000010111000100111101001100100111110010111000101111000001110110110111010001010010010101111100111000110111010110001011001011111110110110111010101001011000111011101010011000100111000010101001000001011010010100010010100110001111101110110111001011011110001100111110000000001111110000000101010011100110010110010101001111110010101001111010111010101100111100111010010101001110110101100000101001111001110001100101101100101011101000010001001110100011001001000010111100000001110110001110000010111011110111000101010000010111111110100101101010111111000000010100110010101001011111110110110111110101110111100101001000111100010001011110010110111110101101010001000001110110110011100010011110100111111100100100110011100111111010011111101011110100101100111001110111110001111010101010111011101001001001011111101000110110110111001010010001111000101010001011110010110111101001100100111111010100011110100100111011110001111011011001010011011101001111000110110001111000100000011110110010101101111100101010011011100010111011000110101111101011111010011001001111000101110110001101011111010110110111010111000100111100000000011110100000000010110110001011100111101110010011110100011010011011110110110001100100010111000101011010010011001111110100101011000100101111100111010011100001111000110011111000000010110111111010100101010111001100011110110010101101010001 The Chinese official said he viewed the Trump Presidency 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.