代写文章兼职,济南公交优化,wordpress 4.9 安装,网站推广公司经理职责第六章 树和二叉树
6.1 树的定义和基本术语
树 Tree 是n个结点的有限集。
任意一棵非空树中#xff1a;
#xff08;1#xff09;有且仅有一个特定的称为根#xff08;root#xff09;的结点#xff1b;
#xff08;2#xff09;当n1时#xff0c;其余结点可…第六章 树和二叉树
6.1 树的定义和基本术语
树 Tree 是n个结点的有限集。
任意一棵非空树中
1有且仅有一个特定的称为根root的结点
2当n1时其余结点可分为m(m0)个互不相交的有限集T1T2...Tm其中每一个集合本身又是一棵树并且称为根的子树SubTree。 结点包含一个数据元素及若干指向其子树的分支。
结点的度degree结点拥有的子树数。
叶子Leaf/终端结点度为0的结点。
分支结点/非终端结点度不为0的结点。 除根结点外分支结点也称为内部结点。
孩子Child结点的子树的根称为该结点的孩子。
双亲Parent该结点称为孩子的双亲。
兄弟Sibling同一个双亲的孩子之间互称兄弟。
祖先从根到该结点所经的所有结点。
子孙以某结点为根的子树中的任一结点。
层次Level:根为第一层根的孩子为第二层。
若某结点在第l层则其子树的根在第l1层。
其双亲在同一层的结点互为堂兄弟。
深度Depth/高度树中结点的最大层次。 有序树树中结点的各子树从左至右是有次序的。
无序树树中结点的各子树从左至右是无次序的。
森林Forestm棵互不相交的树的集合。
对树中每个结点而言其子树的集合即为森林。 6.2 二叉树
二叉树 Binary Tree
每个结点至多只有两棵子树并且二叉树的子树有左右之分其次序不能任意颠倒。 二叉树的5种基本形态
空二叉树
仅有根节点
右子树为空
左子树为空
左右子树均非空 二叉树的性质
1、在二叉树第i层上至多有2^(i-1)个结点。
2、深度为k的二叉树至多有2^k-1个结点。
3、对任何一棵二叉树T如果其终端结点数为n0度为2的结点数为n2则n0n21。
结点nn0n1n2
入度nn12n21 满二叉树一棵深度为k且有2^k-1个结点的二叉树称为满二叉树。
特点每一层上的结点数都是最大结点数。
可以对满二叉树的结点进行连续编号约定编号从根结点起自上而下自左至右。 由此可引出完全二叉树的定义
深度为k的有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中的编号从1至n的结点一一对应时称之为完全二叉树。
特点
1叶子结点只可能在层次最大的两层上出现
2对任一结点若其右分支下的子孙的最大层次为l则其左分支下的子孙的最大层次必为l或l1。 完全二叉树的两个重要性质
1、具有n个结点的完全二叉树的深度为
2、对于完全二叉树的编号
1如果i1则结点i是二叉树的根无双亲如果i1则其双亲结点是i/2
2如果2in则i结点无左孩子否则其左孩子为2i
3如果2i1n则i结点无右孩子否则其右孩子为2i1。 二叉树的存储结构
1顺序存储结构完全二叉树。
2链式存储结构
二叉链表左孩子、右孩子
三叉链表左孩子、右孩子、父结点 二叉链表存储结构的许多基本操作都采用了递归函数因为二叉树的层数是不定的正确采用递归函数可简化编程。 递归函数特点1、降阶2、出口。 在含有n个结点的二叉链表中有n1个空链域。
可以利用这些空链域存储其他有用信息从而得到另一种链式存储结构——线索链表。 6.3 遍历二叉树和线索二叉树
6.3.1 遍历二叉树
将非线性的二叉树结构线性化。
Traversing binary tree
二叉树是由三个基本单元组成根节点、左子树、右子树。
限定先左后右有三种遍历方式先序遍历、中序遍历、后续遍历。
对二叉树做中序遍历和先序遍历或者中序遍历和后续遍历就可以确定二叉树的形状。 先序遍历二叉树
若二叉树为空则空操作否则
1、访问根节点
2、先序遍历左子树
3、先序遍历右子树。 中序遍历二叉树
若二叉树为空则空操作否则
1、中序遍历左子树
2、访问根节点
3、中序遍历右子树。 后序遍历二叉树
若二叉树为空则空操作否则
1、后序遍历左子树
2、后序遍历右子树
3、访问根节点。 非递归中序遍历二叉树 二叉树表达式
前缀表达式-波兰式
中缀表达式
后缀表达式-逆波兰式 还可以从上到下从左到右按层次进行遍历。即层序遍历。
时间复杂度O(n)
空间复杂度O(n) 链式结构先序构造二叉树时要把度数为1的结点和叶子结点的无用指针置空。 6.3.2 线索二叉树
遍历二叉树是以一定规则将二叉树中结点排列成一个线性序列得到二叉树中结点的先序序列或中序序列或后序序列。即对一个非线性结构进行线性化操作。
在有n个结点的二叉链表中必定存在n1个空链域。
利用这些空链域来存储结点的前驱和后继信息。
规定如下
若结点有左子树则lchild指向其左孩子否则指向其前驱
若结点有右子树则rchild指向其右孩子否则指向其后继。 增加两个标志域LTag RTag 0(Link)指向左右孩子1(Tread)指向前驱后继。
指向前驱和后继的指针叫做线索。
线索二叉树Threaded Binary Tree 对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。
在线索树上进行遍历只要先找到序列中的第一个结点然后依次找结点后继直至其后继为空时为止。 中序线索树
后继
若其右标志为1右链直接指示后继
非终端的后继遍历右子树时第一个访问的结点为后继即右子树中最左下的结点。
前驱
若其左标志为1左链直接指示前驱
非终端的前驱遍历左子树时最后一个访问的结点为前驱即左子树中最右下的结点。 后序线索树
后继
若为根节点后继为空
若结点为双亲右孩子或为左孩子且双亲无右孩子则其后继为双亲
若结点为左孩子且双亲有右孩子则后继为双亲右子树上按后序遍历列出的第一个结点。
在后序线索化树上找后继时需知道结点双亲即需带标志域的三叉链表作为存储结构。 中序线索二叉树的遍历虽然时间复杂度为O(n)但常数因子要小于普通二叉树。
若某程序对二叉树需经常遍历或查找结点的前驱或后继应采用线索链表作存储结构。 可以在二叉树的线索表上添加一个头结点令其lchild指向二叉树根结点rchild指向中序遍历时访问的最后一个结点令二叉树中序序列中的第一个结点的lchild域指针和组后一个结点rchild域指针指向头结点。 线索化的实质是将二叉树链表中的空指针改为指向前驱或后继的线索。
线索化的过程即为在遍历的过程中修改空指针的过程。
附设一个指针pre始终指向前一个访问的结点指针p指向当前访问结点。
指针pre指向的是p的前驱指针p指向的是pre的后继。 6.4 树和森林
6.4.1 树的存储结构
1、双亲表示法
以一组连续空间存储树的结点同时在每个结点中附设一个指示器指示其双亲结点的位置。
这种表示法利用了每个结点根结点除外只有唯一双亲的性质。
求孩子结点时需要遍历整个结构。 2、孩子表示法
把每个结点的孩子结点排列起来看成是一个线性表以单链表作为存储结构则n个结点有n个孩子链表叶子的孩子链表为空表。
而n个头指针又组成一个线性表为了便于查找可采用顺序存储结构。
孩子表示法便于那些涉及孩子的操作。 可以把双亲表示法和孩子表示法结合起来即将双亲表示和孩子链表合在一起。 3、 孩子兄弟表示法
二叉链表作为树的存储结构。
结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。
分别命名为firstchild域和nextsibling域。
任何一棵和树对应的二叉树其右子树必空。 6.4.2 森林与二叉树的转换
把森林中第二棵树的根结点看成是第一棵树的根结点兄弟可以导出森林和二叉树的对应关系。 6.4.3 树和森林的遍历
两种方式
先根遍历对应二叉树的先序遍历
后根遍历对应二叉树的后序遍历。 6.6 哈夫曼树及其应用
6.6.1 最优二叉树哈夫曼树
路径从一个结点到另一个结点之间的分支构成两个结点间的路径。
路径长路径上的分支数目。
树的路径长度从树根到每一个叶子结点的路径长度之和。
带权路径长度路径长度与结点权值的乘积。
树的带权路径长度所有叶子结点的带权路径长度之和。
假设有n个权值对应n个叶子结点带权路径长度WPL最小的二叉树称为最优二叉树或哈夫曼树。 最优二叉树特点
权值越小的结点其到根结点的路径越长。
最优二叉树的左右子树是可以互换的不影响树的带权路径长度。 哈夫曼算法
1根据给定的n个权值{W1, W2, ..., Wn}构成n棵二叉树的集合F{T1, T2, ..., Tn}其中每棵二叉树Ti中只用一个带权为Wi的根结点其左右子树均空
2在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树且新的二叉树的根结点的权值为左右子树根结点权值之和
3在F中删除这两棵树并将新的树加入F中
4重复23直至只含一棵树为止。 6.6.2 哈夫曼编码
若想设计长短不等的编码必须是任一个字符的编码都不是另一个字符的编码的前缀这种编码称作前缀编码。 可以利用二叉树来设计二进制的前缀编码。
约定左分支为0右分支为1。
从根结点到叶子结点的路径上的分支01串即为该叶子结点的前缀编码。 设计电文总长最短的二进制前缀编码即为
以n种字符出现的频率作权设计一棵哈夫曼树由此得到的二进制前缀码便称为哈夫曼编码。
哈夫曼树中没有度为1的结点。这类树又称为严格/正则二叉树
则一棵有n个叶子结点的哈夫曼树共有2n-1个结点可以存储在一个大小为2n-1的一维数组中。 6.7 回溯法与树的遍历
试探与回溯在约束条件下先序遍历一颗状态树。
在程序设计问题中有相当一类求一组解、或求全部解、或求最优解的问题这类问题不是根据某种确定的计算法则而是利用试探和回溯Backtracking的搜索技术求解。
回溯法是设计递归过程的一种重要方法它的求解过程实质上是一个先序遍历一棵“状态树”的过程这棵树不是遍历前预先建立的而是隐含在遍历过程中认识到这一点许多问题就迎刃而解了。 很多问题用回溯和试探求解时描述求解过程的状态树不是一棵满的多叉树。
当试探过程中出现的状态和问题所求解产生矛盾时不再继续试探下去这时出现的叶子结点不是问题的解的终结状态。
这类问题的求解过程可看成是在约束条件下进行先序遍历并在遍历过程中剪去那些不满足条件的分支。 八皇后问题
任何两个棋子不在同一行、同一列、同一斜线。
求所有合法布局的过程即为在上述约束条件下先根遍历状态树的过程。
