2023年6月22日发(作者：)

【数据结构·考研】中序线索⼆叉树中序线索⼆叉树在 n 个结点的⼆叉链表中，有（n+1）个空指针域，利⽤这些空指针域来存放当前结点的直接前驱和后继的线索，可以加快查找速度。普通⼆叉树只能找到结点的左右孩⼦信息，⽽结点的直接前驱和直接后继只能在遍历中获得，若将遍历后对应的前驱和后继预存起来，从第⼀个结点开始就可以顺藤摸⽠⽽遍历整棵树，树实际变成了线性序列。例如中序遍历的结果实际上就是把⼆叉树转化成了线性排列。线索⼆叉树的结构声明typedef struct node{ struct node* left; int ltag = 0; char val; int rtag = 0; struct node* right;}TreeNode,*Tree;

通过中序遍历建⽴中序线索⼆叉树⼀个 pre 指针⼀直指向 t 遍历的前⼀个结点，每次遍历到⼀个结点，如果可以做线索的话，刚好做的是 t 的左线索和 pre 的右线索。这样的话当 t 遍历完时候 pre 的右线索还没有处理，此时 pre 指向遍历完之后的最后⼀个结点，我们给 pre 的右线索置 1 收尾。void InThread(Tree& t,TreeNode* &pre){ //pre指针指向t的中序前驱，在主函数中预设为NULL if(t != NULL){ InThread(t->left,pre); //左⼦树线索化

if(t->left == NULL){ //建⽴当前结点的前驱线索

t->left = pre; t->ltag = 1; } if(pre && pre->right == NULL){ //建⽴前驱结点pre的后继线索

pre->right = t; pre->rtag = 1; } pre = t; InThread(t->right,pre); //右⼦树线索化

}

}

//通过中序遍历建⽴中序线索⼆叉树void CreateThread(Tree& t){ TreeNode* pre = NULL; //前驱指针 if(t != NULL){ InThread(t,pre); pre->rtag = 1; //最后⼀个结点右标志改为1 }

}中序序列下的后继结点中序遍历的过程需要不停寻找下⼀个结点，给定⼀个结点 p ，如果p的 rtag == 1，那么p的右孩⼦就是p的后继结点，如果 p 有右孩⼦，即 rtag == 0，那么p的后继结点就是以 p->right 为根的⼆叉树的中序序列下的第⼀个结点，也就是最左边的结点。//返回结点p在线索⼆叉树中的中序序列下的后继结点TreeNode* successor(TreeNode* p){ if(p->rtag == 1) return p->right; p = p->right; while(p->ltag == 0) p = p->left; return p; //最左下结点

}

中序遍历中序线索⼆叉树现在我们可以开始中序遍历中序线索⼆叉树，先找到第⼀个结点，再⼀直寻找它的后继结点。//中序线索⼆叉树的中序遍历

void Inorder(Tree& t){ TreeNode* p = t; while(p->ltag == 0) p = p->left; for(p;p != NULL;p = successor(p)) cout<ltag<<" "<val<<" "<rtag<<" ";}中序序列下的前驱结点给定⼀个结点 p ，如果寻找 p 的前驱结点呢，如果 p->ltag == 1，那么直接返回 p->left ，如果 p 有左孩⼦，那么 p 的前驱就是p的左⼦树最右边的结点。//返回结点p在线索⼆叉树中的中序序列下的前驱结点TreeNode* predecessor(TreeNode* p){ if(p->ltag == 1) return p->left; p = p->left;

while(p->rtag == 0) p = p->right; //找第⼀个没有右孩⼦的结点

return p;}

中序线索⼆叉树的层次遍历因为线索⼆叉树的叶⼦节点⼏乎没有了空指针，所以进队的条件应该做修改，⽤ ltag、rtag 来判断。//层次遍历

void levelOrderTraverse(Tree& t){ if(t == NULL) return; queue q; TreeNode* p; (t); while(!()){ int width = (); for(int i = 0;i < width;i ++){ p = (); (); cout<ltag<<" "<val<<" "<rtag<<" "; if(p->ltag == 0) (p->left); if(p->rtag == 0) (p->right); } cout<

树还是那棵⽼树，完整代码如下：#include#include#includeusing namespace std;typedef struct node{ struct node* left; int ltag = 0; char val; int rtag = 0; struct node* right;}TreeNode,*Tree;

void InThread(Tree& t,TreeNode* &pre){ //pre指针指向t的中序前驱，在主函数中预设为NULL if(t != NULL){ InThread(t->left,pre); //左⼦树线索化

if(t->left == NULL){ //建⽴当前结点的前驱线索

t->left = pre; t->ltag = 1; } if(pre && pre->right == NULL){ //建⽴前驱结点pre的后继线索

pre->right = t; pre->rtag = 1; } pre = t; InThread(t->right,pre); //右⼦树线索化

}

}

//通过中序遍历建⽴中序线索⼆叉树void CreateThread(Tree& t){ TreeNode* pre = NULL; //前驱指针 if(t != NULL){ InThread(t,pre); pre->rtag = 1; //最后⼀个结点右标志改为1 }

}//返回结点p在线索⼆叉树中的中序序列下的后继结点TreeNode* successor(TreeNode* p){ if(p->rtag == 1) return p->right; p = p->right; while(p->ltag == 0) p = p->left; return p; //最左下结点

}

//中序线索⼆叉树的中序遍历

void Inorder(Tree& t){ TreeNode* p = t; while(p->ltag == 0) p = p->left; for(p;p != NULL;p = successor(p)) cout<ltag<<" "<val<<" "<rtag<<" ";}//返回结点p在线索⼆叉树中的中序序列下的前驱结点TreeNode* predecessor(TreeNode* p){ if(p->ltag == 1) return p->left; p = p->left;

while(p->rtag == 0) p = p->right; //找第⼀个没有右孩⼦的结点

return p;}

//层次遍历

void levelOrderTraverse(Tree& t){ if(t == NULL) return; if(t == NULL) return; queue q; TreeNode* p; (t); while(!()){ int width = (); for(int i = 0;i < width;i ++){ p = (); (); cout<ltag<<" "<val<<" "<rtag<<" "; if(p->ltag == 0) (p->left); if(p->rtag == 0) (p->right); } cout<

//先序构造⼆叉树

void CreateTree(Tree& t){ char x; cin>>x; if(x == '#') t = NULL;

else{ t = new TreeNode;

t->val = x;

CreateTree(t->left);

CreateTree(t->right);

}}

int main(){ Tree t; CreateTree(t); /* a b d # # e # # c f # # # */ CreateThread(t);

cout<<"层次遍历："<

Inorder(t); cout<

p = successor(t); cout<val<

cout<<"t的前驱结点："<val<

}运⾏结果：前序线索⼆叉树和后序线索⼆叉树⼆叉树前序线索化和后序线索化的⽅式与中序线索化相似，只是区别在线索化的时机。前序线索化需要对最后⼀个结点进⾏收尾处理，标志它为线索，⽽后序线索⼆叉树不需要，因为它的最后⼀个遍历结点是根。后序线索⼆叉树不能有效解决寻找后继在后序线索⼆叉树中查找结点 *p 的前驱：若结点 *p ⽆左⼦树，则 p->left 指向其前驱；否则，若结点 *p 有左⼦树，当其右⼦树为空时，其左⼦树的根（即 p->left ）为其后序前驱。当其右⼦树⾮空时，其右⼦树的根（即 p->right ）为其后序前驱。在后序线索⼆叉树中查找结点 *p 的后继：若结点 *p 为根，则⽆后继；若结点 *p 为其双亲的右孩⼦，则其后继为其双亲；若结点*p 为其双亲的左孩⼦，且双亲⽆右⼦⼥，则其后继为其双亲；若结点 *p 为其双亲的左孩⼦，且双亲有右⼦⼥，则结点 *p 的后继是其双亲的右⼦树中按后序遍历的第⼀个结点。所以，求后序线索⼆叉树中结点的后继要知道其双亲的信息，要使⽤栈，所以说后序线索⼆叉树是不完善的。先序线索⼆叉树不能有效解决寻找前驱在先序线索⼆叉树中查找结点的后继较容易，⽽查找前驱要知道其双亲的信息，要使⽤栈，所以说先序线索⼆叉树也是不完善的。