数据结构DAY09线索二叉树 [复制链接]

回顾二叉树节点的结构如下，从所描述的节点我们可以很容易得到当前节点的孩子节点。

//二叉树的链式存储typedefintTElemType;typedefstructBiTNode{TElemTypedata;structBiNode*lchild;//左子树structBiNode*rchild;//右子树}BiTNode,*BiTree;普通二叉树的缺陷

不能直接反映节点间的前驱和后继关系，不能像单链表那样直接访问二叉树。

一颗有n个节点的二叉树，假设度为0（叶子节点）节点数为n0，度为1的节点数为n1，度为2的节点数为n2，则二叉树中空指针个数为2*n0+n1，由于n0=n2+1，n=n0+n1+n2（可以参阅上期二叉树性质），可以得到空指针个数为n+1。思考能否使用这些空指针来表示节点前驱和后继关系，使得二叉树可以像单链表那样方便地遍历？，为此我们引入线索二叉树的概念。

我们给二叉树节点添加两个标记，ltag，rtag分别表示左孩子和右孩子所表示的内容。

//线索二叉树存储结构typedefintTElemType;typedefstructThreadNode{TElemTypedata;structThreadNode*lchild;//左孩子指针structThreadNode*rchild;//右孩子指针intltag;//左孩子指针标志，0表示节点的左孩子，1表示节点的前驱intrtag;//右孩子指针标志，0表示节点的右孩子，1表示节点的后继}ThreadNode,*ThreadTree;二叉树的线索化

二叉树的线索化是将二叉树中的空指针改为指向节点的前驱或后继，而节点的前驱和后继是二叉树遍历的结果，根据遍历的方式不同节点的前驱和后继也不同，比如给定一棵二叉树如下所示

先序遍历序列：CBAEDF

中序遍历序列：ABCDEF

后续遍历序列：ABDFEC

在先序遍历中节点E的前驱节点为A后继节点为D，在中序遍历中节点E的前驱节点为D后继节点为F，在后序遍历中节点E的前驱节点为F后继节点为C，因此线索化二叉树可以分为先序线索二叉树、中序线索二叉树、后序线索二叉树

根据上面的遍历序列我们画出对应的线索二叉树（蓝色虚线表示前缀指针，橙色表示后缀指针）

中序线索二叉树实现

中序线索二叉树按照中序遍历的顺序访问二叉树，直到当前节点左指针为空，开始进行线索化，定义一个pre指针指向刚刚访问过的节点，指针p指向当前访问的节点，若p的左孩子为空，则p-lchild=pre，若pre的右孩子为空，则pre-rchild=p

示例代码

//二叉树中序线索化voidInThread(ThreadTree*p,ThreadTree*pre){if(p!=NULL){InThread(p-lchild,pre);if(p-lchild==NULL){p-lchild=pre;p-ltag=1;}if(pre!=NULLpre-rchild==NULL){pre-rchild=p;pre-rtag=1;}pre=p;InThread(p-rchild,pre);}}//建立中序线索二叉树voidCreateInThread(ThreadTreeT){ThreadTreepre=NULL;if(T!=NULL){InThread(T,pre);pre-rchild=NULL;pre-rtag=1;}}

中序线索二叉树遍历

//中序线索二叉树的中序遍历算法voidInOrder(ThreadNode*T){for(ThreadNode*p=FirstNode(T);p!=NULL;p=NextNode(p)){visit(p);}}//求中序序列的第一个节点ThreadNode*FirstNode(ThreadNode*p){while(p-ltag==0){p=p-lchild;}returnp;}//求中序序列的下一个节点ThreadNode*NextNode(ThreadNode*p){if(p-rtag==0){returnFirstNode(p-rchild);}else{returnp-rchild;}}

先序线索二叉树

先序线索二叉树按照先序遍历的顺序访问二叉树，直到当前节点左指针为空，开始进行线索化，定义一个pre指针指向刚刚访问过的节点，指针p指向当前访问的节点，若p的左孩子为空，则p-lchild=pre，若pre的右孩子为空，则pre-rchild=p

示例代码

//二叉树先序线索化voidPreThread(ThreadTree*p,ThreadTree*pre){if(p!=NULL){if(p-lchild==NULL){p-lchild=pre;p-ltag=1;}if(pre!=NULLpre-rchild==NULL){pre-rchild=p;pre-rtag=1;}pre=p;PreThread(p-lchild,pre);PreThread(p-rchild,pre);}}//建立先序线索二叉树voidCreatePreThread(ThreadTreeT){ThreadTreepre=NULL;if(T!=NULL){PreThread(T,pre);pre-rchild=NULL;pre-rtag=1;}}

先序线索二叉树遍历

//先序线索二叉树的先序遍历算法voidPreOrder(ThreadNode*T){for(ThreadNode*p=FirstNode(T);p!=NULL;p=NextNode(p)){visit(p);}}//求先序序列的第一个节点ThreadNode*FirstNode(ThreadNode*p){returnp;}//求先序序列的下一个节点ThreadNode*NextNode(ThreadNode*p){if(p-ltag==0){returnFirstNode(p-lchild);}else{returnp-rchild;}}

后序线索二叉树

后序线索二叉树按照后序遍历的顺序访问二叉树，直到当前节点左指针为空，开始进行线索化，定义一个pre指针指向刚刚访问过的节点，指针p指向当前访问的节点，若p的左孩子为空，则p-lchild=pre，若pre的右孩子为空，则pre-rchild=p

示例代码

//二叉树后序线索化voidPostThread(ThreadTree*p,ThreadTree*pre){if(p!=NULL){PostThread(p-lchild,pre);PostThread(p-rchild,pre);if(p-lchild==NULL){p-lchild=pre;p-ltag=1;}if(pre!=NULLpre-rchild==NULL){pre-rchild=p;pre-rtag=1;}pre=p;}}//建立后序线索二叉树voidCreatePostThread(ThreadTreeT){ThreadTreepre=NULL;if(T!=NULL){PostThread(T,pre);}}

后序线索二叉树遍历

//后序线索二叉树的后序遍历算法voidPostOrder(ThreadNode*T){for(ThreadNode*p=FirstNode(T);p!=NULL;p=NextNode(p)){visit(p);}}//求后序序列的第一个节点ThreadNode*FirstNode(ThreadNode*p){while(p){if(p-ltag==0){p=p-lchild;continue;}pre=p;if(pre-rtag==1){returnpre;}else{p=p-rchild;}}}//求后序序列的下一个节点ThreadNode*NextNode(ThreadNode*p){if(p-rtag==1){returnp-rchild;}else{returnFirstNode(p-rchild);}}参考文献

[1]数据结构：C语言版.严蔚敏等.北京：清华大学出版社，

[2]数据结构考研复习指导：王道论坛.电子工业出版社

[3]数据结构：第二版.陈越.北京：高等教育出版社