#include 
   
     #include 
    
      #include 
     
       using namespace std; class Expection//一个自定义的异常类 { public: void Null_Thing()//空指针异常. { cout<<"Expection!!!,this is null"<
      
        struct Node { Type data; Node
       
         *left; Node
        
          *right; bool ltag;//线索我用bool类型存储。 bool rtag; Node(Type d = Type()):data(d),left(NULL),right(NULL),ltag(false),rtag(false){} }; template
         
           class SBTree { public: SBTree() { root = NULL; } void Insert(const char *s) { Insert(root,s); } void Printf() { Printf(root); } void Init_Thread()//二叉树的线索化。 { Node
          
            *pre = NULL; _Init_Thread(root,pre); } Node
           
             *Fist() { return Fist(root); } void Init_SetDList()//构造双向链表，以root为头节点. { _Init_SetDList(root); } Node
            
              * Find(Type val)//寻找节点,找到则正常，如果找不到则抛出异常。 { Node
             
               *p = NULL; try { p = Find(root,val); } catch(Expection exp) { exp.Null_Thing(); } return p; } Type GetValue(Node
              
                *t)//将节点的Type值取出。 { try { t = Find(t->data); } catch(Expection exp) { exp.Null_Thing(); } return t->data; } Type GetCommParent(Type val1,Type val2)//得到两个节点的最矮公共父亲节点，这才是我想重点写的，其他的都是辅助, { if(_GetCommParent(root,val1,val2)) return _GetCommParent(root,val1,val2)->data; } private: Node
               
                * _GetCommParent(Node
                
                  *t,Type val1,Type val2) { stack
                 
                  * > st; if(Find_commparent(t,val1) && Find_commparent(t,val2)) st.push(t); while(1) { if(Find_commparent(t->left,val1) && Find_commparent(t->left,val2)) { t=t->left; st.push(t); } else if(Find_commparent(t->right,val1) && Find_commparent(t->right,val2)) { t=t->right; st.push(t); } else { if(st.empty()==false) { t = st.top();//用栈搞吧，好像与我开始的本意不符合。 st.pop();//悲剧的我没有用递归搞出来，想的我要吐了，思想是懂了，可是代码总是有问题，唉，容我三思。 return t; } else return NULL; } } } bool Find_commparent(Node
                  
                    *t,Type val) { if(t==NULL) return false; if(t->data == val)return true; else { bool BOOL = Find_commparent(t->left,val); if(BOOL==true) return true; BOOL = Find_commparent(t->right,val); if(BOOL == true) return true; } } Node
                   
                    * Find(Node
                    
                      *t,Type val) { Node
                     
                       *p = NULL; try { p = First(t); } catch(Expection exp) { exp.Null_Thing(); } while(p!=NULL) { if(p->data == val)break; p = p->right; } if(p!=NULL)return p; else throw Expection(); } void _Init_SetDList(Node
                      
                        *t) { Node
                       
                         *p = NULL; try { p = First(t); } catch(Expection exp) { exp.Null_Thing(); } root = p; while(p!=NULL) { cout<
                        
                         data<<" "; p = p->right; } } Node
                         
                           *First(Node
                          
                            *t) { if(t==NULL)throw Expection(); else while(t->left!=NULL) { t = t->left; } return t; } bool _Init_Thread(Node
                           
                             *&t,Node
                            
                              *&pre) { if(t==NULL) { return true; } _Init_Thread(t->left,pre); if(pre != NULL && pre->right==NULL) { pre -> right = t; pre -> rtag = true; } if(t!=NULL && t->left==NULL) { t->left = pre; t->ltag = true; } pre = t; _Init_Thread(t->right,pre); } bool Insert(Node
                             
                               *&t,const char *&s) { if(*s=='#') { t = NULL; return true; } else { t = new Node
                              
                               (*s); Insert(t->left,++s); Insert(t->right,++s); } } void Printf(Node
                               
                                 *t) { if(t!=NULL) { cout<
                                
                                 data<<"\t"; Printf(t->left); Printf(t->right); } } private: Node
                                 
                                   *root; }; int main() { char str[]="ABCD###EF##G##HI##J#K##"; SBTree
                                  
                                    sb; sb.Insert(str); //sb.Init_Thread(); //sb.Find('2'); cout<