当前位置: 首页 > news >正文

网站建设销售该学的qq群推广

网站建设销售该学的,qq群推广,怎么样注册一个网站,中国网络营销平台目录 注: 树的存储结构 1. 双亲表示法 2. 孩子表示法 3. 重要:孩子兄弟法(二叉树表示法) 森林与二叉树的转换 树和森林的遍历 1. 树的遍历 2. 森林的遍历 哈夫曼树及其应用 基本概念 哈夫曼树的构造算法 1. 构造过程 …

目录

注:

树的存储结构

1. 双亲表示法

2. 孩子表示法

3. 重要:孩子兄弟法(二叉树表示法)

森林与二叉树的转换

树和森林的遍历

1. 树的遍历

2. 森林的遍历

哈夫曼树及其应用

基本概念

哈夫曼树的构造算法

 1. 构造过程

2. 算法实现

哈夫曼编码

算法实现

文件的编码和译码

二叉树的运用 - 利用二叉树求解表达式

中缀表达式树的创建

中缀表达式树的求值


 

注:

        本笔记参考:《数据结构(C语言版)》


        接下来是树的表示、遍历操作及树林与二叉树之间的对应关系。

树的存储结构

1. 双亲表示法

        用一组连续的存储单元存储树的结点,每个结点包括两个域:

例如:

  • 优点:求结点的双亲树的根会十分方便;
  • 缺点:求结点的孩子时需要遍历整个结构。

------

2. 孩子表示法

        由于每个结点可以有多棵子树,所以每个结点可以有多个指针域,每个指针域分别指向其中一棵子树的根结点:

    除此之外,还有一种存储结构:在这种存储结构中,由孩子结点组成了一个个线性表,并且把这些链表的头结点再组成一个线性表。

【例如】

        而如果把双亲表示法和孩子表示法结合起来,就会得到又一种存储结构:

------

3. 重要:孩子兄弟法(二叉树表示法)

        即将二叉链表作为树的存储结构,这种链表有两个链域:

typedef struct CSNode {ElemType data;CSNode* firstchild, * nextsibling;
}CSNode, *CSTree;

        这种存储结构便于各种关于树的操作,譬如访问孩子节点:只需交替寻找 firstchild域nextsibling域 即可。

     而如果要方便寻找双亲结点,仅需在结构上多设置一个 parent域 即可。

        如上图所示,这种存储结构与二叉链表完全一致,可以通过这种结构,将一般的树转换成二叉树进行处理。因此,孩子兄弟表示法的运用较为普遍

森林与二叉树的转换

        由上述的孩子兄弟表示法可知,任何一棵和树对应的二叉树,其根结点的右子树必空。例如:

        通过上述的例子,就可以揭示森林与二叉树之间的转换规律。

        现在假设:

    因为空树就是空二叉树,所以这种情况不做说明。

1. 森林转换为二叉树

2. 二叉树转换为森林

    上述所描述的转换方式都可以通过递归实现。

树和森林的遍历

1. 树的遍历

        与二叉树不同,树的遍历只有两种方式:

  1. 先根(次序)遍历:优先访问树的根结点,然后依此访问子树;
  2. 后根(次序)遍历:先后根遍历子树,再访问对应根结点。

【例如】


2. 森林的遍历

||| 森林和树之间是可以进行相互递归的。

    遍历的一个前提:森林非空。

(1)先序遍历规则:

  1. 访问森林中第一棵树的根结点;
  2. 先序访问第一棵树的根结点的子树森林;
  3. 先序遍历由剩余的树构成的森林。

(2)中序遍历规则:

  1. 中序遍历森林中第一棵树的根结点的子树森林;
  2. 访问第一棵树的根结点;
  3. 中序遍历由剩余的树构成的森林。

【例如】

    注:此处森林的先序和中序遍历,分别与对应二叉树的先序和中序遍历相对。

哈夫曼树及其应用

基本概念

||| 哈夫曼树(即最优二叉树):是一类带权路径长度最短的二叉树。

        以下是一些会用到的概念:

概念定义
路径从树中的一个结点到另一个结点之间的 分支 构成两结点之间的路径
路径长度即路径上的分支数目
树的路径长度从树根到每一结点的路径长度之和

赋予某个实体的一个量

(是对实体的某个或某些属性的数值化描述)

结点的带权路径长度= 该结点到树根之间的路径长度 × 结点上的权

树的带权路径长度(WSL)

WSL=\sum_{k=1}^{n}w_{k}l_{k}

= 树中 所有叶子结点 的带权路径长度之和

【例如】

        有4个叶子结点a、b、c、d,分别带权7、5、2、4,这4个叶子结点存在于不同的二叉树上:

        可以验证,下面的这棵树的带权路径长度恰好是最小的(或者说,在所有带权为7、5、2、4的4个叶子结点的二叉树中其值最小),它就是哈夫曼树。

    由上述例子可以看出:哈夫曼树权值越大的结点离根结点越近

哈夫曼树的构造算法

 1. 构造过程


2. 算法实现

    由上述构造可知,哈夫曼树中不存在度为1的结点。故若哈夫曼树存在n个叶子结点,则其总结点数一定是2n - 1。

        哈夫曼树的结点存储结构:

        若将上述的存储结构转换为代码,就是:

typedef struct
{int weight;					//结点的权值int parent, lchild, rchild;	//结点的双亲、左孩子和右孩子的下标
}HTNode, *HuffmanTree;

        注意:和以往的链式存储不同,此次是通过动态分配的方式对哈夫曼树进行存储。

        在具体的实现中,为了方便,往往会将下标为0的单元置空,所以开辟的数组大小将会是2n。对存储内容进行分类:

  • 前1~n个单元:存储叶子结点;
  • 后n - 1个单元:存储非叶子结点。

【参考代码:构造哈夫曼树】

void CreateHuffmanTree(HuffmanTree& HT, int n)
{//---初始化开始---if (n <= 1)return;int m = 2 * n - 1;HT = new HTNode[m + 1];				//规定:HT[m]表示根结点for (int i = 1; i <= m; i++){									//处理 1 至 m 个单元(初始化)HT[i].parent = 0;HT[i].lchild = 0;HT[i].rchild = 0;}for (int i = 1; i <= n; i++){									//输入叶子结点的权值(即前n个结点)cin >> HT[i].weight;}//---初始化完毕,开始创建哈夫曼树---for (int i = n + 1; i <= m; i++){									//进行n-1次的构造操作int s1 = 0;int s2 = 0;SelectLeaves(HT, i - 1, s1, s2);//挑选目标结点HT[s1].parent = i;				//更改双亲域(相当于删除s1和s2,得到了新结点i)HT[s2].parent = i;HT[i].lchild = s1;				//将s1和s2作为i的孩子HT[i].rchild = s2;HT[i].weight = HT[s1].weight + HT[s2].weight;}
}

其中,函数SelectLeaves的参考如下(仅供参考):

//挑选要求:
//1. 双亲域为0;
//2. 权值最小。
void SelectLeaves(HuffmanTree HT, int i, int& s1, int& s2)
{int left = 1;int right = i;while (left < right){if (HT[left].parent == 0 && HT[right].parent == 0){if (HT[left].weight <= HT[right].weight)right--;elseleft++;}else if (HT[left].parent != 0)left++;elseright--;}s1 = left;HT[s1].parent = 1;left = 1;right = i;while (left < right){if (HT[left].parent == 0 && HT[right].parent == 0){if (HT[left].weight <= HT[right].weight)right--;elseleft++;}else if (HT[left].parent != 0)left++;elseright--;}s2 = left;
}

哈夫曼编码

        为了对数据文件进行尽可能的压缩,有人提出了不定长编码的概念:为出现次数较多的字符编以较短的代码。而通过哈夫曼树设计的二进制编码,就可以满足这一需求。

在上图中,约定:

  • 左分支标记为0;
  • 右分支标记为1。

        由此,根结点到每个叶子结点的路径上的0、1序列就构成了相应字符的编码。这种由各分支的赋值构成的二进制串,就是哈夫曼编码

    前缀编码的概念(提及):若在一个编码方案中,任一编码都不是其他任何编码的前缀(最左子串),则称该编码为前缀编码。譬如:

前缀编码: 0, 10, 110, 111

非前缀编码:0, 01, 010, 111

哈夫曼编码的两个性质

  1. 哈夫曼编码是前缀编码(因为路径的不同)
  2. 哈夫曼编码是最优前缀编码:对于包含n个字符的数据文件,分别以字符的出现次数为权值构造哈夫曼树,再用该树对应的哈夫曼编码压缩文件,可使文件压缩后对应的二进制文件长度最短

算法实现

主要思想:

  • 从叶子出发,向上回溯至根结点。
  • 回溯时,走左分支则生成代码0。
  • 回溯时,走右分支则生成代码1。

        使用一个指针数组作为哈夫曼编码表,存放每个字符编码串的首地址(依旧是从1号单元开始使用):

typedef char** HuffmanCode;		//通过动态分配数组存储哈夫曼表

    在动态开辟数组时,会发现:由于当前并不清楚每个字符编码的长度,所以不能为每个字符分配合适的存储空间。为了解决这个麻烦,通常会动态分配一个长度为n的一维数组作为临时的存储。

        注意:由于求解编码的过程是向上回溯的,所以对于每个字符,得到的编码顺序是从右往左的。因此,在将编码往临时的一维数组cd内存储时,顺序也是从后向前的(即字符的第一个编码应该存储到 cd[n - 2] 中,以此类推)。

【参考代码】

void CreateHuffmanCode(HuffmanTree HT, HuffmanCode& HC, int n)
{//将从叶子到根结点回溯求得的每个字符的哈夫曼编码,存储到编码表HC中HC = new char* [n + 1];				//分配存储n个字符编码的编码表空间char* cd = new char[n];				//分配临时存放每个字符编码的动态存储空间cd[n - 1] = '\0';					//编码结束符for (int i = 1; i <= n; i++)		//逐字符求编码{int start = n - 1;				//从后往前写入int c = i;						//从每个叶子结点开始int f = HT[i].parent;while (f != 0)					//直到回到根结点为止{--start;if (HT[f].lchild == c)		//左、右分支对应不同的代码cd[start] = '0';elsecd[start] = '1';c = f;						//继续回溯f = HT[f].parent;}HC[i] = new char[n - start];	//分配空间strcpy(HC[i], &cd[start]);		//将求得的编码复制到HC中}delete[] cd;
}

【例子】

        设在一系统通信内只可能出现8种字符,出现概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11。

        为设计哈夫曼编码,将概率作为对应字符的权值,得到:w = (5, 29, 7, 8, 14, 23, 3, 11)。其对应的哈夫曼表为:


文件的编码和译码

        在完成字符集的哈夫曼编码表后,就可以进行编码和译码的操作。

对数据文件进行编码的过程是:

  1. 依此读入文件中的字符;
  2. 在哈夫曼编码表HC中找到此字符;
  3. 将对应字符转换为编码表中存放的编码串。

对编码后的文件进行译码的过程是:

  1. 依此读入文件中的二进制码;
  2. 从哈夫曼树的根结点(即HT[m])出发,读入0,则进左孩子;读入1,则进右孩子。一旦到达某一叶子HT[i],则译出相应的字符编码HC[i];
  3. 循环上述步骤,直到文件结束。

二叉树的运用 - 利用二叉树求解表达式

        对于任一算术表达式,都可以使用二叉树进行表示。而当对应二叉树创建完毕时,就可以利用对于二叉树的操作,进行表达式的求值运算。

中缀表达式树的创建

        假设:运算符均为双目运算符。

        由于创建的表达式树需要准确表达运算的次序,所以需要考虑各个运算符之间的优先级。为此,可以借助一个运算符栈,来存储未处理的运算符。

        由两个操作数与一个运算符即可建立一棵表达式二叉树,而该二叉树又可以是另一棵树的子树。可以结组一个表达式树栈,以此来暂存已建立好的树。

【参考代码】

    假设每个表达式的开头和结尾均为“#”。

两个工作栈:

  • OPTR,用来暂存运算符。
  • EXPT,用来暂存已建立好的表达式树的根结点。

【参考代码】

BiTree InitExpTree()
{SqStack EXPT;LinkStack OPTR;InitStack(EXPT);	//初始化栈InitLinkStack(OPTR);LinkPush(OPTR, '#');		//将表达式起始符‘#’压入栈顶char ch = 0;cin >> ch;while (ch != '#' || LinkGetTop(OPTR) != '#')	//表达式未扫描完毕 || OPTR栈顶元素不是‘#’{if (!In(ch))	//ch不是运算符{BiTree T = new BiTNode;CreateExpTree(T, NULL, NULL, ch);	//以ch为根创建一棵只有根结点的二叉树Push(EXPT, T);					//将二叉树根结点T压入EXPT栈内cin >> ch;}else{switch (Precede(LinkGetTop(OPTR), ch))	//比较二者的优先级{case '<':{LinkPush(OPTR, ch);					//当前字符入栈cin >> ch;break;}case '>':{char theta = 0;BiTree T = new BiTNode;BiTree a = new BiTNode;BiTree b = new BiTNode;LinkPop(OPTR, theta);				//弹出OPTR栈顶的运算符Pop(EXPT, b);				//弹出EXPT栈顶的两个运算数Pop(EXPT, a);CreateExpTree(T, a, b, theta);	//创建新的子树Push(EXPT, T);break;}case '=':							//仅当:OPTR栈顶元素是'(',字符ch是')'{char x = 0;LinkPop(OPTR, x);cin >> ch;break;}}}}BiTree T = new BiTNode;Pop(EXPT, T);return T;
}

    由于字符的限制,上述算法只能进行10以内的运算。

【算法分析】

  • 时间复杂度:遍历表达式中的每个字符,故时间复杂度为O(n)
  • 空间复杂度:算法运行时所占用的辅助空间主要有OPTR栈和EXPT栈,它们的大小之和不会超过n,故空间复杂度为O(n)

中缀表达式树的求值

【参考代码】

int EvaluateExpTree(BiTree T)
{int lvalue = 0, rvalue = 0;			///初始值均为0if (T->rchild == NULL && T->lchild == NULL)return T->data - '0';			//若当前结点为操作数,则返回该结点的对应数值else								//若结点为操作符{lvalue = EvaluateExpTree(T->lchild);rvalue = EvaluateExpTree(T->rchild);return GetValue(T->data, lvalue, rvalue);	//对取得的两个操作数进行计算}
}

    其中,函数GetValue就是对加、减、乘、除四种运算进行处理的函数。

        该算法的时间复杂度和空间复杂度均为O(n)

http://www.khdw.cn/news/55563.html

相关文章:

  • 北京做网站公司 seoseo关键词排名查询
  • 做网站要求电脑配置怎样策划一个营销型网站
  • 检察院门户网站建设情况微信营销方法
  • 做网站需要技术免费seo网站优化
  • 怎么做二级网站域名网红推广团队去哪里找
  • 哪里有做网站的单位最近实时热点事件
  • 合肥大型网站制上海品牌推广公司
  • 卖房子上哪个网站最好卖b站黄页推广软件
  • 公司被其它人拿来做网站今日新闻联播主要内容
  • 衡阳网站优化方案seo优化快排
  • 中远智达网站建设今日头条最新版
  • 用织梦做网站费用百度浏览官网
  • 网站备案变更 委托书百度推广优化中心
  • 浮山网站建设百度指数三个功能模块
  • 怎么自己建设网站有效的网站推广方式
  • 宁夏网站建设公司网站推广要点
  • wordpress文件上传函数seo快速排名多少钱
  • 有个网站做中日韩测试英文外链seo兼职
  • 关于网站开发的创业计划书谷歌外链代发
  • 做个人网页优化大师使用心得
  • 商城网站建设 优帮云网店营销与推广策划方案
  • 政务公开做的好的网站有哪些女生读网络营销与电商直播
  • 旅游公司网页设计西安seo服务外包
  • 应用商店怎么下载seo网页优化服务
  • wordpress 文章阅读数游戏优化
  • 广告设计网站免费数字营销成功案例
  • 初学者怎么做php网站什么叫seo
  • 注册网站域名需要什么网站有吗免费的
  • 如何用魔方网表做门户网站必应搜索引擎网站
  • 怎样联系网站管理员百度投诉中心在线申诉