中序线索二叉树

中序线索二叉树的构造

对于每个结点o而言，重新定义其左、右儿子指针lson,rson:

• 左儿子指针lson:

• • Case 1:若o存在左儿子，则lson仍指向其左儿子，o->ltag=0(此时o的中序前驱应为o的左子树中序遍历的最后一个结点，也就是o的左子树最右下那个结点)
• • Case 2:若o不存在左儿子，则lson指向其在中序遍历序列中的前驱，o->ltag=1

• 右儿子指针rson:

• • Case 1:若o存在右儿子，则rson仍指向其右儿子，o->rtag=0(此时o的中序后继应为o的右子树下的最左下方结点)
• • Case 2:若o不存在右儿子，则rson指向其在中序遍历序列中的后继，o->rtag=1

中序线索二叉树的遍历

中序遍历整个树

假设当前访问节点o及其子树：

Step 1: 子树o的中序遍历中，第一个遍历到的，显然是o最左下方的结点。因此首先不断沿左儿子指针走，走到子树o下的最左下方结点p处。

Step 2: 访问子树o中最左下方结点后，下一步，应访问其中序后继结点

• Case 1:若p无右儿子，则应向上走返回，而返回过程中，所有无右儿子的祖先结点，都已访问过左子树了
• • (i)此时应沿着p的后继线索不断访问后继结点，直至找到一个有右儿子的后继结点p\’。
• • (ii)中序遍历p\’的右子树，o<=p\’, Goto Step 1
• Case 2:若p有右儿子，则下一步应中序遍历p的右子树，o<=p->rson，Goto Step 1

查找中序线索二叉树结点o的前驱

• Case 1. o有左儿子，则o的前驱为其左子树下最右下的那个结点，从o的左儿子出发，不断沿右儿子指针(rtag=0)走，即可找到o的前驱

• Case 2. o没有左儿子，则o的前驱为o的前驱指针指向的结点

后序线索二叉树

后序线索二叉树的构造

对于每个结点o而言，重新定义其左、右儿子指针lson,rson:

• 左儿子指针lson:

• • Case 1:若o存在左儿子，则lson仍指向其左儿子，o->ltag=0
• • Case 2:若o不存在左儿子，则lson指向其在后序遍历序列中的前驱，o->ltag=1

• 右儿子指针rson:

• • Case 1:若o存在右儿子，则rson仍指向其右儿子，o->rtag=0
• • Case 2:若o不存在右儿子，则rson指向其在后序遍历序列中的后继，o->rtag=1

后序线索二叉树的遍历

查找结点o的前驱

• Case 1. o有左儿子，则

• • (i)o无右儿子，则o的左儿子是o的前驱，因为访问完o的左儿子后，就要返回访问其父节点o
• • (ii)o有右儿子，则o的右儿子是o的前驱，因为访问完o的右儿子后，就要返回访问其父节点o

• Case 2. o没有左儿子，则o的前驱为o的前驱指针指向的结点

查找结点o的后继

• Case 1. o有右儿子，则

• • (i)o是fa[o]的右儿子，则o的后继是fa[o]
• • (ii)o是fa[o]的左儿子，则:
• • • 若fa[o]无右儿子，o的后继是fa[o]
• • • 否则，下一步应访问fa[o]的右子树，其后继结点应为fa[o].rson的后序遍历序列的第一个结点，即fa[o].rson的最左下结点

• Case 2. o没有右儿子，则o的后继为o的后继指针指向的结点

可见，后序线索二叉树中，查找前驱很方便，但是查找后继非常麻烦

先序线索二叉树

先序线索二叉树的构造

对于每个结点o而言，重新定义其左、右儿子指针lson,rson:

• 左儿子指针lson:

• • Case 1:若o存在左儿子，则lson仍指向其左儿子，o->ltag=0
• • Case 2:若o不存在左儿子，则lson指向其在先序遍历序列中的前驱，o->ltag=1

• 右儿子指针rson:

• • Case 1:若o存在右儿子，则rson仍指向其右儿子，o->rtag=0
• • Case 2:若o不存在右儿子，则rson指向其在先序遍历序列中的后继，o->rtag=1

先序线索二叉树的遍历

查找结点o的前驱

• Case 1. o有左儿子，则：

• • (i)o是fa[o]的右儿子，则o的后继是fa[o]
• • (ii)o是fa[o]的左儿子，则:
• • • 若fa[o]无右儿子，o的后继是fa[o]
• • • 否则，下一步应访问fa[o]的右子树，其后继结点应为fa[o].rson的先序遍历序列的第一个结点，即fa[o].rson

• Case 2. o没有左儿子，则o的前驱指针指向其前驱结点

查找结点o的后继

• Case 1. o有右儿子，则

• • (i)o没有左儿子，则o的后继是o->rson
• • (ii)o有左儿子，则o的后继是o->lson

• Case 2. o没有右儿子，则o的后继为o的后继指针指向的结点

可见，先序线索二叉树和后序正好相反，查找后继很方便，但是查找前驱非常麻烦

参考文献：

[1]waret.线索二叉树的及其遍历问题 .http://waret.iteye.com/blog/709779