现将二叉树的结点结构重新定义如下：
|
leftchild
|
lefttag | _date | righttag | rightchild |
其中：lefttag=0 时leftchild指向左子女；
lefttag=1 时
leftchild指向前驱；
righttag=0 时rightchild指向右子女；
righttag=1 时
rightchild指向后继
中序线索二叉树图如下
创建二叉树
void _CreateTree(Node*& root,T a[],size_t size,size_t& index,const T& invalid)
{
assert(a);
if(index< size&& a[index]!=invalid)
{
root=new Node(a[index]);
_CreateTree(root->leftchild,a,size,++index,invalid);
_CreateTree(root->rightchild,invalid);
}
}
中序线索化
void _InOrderThead(Node* root,Node* &pre)
{
if(root==NULL)
return ;
_InOrderThead(root->leftchild,pre);
if(root->leftchild==NULL)
{
root->LeftTag=Thread;
root->leftchild=pre;
}
if(pre&&pre->rightchild==NULL)
{
pre->RightTag=Thread;
pre->rightchild=root;
}
pre=root;
_InOrderThead(root->rightchild,pre);
}
前序线索化
void _PrevOrderThead(Node* root,Node* &pre)
{
if(root==NULL)
return ;
if(root->leftchild==NULL)
{
root->LeftTag=Thread;
root->leftchild=pre;
}
if(pre&&pre->rightchild==NULL)
{
pre->RightTag=Thread;
pre->rightchild=root;
}
pre=root;
if(root->LeftTag==Link)
_PrevOrderThead(root->leftchild,pre);
if(root->RightTag==Link)
_PrevOrderThead(root->rightchild,pre);
}
后序线索化
void _PostOrderThead(Node* root,Node* &pre)
{
if(root==NULL)
return;
_PostOrderThead(root->leftchild,pre);
_PostOrderThead(root->rightchild,pre);
if(root->leftchild==NULL)
{
root->LeftTag=Thread;
root->leftchild=pre;
}
if(pre&&pre->rightchild==NULL)
{
pre->RightTag=Thread;
pre->rightchild=root;
}
pre=root;
}
详细代码实现
#include<iostream>
#include<stack>
#include<queue>
#include <assert.h>
using namespace std;
enum PointTag
{
Link,//指针
Thread//线索
};
template <class T>
struct BinTreeNode
{
T _date;
BinTreeNode<T>* leftchild;//左孩子
BinTreeNode<T>* rightchild;//右孩子
PointTag LeftTag;//左孩子线索化标志
PointTag RightTag;//右孩子线索化标志
BinTreeNode(const T& x)
:_date(x),leftchild(NULL),rightchild(NULL),LeftTag(Link),RightTag(Link)
{}
};
template <class T>
class BinTree
{
typedef BinTreeNode<T> Node;
public:
BinTree()
:_root(NULL)
{}
BinTree(T* a,const T& invalid)
:_root(NULL)
{
size_t index=0;
_CreateTree( _root,index,invalid);
}
void PrevOrderThead()
{
Node* pre=NULL;
_PrevOrderThead(_root,pre);
}
void PrevOrder_NonR()
{
Node* root=_root;
if(root==NULL)
return;
while(root)
{
while(root->LeftTag==Link)
{
cout<<root->_date<<" ";
root=root->leftchild;
}
cout<<root->_date<<" ";
root=root->rightchild;
}
cout<<endl;
}
void InOrderThead()
{
Node* pre=NULL;
_InOrderThead(_root,pre);
}
void InOrder_NonR()
{
Node* root=_root;
if(root==NULL)
return;
while(root)
{
while(root->LeftTag==Link)
{
root=root->leftchild;
}
cout<<root->_date<<" ";
while (root->RightTag==Thread)
{
root=root->rightchild;
cout<<root->_date<<" ";
}
root=root->rightchild;
}
cout<<endl;
}
void PostOrderThead()
{
Node* pre=NULL;
_PostOrderThead(_root,pre);
}
void PostOrder_NonR()
{
}
protected:
void _CreateTree(Node*& root,invalid);
}
}
void _InOrderThead(Node* root,pre);
}
void _PrevOrderThead(Node* root,pre);
}
void _PostOrderThead(Node* root,pre);
if(root->leftchild==NULL)
{
root->LeftTag=Thread;
root->leftchild=pre;
}
if(pre&&pre->rightchild==NULL)
{
pre->RightTag=Thread;
pre->rightchild=root;
}
pre=root;
}
private:
Node* _root;
};
