做衣服接订单的网站,做网站去哪好,wordpress postpass,360搜索首页树与二叉树 计算机中的树树的概念树的类型 什么是二叉树二叉树#xff1a;定义与特点二叉树#xff1a;前序、中序、后序遍历二叉树#xff1a;深度、广度优先遍历二叉树#xff1a;线索化二叉树#xff1a;序列化与反序列化 haffman树平均编码长度构建haffman树haffman树… 树与二叉树 计算机中的树树的概念树的类型 什么是二叉树二叉树定义与特点二叉树前序、中序、后序遍历二叉树深度、广度优先遍历二叉树线索化二叉树序列化与反序列化 haffman树平均编码长度构建haffman树haffman树代码演示 计算机中的树 树的概念 计算机中的树与现实生活中的树结构是类似的但是计算机中的树型结构更加抽象化。在计算机中的树型结构具备以下几个特点 除了根节点每个结点都具有唯一父节点。每个结点可以有若干个子节点。树型结构具备层次关系。边与结点之间具备无循环的特性。
树的类型 二叉树Binary Tree 每个节点最多有两个子节点通常称为左子节点和右子节点。 多叉树 每个节点最多不止有两个子节点比如说字典树、和双数组字典树。
什么是二叉树
二叉树定义与特点
每个结点最多只有两个子节点。遍历和结构操作方便。满足递归的基本性质相关操作可以借助递归方式完成。二叉树在计算机领域应用广泛。
二叉树前序、中序、后序遍历
前序遍历 所谓前序遍历指的就是遍历顺序按照根、左、右 的方式进行。 // typedef struct Node {// int val;// struct Node *left, *right; // } Node;void preOrder(Node *root) {if (root NULL) return ;printf(%d , root-val);preOrder(root-left);preOrder(root-right);return ;}中序遍历 中序遍历的遍历顺序按照左、根、右 的方式进行。 // typedef struct Node {
// int val;
// struct Node *left, *right;
// } Node;void inOrder(Node *root) {if (root NULL) return ;inOrder(root-left);printf(%d , root-val);inOrder(root-right);return ;
}后序遍历 后序遍历的遍历顺序是按照左、右、根的方式 // typedef struct Node {
// int val;
// struct Node *left, *right;
// } Node;void lastOrder(Node *root) {if (root NULL) return ;lastOrder(root-left);lastOrder(root-right);printf(%d , root-val);return ;
} 二叉树深度、广度优先遍历
深度优先遍历(DFS) 深度优先遍历其遍历方式就是沿着其中一条路径一直走到底当无路可走时就需要按照原来的路径回退一步继续搜索其他结点重复原来的操作。不撞南墙不回头 // typedef struct Node {
// int key;
// struct Node *lchild, *rchild;
//} Node;int tot 0;void dfs(Node *root) {if (root NULL) return ;int l, r;l tot;tot 1;dfs(root-lchild);dfs(root-rchild);r tot; printf(%d : l[%d] | r[%d]\n, root-key, l, r);return ;
}广度优先遍历(BFS) 广度优先遍历也可称之为层序遍历因为将树型结构看成是一个金子塔那么BFS就是从顶向底层遍历。 // typedef struct Node {
// int key;
// struct Node *lchild, *rchild;
//} Node;#define MAX_QUEUE 15void bfs(Node *root) {if (root NULL) return ;Node *array[MAX_QUEUE] {0};#undef MAX_QUEUEint head 0, tail 0;array[tail] root;while (tail ! head) {Node *tmp array[head];if (tmp-lchild) array[tail] tmp-lchild;if (tmp-rchild) array[tail] tmp-rchild;printf(%d , tmp-key);}printf(\n);return ;
}二叉树线索化 二叉树的线索化其实就是将左右子节点为空的结点重复利用起来为特定的遍历方式建立线索化这样在完成某一个遍历顺序时可以达到线性复杂度的效率。摆脱递归式遍历的资源浪费问题。 中序遍历线索化 中序遍历的线索化可以将当前结点中子节点为空的结点指向中序遍历的前驱或者后继结点即当左孩子为空时则指向中序遍历中当前结点的前驱结点当右孩子为空时则指向中序遍历中当前结点的后继结点。 中序遍历线索化建立 //typedef struct Node {// int key;// int ltag, rtag;// struct Node *lchild, *rchild;// } Node;Node *pre_node NULL, *in_node NULL;
void __build_thread(Node *root) {if (root NULL) return ;if (root-ltag 0) __build_thread(root-lchild);if (in_node NULL) in_node root;if (pre_node root-lchild NULL) {root-lchild pre_node;root-ltag 1;}if (pre_node pre_node-rchild NULL) {pre_node-rchild root;pre_node-rtag 1;}pre_node root;if (root-rtag 0) __build_thread(root-rchild);return ;
}void build_thread(Node *root) {__build_thread(root);pre_node-rchild NULL;pre_node-rtag 1;return ;
}
中序线索化遍历 //typedef struct Node {// int key;// int ltag, rtag;// struct Node *lchild, *rchild;// } Node;Node *getNextNode(Node *root) { if (root-rtag 1) return root-rchild;root root-rchild;while (root-ltag 0 root-lchild) root root-lchild;return root;
}
二叉树序列化与反序列化
序列化(Serialize) 二叉树的序列化指的是将二叉树的表示方法转化为字符串形式即广义表表示方法。 //序列化
#define MAX_CHR 1000char buff[MAX_CHR 5];
int len 0;void serialize(Node *root) {if (root NULL) return ;len sprintf(buff len, %d, KEY(root));if (root-lchild NULL root-rchild NULL) return ;len sprintf(buff len, ();serialize(root-lchild);len sprintf(buff len, ,);serialize(root-rchild);len sprintf(buff len, ));return ;
}反序列化(Deserialize) 二叉树的反序列化就是将字符串广义表形式表示的二叉树又转换为树节点的形式。由于二叉树满足递归的性质因此可以借助栈完成反序列化 //反序列化Node *deserialize(char *str) {Node *root NULL, *preNode NULL;Node **array (Node **)malloc(sizeof(Node *) * MAX_CHR);int top -1, scode 0, flag 0;for (int i 0; str[i]; i) {switch (scode) {case 0: {//读取关键词if (str[i] 9 str[i] 0) {scode 1;//读取数字} else if (str[i] () {scode 2;//入栈新元素} else if (str[i] ,) {scode 3;//修改flag} else if (str[i] )) {scode 4;//完成栈顶元素的弹出}i - 1;} break;case 1: {//读取数字int num 0;while (str[i] 9 str[i] 0) {num num * 10 (str[i] - 0);i;}preNode getNewNode(num);if (root NULL) {root preNode;} if (top ! -1 flag 0) {array[top]-lchild preNode;}if (top ! -1 flag 1) {array[top]-rchild preNode;}scode 0;i - 1;} break;case 2: {//入栈新元素 (array[top] preNode;flag 0;scode 0;} break;case 3: {//遇到逗号 ,flag 1;scode 0;} break;case 4: {//出栈 )--top;flag 0;scode 0;} break;}}return root;
}haffman树
平均编码长度 定长编码指的是无论是何种字符每个字符的编码都是固定长度。变长编码即每种字符的编码长度都不是固定的 问题1这两种编码方式哪种更加适合用于网络传输问题2如何衡量两种编码方式的优劣 我们知道最重要的衡量标准就是单位时间内网络传输数据量的大小之分。假设两种编码方式都是在相同网络传输环境下哪种编码方式传输效率更高呢不言而喻就是平均编码长度最小的编码方式。 a v g ( L ) ∑ L i × P i avg(L) \sum{L_i \times P_i} avg(L)∑Li×Pi avg(L)表示平均编码长度 每一种字符的编码长度与对应字符出现概率的乘积累加和 构建haffman树 首先统计得到每一种字符的概率每次将最低频率的两个结点合并成一颗子树经过了n - 1轮合并就得到了一颗哈夫曼树按照左0右1的形式将编码读取出来 haffman树代码演示
完整代码
/************************************************************************* File Name: 04.haffmantree.cpp Author: Mail: Created Time: Wed 17 Jul 2024 10:23:16 AM CST************************************************************************/#includestdio.h
#includestdlib.h
#includestring.h#define MAX_CHR 128typedef struct Node {char ch;int freq;struct Node *lchild, *rchild;
} Node;Node *getNewNode(char ch, int freq) {Node *p (Node *)malloc(sizeof(Node));p-ch ch;p-freq freq;p-lchild p-rchild NULL;return p;
}int findMinNode(Node **arr, int n) {int ind 0;for (int i 1; i n; i) {if (arr[ind]-freq arr[i]-freq ) ind i;}return ind;
} void swap_node(Node **arr, int i, int j) {Node *tmp arr[i];arr[i] arr[j];arr[j] tmp;return ;
}Node *buildHaffManTree(Node **arr, int n) {for (int i 1; i n; i) {//find two nodeint ind1 findMinNode(arr, n - i);swap_node(arr, ind1, n - i);int ind2 findMinNode(arr, n - i - 1);swap_node(arr, ind2, n - i - 1);//build new nodeint freq_tmp arr[n - i]-freq arr[n - i - 1]-freq;Node *new_node getNewNode(0, freq_tmp);new_node-lchild arr[n - i - 1];new_node-rchild arr[n - i];arr[n - i - 1] new_node;}return arr[0];
}char *ch_code[MAX_CHR 5] {0};
int k 0;void extractHaffManTree(Node *root, char buff[], int k) {buff[k] 0;if (root-lchild NULL root-rchild NULL) {ch_code[root-ch] strdup(buff);return ;}buff[k] 0;extractHaffManTree(root-lchild, buff, k 1);buff[k] 1;extractHaffManTree(root-rchild, buff, k 1);return ;
}void clear(Node *root) {if (root NULL) return ;clear(root-lchild);clear(root-rchild);free(root);return ;
}int main() {int n;char s[10] {0};scanf(%d, n);Node **array (Node **)malloc(sizeof(Node *) * n);for (int i 0; i n; i) {int freq;scanf(%s%d, s, freq);array[i] getNewNode(s[0], freq);}Node *root buildHaffManTree(array, n);char buff[1000] {0};extractHaffManTree(root, buff, 0);for (int i 0; i MAX_CHR; i) {if (ch_code[i] NULL) continue;printf(%c : %s\n, i, ch_code[i]);}clear(root);#undef MAX_CHRreturn 0;
}运行效果展示
