手がかりツリーの作成、中順遍歴、左右挿入

#include <iostream>
#include <stdio.h>

using namespace std;

struct binTreeNode
{
    char data;
    bool lthread,rthread;
    binTreeNode *lchild, *rchild;
};


//     ：
void creatBinTreePre(binTreeNode *&T)
{
    char c;
    c = getchar();
    if('^' == c)
    T = NULL;
    else{
        T = new binTreeNode;
        T->data = c;
        creatBinTreePre(T->lchild);
        creatBinTreePre(T->rchild);
    }
}


//      ：
void inOrderThreading(binTreeNode *&T, binTreeNode *&pre)
{
    if(T){
        inOrderThreading(T->lchild,pre);
        if(!T->lchild){
            T->lthread = true;
            T->lchild = pre;
        }
        if(!pre->rchild){
            pre->rthread = true;
            pre->rchild = T;
        }
        pre = T;
        inOrderThreading(T->rchild,pre);
    }
}

//          
void inithread(binTreeNode *&T, binTreeNode *&root)
{
    binTreeNode *pre = new binTreeNode;
    if( T ){
        pre->lchild = T;
        pre->rchild = pre;
        root = pre;
        inOrderThreading(T, pre);
        pre->rthread = true;
        pre->rchild = root;
    }
    else{
        pre->lchild = pre;
        pre->rchild = pre;
    }

}


//         ：
binTreeNode *insucc(binTreeNode *tree)
{
    binTreeNode *temp;
    temp = tree->rchild;
    if(!tree->rthread)
        while(!temp->lthread)
            temp = temp->lchild;
    return temp;
}

//        ：
void tinorder(binTreeNode *tree)
{
    binTreeNode *temp = tree;
    while(1){
        temp = insucc(temp);
        if(temp == tree)
            break;
        cout<<temp->data<<endl;
    }
}

//              
binTreeNode *findParentNode(char c, binTreeNode *tree)
{
    binTreeNode *temp = tree;
    while(1){
        temp =insucc(temp);
        if(temp == tree)
            break;
        if(temp->data == c)
            return temp;
    }
}

//   
void insertRight(binTreeNode *parent, binTreeNode *child)
{
    binTreeNode *temp = NULL;
    child->rchild = parent->rchild;
    child->rthread = parent->rthread;
    child->lchild = parent;
    child->lthread = true;
    parent->rchild = child;
    parent->rthread = false;
    if(!child->rthread){
        temp = insucc(child);
        temp->lchild = child;
    }
}

//   
void insertLeft(binTreeNode *parent, binTreeNode *child)
{
    binTreeNode *temp = NULL;
    if(!parent->lthread){
     temp = parent->lchild;
     while(insucc(temp) != parent){
        temp = insucc(temp);
     }
     temp->rchild = child;
     temp->rthread = true;
    }
    child->lchild = parent->lchild;
    child->lthread = parent->lthread;
    child->rchild = parent;
    child->rthread = true;
    parent->lchild = child;
    parent->lthread = false;
}

 int main()
 {
    binTreeNode *T = NULL, *root = NULL, *parent = NULL, *child = NULL;
    char c;
    creatBinTreePre( T );
    inithread(T, root);

    cout<<"            ：
";
    tinorder(root);

    cout<<"------------   ---------
";
    cout<<"              ：";
    cin>>c;
    parent = findParentNode(c, root);
    cout<<"              ：";
    cin>>c;
    child = new binTreeNode;
    child->data = c;
    insertRight(parent, child);
    cout<<"                ：
";
    tinorder(root);

    cout<<"------------   ---------
";
    cout<<"              ：";
    cin>>c;
    parent = findParentNode(c, root);
    cout<<"              ：";
    cin>>c;
    child = new binTreeNode;
    child->data = c;
    insertLeft(parent, child);
    cout<<"                ：
";
    tinorder(root);

    return 0;
}