企业官网建设流程全解析

建设风景网站策划书,平凉公司网站建设,成都公司注册价格,网站建设与管理专业题目一、线索二叉树 线索二叉树是对普通二叉树的优化结构#xff0c;旨在提高遍历效率。在传统二叉树中#xff0c;每个结点有左右两个指针#xff0c;对于n个结点的二叉树#xff0c;共有2n个指针域#xff0c;其中只有n-1个被用于连接子结点#xff0c;其余n1个为空。线索二…一、线索二叉树线索二叉树是对普通二叉树的优化结构旨在提高遍历效率。在传统二叉树中每个结点有左右两个指针对于n个结点的二叉树共有2n个指针域其中只有n-1个被用于连接子结点其余n1个为空。线索二叉树利用这些空指针域来存储前驱和后继信息从而加快遍历速度。每个结点增设两个标志位ltag0 表示 lchild 指向左孩子1 表示 lchild 指向前驱结点rtag0 表示 rchild 指向右孩子1 表示 rchild 指向后继结点。通过中序遍历过程中的指针p和pre记录上一个访问的结点可以在线索化过程中建立线索链表。若pre-rchild为空则将其指向p并设置pre-rtag 1同理处理p-lchild。查找中序后继的操作如下若p-rtag 1则p-rchild直接指向其后继若p-rtag 0则后继为右子树中最左侧的结点即右子树中序遍历时的第一个结点需沿左链下行至ltag 1的结点。类似地可定义先序线索树和后序线索树但中序线索树最常用因其线索结构更清晰、易于实现非递归遍历。二、最优二叉树哈夫曼树最优二叉树又称哈夫曼树Huffman Tree是一类带权路径长度WPL, Weighted Path Length最小的二叉树。它广泛应用于数据压缩领域如哈夫曼编码。基本概念路径长度从根到某结点的边数。带权路径长度WPL所有叶结点的权值 × 路径长度之和。哈夫曼树的目标是使 WPL 最小。构造方法哈夫曼算法将每个权值作为一个独立的树单结点构成森林选出两棵根结点权值最小的树合并成一棵新树新根权值为两者之和重复步骤2直到只剩一棵树为止。特点没有度为1的结点每次合并两个结点权值越大的叶结点离根越近左右子树顺序不影响 WPL但影响编码唯一性通常约定左0右1。应用哈夫曼编码是一种变长前缀码能有效压缩数据避免歧义解码。# 示例哈夫曼树结点定义classTreeNode:def__init__(self,weight,valNone):self.weightweight self.valval# 叶结点存储字符self.leftNoneself.rightNoneself.ltag0self.rtag0实现中序线索二叉树的非递归中序遍历关键在于利用线索信息直接找到后继结点避免使用栈或递归。由于线索已将中序前驱和后继显式链接遍历过程只需从最左下结点开始依次沿线索访问即可。实现步骤找到中序遍历的第一个结点从根出发一直向左走若ltag 0则进入左子树否则当前结点即为最左结点从该结点开始循环执行以下操作直到返回根并结束访问当前结点若rtag 1则rchild直接指向后继跳转到该后继若rtag 0则后继是右子树中最左下的结点需进入右子树并持续向左走lchild且ltag 0直到ltag 1的结点。数据结构定义含线索标志classThreadNode:def__init__(self,val):self.valval self.leftNoneself.rightNoneself.ltag0# 0表示left指向左孩子1表示指向前驱self.rtag0# 0表示right指向右孩子1表示指向后继非递归中序遍历函数definorder_traverse_threaded(root):ifnotroot:return# 找到最左下结点中序第一个结点currentrootwhilecurrentandcurrent.ltag0:# ltag0才有左孩子currentcurrent.left# 从中序第一个结点开始遍历whilecurrent:print(current.val,end )# 访问当前结点# 情况1rtag1右指针是线索直接指向后继ifcurrent.rtag1:currentcurrent.rightelse:# 情况2rtag0后继是右子树中最左结点currentcurrent.rightifcurrentandcurrent.ltag0:# 存在左子树whilecurrentandcurrent.ltag0:currentcurrent.left# 若current为None则结束ifnotcurrent:break示例说明假设有一棵中序线索化的二叉树中序序列为D → B → E → A → F → C → G调用inorder_traverse_threaded(root)将按此顺序输出无需栈时间复杂度 O(n)空间复杂度 O(1)。注意前提是树已经完成中序线索化在建树时通过中序遍历设置ltag和rtag。