线索二叉树是对普通二叉树的优化结构，旨在提高遍历效率

一、线索二叉树
线索二叉树是对普通二叉树的优化结构，旨在提高遍历效率。在传统二叉树中，每个结点有左右两个指针，对于n个结点的二叉树，共有2n个指针域，其中只有n-1个被用于连接子结点，其余n+1个为空。线索二叉树利用这些空指针域来存储前驱和后继信息，从而加快遍历速度。

每个结点增设两个标志位：

• ltag：0 表示 lchild 指向左孩子，1 表示 lchild 指向前驱结点；
• rtag：0 表示 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 最小。

构造方法（哈夫曼算法）：

1. 将每个权值作为一个独立的树（单结点），构成森林；
2. 选出两棵根结点权值最小的树，合并成一棵新树，新根权值为两者之和；
3. 重复步骤2，直到只剩一棵树为止。

特点：

• 没有度为1的结点（每次合并两个结点）；
• 权值越大的叶结点离根越近；
• 左右子树顺序不影响 WPL，但影响编码唯一性，通常约定左0右1。

应用：

• 哈夫曼编码是一种变长前缀码，能有效压缩数据，避免歧义解码。

# 示例：哈夫曼树结点定义classTreeNode:def__init__(self,weight,val=None):self.weight=weight self.val=val# 叶结点存储字符self.left=Noneself.right=Noneself.ltag=0self.rtag=0

实现中序线索二叉树的非递归中序遍历，关键在于利用线索信息直接找到后继结点，避免使用栈或递归。由于线索已将中序前驱和后继显式链接，遍历过程只需从最左下结点开始，依次沿线索访问即可。

实现步骤：

1. 找到中序遍历的第一个结点：从根出发，一直向左走（若ltag == 0则进入左子树，否则当前结点即为最左结点）；
2. 从该结点开始，循环执行以下操作直到返回根并结束：
   • 访问当前结点；
   • 若rtag == 1，则rchild直接指向后继，跳转到该后继；
   • 若rtag == 0，则后继是右子树中最左下的结点，需进入右子树并持续向左走（lchild且ltag == 0）直到ltag == 1的结点。

数据结构定义（含线索标志）

classThreadNode:def__init__(self,val):self.val=val self.left=Noneself.right=Noneself.ltag=0# 0表示left指向左孩子，1表示指向前驱self.rtag=0# 0表示right指向右孩子，1表示指向后继

非递归中序遍历函数

definorder_traverse_threaded(root):ifnotroot:return# 找到最左下结点（中序第一个结点）current=rootwhilecurrentandcurrent.ltag==0:# ltag=0才有左孩子current=current.left# 从中序第一个结点开始遍历whilecurrent:print(current.val,end=' ')# 访问当前结点# 情况1：rtag=1，右指针是线索，直接指向后继ifcurrent.rtag==1:current=current.rightelse:# 情况2：rtag=0，后继是右子树中最左结点current=current.rightifcurrentandcurrent.ltag==0:# 存在左子树whilecurrentandcurrent.ltag==0:current=current.left# 若current为None则结束ifnotcurrent:break

示例说明

假设有一棵中序线索化的二叉树，中序序列为：D → B → E → A → F → C → G
调用inorder_traverse_threaded(root)将按此顺序输出，无需栈，时间复杂度 O(n)，空间复杂度 O(1)。

注意：前提是树已经完成中序线索化，在建树时通过中序遍历设置ltag和rtag。