首页 > 代码库 > 二叉树及其线索化分析
二叉树及其线索化分析
1. Where did it could work?
/**
* Q: Where did it could work?
*
* A: Bin-tree is generally used in deal with work about search or sort. For a balance tree, it‘s depth is log2(n). That‘s means if we want to find a node in the tree we need
* only do choice at most log2(n). This is very exciting compare with the normal search algorithm,which search a node by check nodes one by one. of course, not all of
* binary trees have this feature, that is depend on the rules what we used to create this tree. By choice varied rules, we could get some amazing result. For example:
* ordered tree is helpful if we want to get a excellent search performance, or insert a member into a sequence quickly; we use maximum tree to build heap sort; we
* use the feature of tree to build a Huffman coding and the like.
*
* Here is an examples about heap sort.
* http://blog.csdn.net/u012301943/article/details/34136891#t12
*/
2. Have any properties ?
/**
* Q: Have any properties ?
*
* A: Though the types of tree is varied, they still have some common features. For a complete binary tree, we could ensure all of it‘s nodes have two child except for leaf
* node and the parent of the last leaf node. so the features is as following:
*
* 1). if the number of node in the n-th layer is labeled as L(n), then
* L(n+1) = L(n) + L(n-1) + ...L(2) + L(1) + 1, except for the last layer.
*
* Demonstrate this conclusion:
* Image this, we have a tree ,which‘s depth is n; In first layer, it have 2^0 nodes;
* In second layer, it have 2^1 nodes.
*
* O -- 2^0
* O O -- 2^1
* O O O O -- 2^2
* . .
* . .
* . .
* .
* O O ................ O O -- 2^(n-2)
* O O ................ O O -- 2^(n-1)
*
*
* So, How many nodes in this tree?
* The answer should as following ,
*
* S(n) = 2^0 + 2^1 + ....2^(n-1) = 2^n -1
* based on this conclusion, we know
*
* S(n+1) = 2^(n+1) - 1 = 2^n + 2^n - 1 = 2^n + S(n)
* L(n+1) = S(n+1) - S(n) = 2^n -1 + 1 = S(n) + 1
*
*
* 2). Number all of nodes from top to bottom, from left to right. if the number of root node is 1 and we labeled the i-th node as N(i), then we can ensure that
* Left child : N(2*i)
* right child: N(2*i + 1)
*
* Demonstrate this conclusion:
*
* now , we number all of nodes in a tree. Based on our conclusion above , we could to know the number of every node is 2^n + X(n) - 1; X means for
* the position of this node in corresponding layer.
*
* O -- 2^0 + X0 -1
* O O -- 2^1 + X1 -1
* O O O O -- 2^2 + X2 -1
* . .
* . .
* . .
* .
* O O ................ O O -- 2^(n-2) + X[n-2] - 1
* O O ................ O O -- 2^(n-1) + X[n-1] - 1
*
* if there is a node W in the i-th layer, we can know it‘s number is
* 2^(i-1) + X[i-1] -1.
*
* then the number of right child of W should be
* 2^i + X[i] - 1.
*
* it is easy to prove that:
* X(i+1) = 2*X(i)
*
* combine the conclusion above, we could know :
* Node : 2^i + X(i) - 1
* Right child : 2^(i+1) + X[i+1] -1 = 2^(i+1) + 2*X[i] - 1
* =2*( 2^i + X[i] - 1 ) +1
*
* that‘s means ,
* Node : i
* Right child : 2*i + 1
* Left child : 2*i
*/
3.How come we want to threaded a tree into a link?
/**
* Q: How come we want to threaded a tree into a link?
*
*
* As we all know , generally, our node is like this
*
* struct node{
* struct node *lchild;
* struct node *rchild;
* DATA data;
* };
*
* there are three member. we use @lchild and @rchild to save a pointer to the node‘s child. But for leaf node, we didn‘t use this region. That is a waste resource.
*
* Can I reuse those resources ?
*
* Of course, we can. Think about this: How can we throughout a tree?
*
* Recursion is a common way. Actually, what we really need is a stack, which have a feature of first-in and last-out. So we have two choices if we want to throughout
* a tree. First method is use function recursion. In this case, the system will automaticlly create a stack for us. Second method, create a stack and manage it by ourself.
* No matter what we choice, the cost is still expensive. Now, we have some idle resources.Some people introduce a method to use those resources to solve this
* problem. when we want to throughout a tree, this way can protect us from the expensive recursion operation. In other words, we can use some idle resources to
* improve our binary tree.
*/
4. How can we create a threaded tree ?
/**
* Q: How can we create a threaded tree ?
*
* A: First at all, some bad news need to clarify. As we all know, we have three kinds of ergodic order: preorder, inorder and postorder. If we want to create a
* threaded tree They must be have different requests for idle resources. On the other hand, we have two types of threaded tree: towards to back, toward to
* head. They have different requests to idle resources too . In a word, we have the following conclusion:
*
* 1). For inorder traversal, the idle resources is match with the requests. We can create two types of threaded tree: toward to back and toward to head.
* 2). For preorder traversal, the situation is become awful. We can only create the threaded tree that toward to back.
* 3). For postorder traversal, we can only create the threaded tree that toward to head.
*
* (Need to say, there are some trick to cover this problem, but difficult.)
* we should have demonstrated the conclusion above, explain it as clear and simple as possible, but, unfortunately,that is out of my league. All of the text above is
* just want to clarify a fact: we can‘t create a threaded tree always, sometime it is difficult since we haven‘t a match idle resource. Now, It time to return our issue.
* Actually, the process of initialize a threaded tree is simple. What we need to do is just through a tree by a order, and initialize some idle region in some nodes.
*/
5. source code
/*
* Here is a simple source code about the threaded binary tree. There are many problem in it. But easy on it, it just a example:
*/
#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;}