线索二叉树
一 引入遍历二叉树有先序，中序，后序，这三种可以用递归或者栈来实现；
层序遍历可以用队列实现。
如果为了更加方便高效的遍历二叉树，容易想到的是在二叉树结点增加两个指针，分别指向前驱和后继结点。
但无疑会大大降低结点存储密度。
不过考虑到二叉树中，分支数+1=结点数可推出：
n0=n2+1，也就是说，叶子结点数=度为2的结点数+1；
空链域数目：每个叶子结点有2个+每个度为1的结点有1个=2*n0+n1=n2+1+n0+n1=n+1（n是总结点数）
所以可利用这n+1个空指针指向前驱和后继。
所以如果一个结点有左右孩子，那它就不能指向它的前驱后继了。
为了区分节点的两个指针指向的是孩子还是前驱后继，
可以用两个只占两比特的LTag和RTag指示，0(link)表示此指针指向孩子，1（Thread）表指向前驱后继。
另外增加了一个头节点HeadNode。
注意：没有实现后序遍历，是因为后序线索化后，根节点在最后遍历，左子树无后继与右子树关联
若要遍历，仍然需要栈或者递归！
从test.txt读入树，先序方式建立树。如ABD#E###C#JK##M##建立树
例如可以通过
先序建立线索关系如下：
二 程序实现
#ifndef TBTREE_H
#define TBTREE_H
enum PTag{
Link,Thread
};
template <typename T>
struct TBNode{
T data;
TBNode<T> *lchild,*rchild;
PTag LTag:2,RTag :2;
};
template<typename T>
class TBTree{
private:
TBNode<T> *HeadNode,*pre;
void CreateTBTree(ifstream &f,TBNode<T>* &t){
T e;
InputFromFile(f,e);
if(e==Emp) t=NULL;
else {
t=new TBNode<T>;
assert(t!=NULL);
t->data=e;
CreateTBTree(f,t->lchild);
if(t->lchild!=NULL)
t->LTag=Link;
else
t->LTag=Thread;
CreateTBTree(f,t->rchild);
if(t->rchild!=NULL)
t->RTag=Link;
else
t->RTag=Thread;
}
}
void DestroyTBTree(TBNode<T>* &t){
if(t!=NULL){
if(t->LTag==Link)
DestroyTBTree(t->lchild);
if(t->RTag==Link)
DestroyTBTree(t->rchild);
delete t;
t=NULL;
}
}
void InThread(TBNode<T>* p){
if(p!=NULL){
if(p->LTag==Link)
InThread(p->lchild);
else p->lchild=pre;
if(pre->RTag==Thread)
pre->rchild=p;
pre=p;
if(p->RTag==Link)
InThread(p->rchild);
}
}
void PreThread(TBNode<T>* p){
if(p!=NULL){
if(pre->RTag==Thread)
pre->rchild=p;
if(p->LTag==Thread)
p->lchild=pre;
pre=p;
if(p->LTag==Link)
PreThread(p->lchild);
if(p->RTag==Link)
PreThread(p->rchild);
}
}
void PostThread(TBNode<T>* p){
if(p!=NULL){
if(p->LTag==Link)
PostThread(p->lchild);
if(p->RTag==Link)
PostThread(p->rchild);
if(p->LTag==Thread)
p->lchild=pre;
if(pre->RTag==Thread)
pre->rchild=p;
pre=p;
}
}
public :
TBTree(){
HeadNode=new TBNode<T>;
assert(HeadNode!=NULL);
HeadNode->LTag=Link;
HeadNode->RTag=Thread;
HeadNode->rchild=HeadNode->lchild=HeadNode;
}
~TBTree(){
if(HeadNode!=NULL){
if(HeadNode->lchild)
DestroyTBTree(HeadNode->lchild);
delete HeadNode;
}
}
void CreateTBTree(char* FileName){
ifstream fin(FileName);
CreateTBTree(fin,HeadNode->lchild);
fin.close();
}
void InThread(){
if(HeadNode->lchild!=NULL){
pre=HeadNode;
InThread(HeadNode->lchild);
pre->rchild=HeadNode;
HeadNode->rchild=pre;
}
}
void InPrint(void (*visit)(TBNode<T>*))const{
TBNode<T>* p=HeadNode->lchild;
while(p!=HeadNode){
while(p->LTag==Link)
p=p->lchild;
visit(p);
while(p->RTag==Thread&&p->rchild!=HeadNode){
p=p->rchild;
visit(p);
}
p=p->rchild;
}
}
void PreThread(){
if(HeadNode->lchild!=HeadNode){
pre=HeadNode;
PreThread(HeadNode->lchild);
pre->rchild=HeadNode;
HeadNode->rchild=pre;
}
}
void PrePrint(void (*visit)(TBNode<T>*))const{
TBNode<T> *p=HeadNode->lchild;
while(p!=HeadNode){
visit(p);
if(p->LTag==Link)
p=p->lchild;
else
p=p->rchild;
}
}
void PostThread(){
if(HeadNode->lchild!=HeadNode){
HeadNode->rchild=HeadNode->lchild;
pre=HeadNode;
PostThread(HeadNode->lchild);
if(pre->RTag!=Link)
pre->rchild=HeadNode;
}
}
};
#endif
#include <iostream>
#include <fstream>
#include <assert.h>
using namespace std;
typedef char T;
T Emp='#';
void InputFromFile(ifstream &f, T &c)
{
f>>c;
}
void Input(T &c)
{
cin>>c;
}
#include "TBTree.h"
void Visit(TBNode<T> *c)
{
cout<<c->data<<' ';
}
int main()
{
TBTree<T> t;
t.CreateTBTree("test.txt");
t.PreThread();
cout<<"先序遍历：";
t.PrePrint(Visit);
t.InThread();
cout<<endl<<"中序遍历：";
t.InPrint(Visit);
t.PostThread();
cout<<endl;
return 0;
}
运行输出
文档来源：51CTO技术博客https://blog.51cto.com/u_15298598/3118710
页:
[1]