首页 > 代码库 > 二叉树及其线索化分析

二叉树及其线索化分析

 

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;}