C++線索二叉樹求最矮公共父親節點

C++線索二叉樹求最矮公共父親節點

#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<