1. Where did it could work?
2. Have any properties ?
3.How come we want to threaded a tree into a link?
4. How can we create a threaded tree ?
5. source code
#include <stdio.h>
typedef int INDEX;
enum ORDER {
OR_PRE,
OR_POST,
OR_IN,
OR_INVALIED,
};
/**
* The node of a tree. Because it's data region is unknown, we build a
* template class to ensure it can match with different data element.
*/
template <class ELEM>
class NODE {
public:
NODE<ELEM> *left;
NODE<ELEM> *right;
ELEM ele;
/*
* In a threaded tree, we need two tags to ensure the status of pointer region.
*/
bool rtag;
bool ltag;
};
/**
* the type of data region. For uniform the use of target data, Here define
* a macro.
*/
#define ELEMENT char
/**
* This is a common interface for user do some operation. It is defined by
* user and called by every node when do a throughout traversal.
*/
typedef bool (*CallBack)( NODE<ELEMENT> *data);
/**
* The core class, it is provide some operation that is needed by deal with the
* binary tree . some of non-core operation is not defined.
*/
class BTREE:public NODE<ELEMENT> {
public:
BTREE( );
~BTREE( );
/*
* Create a tree by a string.
*/
bool CreateBTree( char *);
bool DestroyBTree( );
bool EmptyBTree( );
/*
* Three types of ergodic : inorder, preorder and postorder. In inorder traversal,
* we will initialize those idle region of nodes to create a threaded tree.
*/
bool InOrder( CallBack func);
bool PreOrder( CallBack func);
bool PostOrder( CallBack func);
/*
* After do a inorder traversal, a threaded tree will be created automatically..
* Of course, It is a inorder threaded tree. Based on those data, we can
* do a inorder traversal simply, no longer need recursion operation.
*/
bool InOrder_th( CallBack func);
private:
/*
* used to create a tree by a string.
*/
bool createSubTree( char *tree, INDEX &pos, NODE<ELEMENT> **p_child);
/*
* Normally, we traverse a tree by recursion operation. The following is
* the recursion function corresponding to different order .
*/
bool _InOrder( CallBack func, NODE<ELEMENT> *nod);
bool _PreOrder( CallBack func, NODE<ELEMENT> *nod);
bool _PostOrder( CallBack func, NODE<ELEMENT> *nod);
/*
* used to create a link between two nodes.
*/
bool _CreateLink( NODE<ELEMENT> *nod, NODE<ELEMENT> *last);
/*
* point to root node.
*/
NODE<ELEMENT> *root;
/*
* In general, It is a invalied value. After do a traversal, we will create
* a threaded tree , this member is used to record what kind of current
* threaded tree. This is important, since different threaded tree have
* a different rules for use.
*/
ORDER order;
/*
* we record every node which we was arrived at last time. So when we
* arrive a new node, if necessary, we can create a link between those
* two nodes .
*/
NODE<ELEMENT> *last;
/*
* A threaded tree have a head node and it is not always the root node.
* So it is needful to have a pointer to this head node.
*/
NODE<ELEMENT> *head;
/*
* This is the end node of a threaded tree. Sometime we maybe want to
* traversal a tree by reversed direction.
*/
NODE<ELEMENT> *end;
};
BTREE::BTREE( )
{
this->root = NULL;
this->order = OR_INVALIED;
this->last = NULL;
this->head = NULL;
this->end = NULL;
}
BTREE::~BTREE( )
{
if( this->root!=NULL)
{
this->DestroyBTree( );
this->root = NULL;
this->last = NULL;
this->head = NULL;
this->end = NULL;
}
}
/*
* create a tree.
*/
bool BTREE::CreateBTree( char *tree)
{
INDEX pos = 0;
return this->createSubTree( tree, pos, &this->root);
}
bool BTREE::DestroyBTree( )
{
return false;
}
bool BTREE::EmptyBTree( )
{
return false;
}
/**
* Create a tree by a string.
*/
bool BTREE::createSubTree( char *tree, INDEX &pos, NODE<ELEMENT> **p_child)
{
/*
* if we encounter a '\0' or ' ', that's means this branch is NULL.
*/
if( (tree[pos]!='\0')
&&(tree[pos]!=' ') )
{
/*
* create a node for this normal char. Then we will try to create it's child.
* Of cource, if the following char is a abnormal char, that's means there
* are no child for this node.
*/
*p_child = new NODE<ELEMENT>;
(*p_child)->ele = tree[pos];
(*p_child)->left = NULL;
(*p_child)->right = NULL;
(*p_child)->rtag = false;
(*p_child)->ltag = false;
/*
* recur to create sub-tree.
*/
pos++;
this->createSubTree( tree, pos, &(*p_child)->left);
pos ++;
this->createSubTree( tree, pos, &(*p_child)->right);
return true;
}
*p_child = NULL;
return false;
}
bool BTREE::InOrder( CallBack func)
{
this->last = NULL;
if( this->_InOrder( func, this->root))
{
this->order = OR_IN;
return true;
}
else
{
this->order = OR_INVALIED;
return false;
}
}
bool BTREE::_InOrder( CallBack func, NODE<ELEMENT> *nod)
{
if( nod!=NULL)
{
if( !nod->ltag)
this->_InOrder( func, nod->left);
if( func!=NULL)
func( nod);
//create link
this->_CreateLink( nod, this->last);
//save the head of nodes.
if( this->last==NULL)
{
this->head = nod;
}
this->last = nod;
if( !nod->rtag)
this->_InOrder( func, nod->right);
return true;
}
return false;
}
bool BTREE::_CreateLink( NODE<ELEMENT> *nod, NODE<ELEMENT> *last )
{
nod->ltag = false;
nod->rtag = false;
if( nod->left==NULL)
{
nod ->left = last;
nod->ltag = true;
}
if( ( last!=NULL)
&&(last->right==NULL))
{
last->right = nod;
last->rtag = true;
}
return true;
}
bool BTREE::PostOrder( CallBack func)
{
if( this->_PostOrder( func, this->root) )
{
this->order = OR_POST;
return true;
}
else
{
this->order = OR_INVALIED;
return false;
}
}
bool BTREE::_PostOrder(CallBack func,NODE < ELEMENT > * nod)
{
if( nod!=NULL)
{
if( !nod->ltag)
this->_PostOrder( func, nod->left);
if( !nod->rtag )
this->_PostOrder( func, nod->right);
if( func!=NULL)
func( nod);
return true;
}
return false;
}
bool BTREE::PreOrder( CallBack func)
{
if( this->_PreOrder( func, this->root) )
{
this->order = OR_PRE;
return true;
}
else
{
this->order = OR_INVALIED;
return false;
}
}
bool BTREE::_PreOrder( CallBack func,NODE < ELEMENT > * nod)
{
if( nod!=NULL)
{
if( func!=NULL)
func( nod);
if( !nod->ltag )
this->_PreOrder( func, nod->left);
if( !nod->rtag)
this->_PreOrder( func, nod->right);
return true;
}
return false;
}
/**
* compare this with the normal traversal function , the recursion function
* are avoided.
*/
bool BTREE::InOrder_th(CallBack func)
{
if( this->order!=OR_IN)
{
return false;
}
NODE<ELEMENT> *cur = this->head;
while( cur!=NULL)
{
if( func!=NULL)
func( cur);
if( cur->rtag )
{
cur = cur->right;
}
else
{//find smallest one in right branch.
cur = cur->right;
while( (cur!=NULL)
&& (!cur->ltag) )
{
cur = cur->left;
}
}
}
return true;
}
bool show( NODE<ELEMENT> *data)
{
printf(" %c ", data->ele);
fflush( stdin);
//getchar();
return true;
}
/**
* based on our rules, we will create a tree like this.
*
* [1]
* / \
* [2] [3]
* / \ / \
* [4] [5] [6] [7]
* / \
* [8] [9]
*
*/
#define TREE "1248 9 5 36 7 "
/***/
int main()
{
BTREE tree;
tree.CreateBTree( TREE);
tree.InOrder( show);
printf("\n");
tree.InOrder_th( show);
printf("\n");
tree.PreOrder( show);
printf("\n");
tree.PostOrder( show);
printf("\n");
return 0;
}
![树的基本概念(定义、基本术语、性质)[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)