中序穿线二叉树

溯影

《数据结构C++描述》 清华大学出版社    任燕编著
小弟学习一下中序穿线二叉树，发现里面有很多的方法都和普通的二叉树有所不同，
比如遍历，删除结点等方法都和普通二叉树的方法有较大差异，同时小弟也是改正了书上类模板程序中一个方法的bug
还请大神指教，加油！！！

#include <iostream>
#include <cstdlib>
#include <assert.h>
#include <cstdbool>
using namespace std;

typedef enum PointerTag{ LINK, THREAD };                                //相当于LINK = 0,THREAD = 1

template <typename elemtype>
class ThreadTree{
public:
        //中序穿线二叉树（二叉链表存储）结点的数据结构C++类定义
        class ThreadTNode{
        public:
                //这里的构造函数已经给赋值ltag = LINK和rtag = LINK，所以接下来
                //线索话操作只管THREAD赋值即可
                ThreadTNode() :ltag(LINK), left(NULL), rtag(LINK), right(NULL){};
                ~ThreadTNode(){};
        public:
                elemtype data;                                                                        //数据域
                class ThreadTNode *left, *right;                                //左右指针域
                PointerTag ltag, rtag;                                                        //左右指针标记
        };
        typedef ThreadTNode* NodePointer;                                        //指向结点的指针类型声明

public:
        //中序穿线二叉树置空
        void clear();
        //中序穿线二叉树置空辅助函数
        void clear_aux(NodePointer p);


        //递归求中序穿线二叉树的深度
        int depth();
        //递归求中序穿线二叉树的深度的辅助函数
        int depth_aux(NodePointer p);


        //取中序穿线二叉树的根指针
        NodePointer getRoot();


        //中序遍历中序穿线二叉树
        void inOrderTraverse_ThreadTree();
        //中序遍历中序穿线二叉树的辅助函数
        void inOrderTraverse_ThreadTree_aux(NodePointer p);


        //判断是否为空
        bool isEmpty();


        //生成中序穿线二叉树
        void CreateThreadTree();
        //生成中序穿线二叉树的辅助函数
        void CreateThreadTree_aux(NodePointer &p);


        //中序穿线二叉树穿线操作
        void seqToThreadTree();
        //中序穿线二叉树穿线操作的辅助函数
        void seqToThreadTree_aux(NodePointer &p);


        //找指定结点中序的前驱
        bool searchPriorNode(elemtype key, elemtype& prior);


        //找指定结点中序的后继
        bool searchNextNode(elemtype key, elemtype& next);


        //找指定结点
        bool searchNode(elemtype key, NodePointer &p);

        //中序穿线二叉树构造函数重载
        ThreadTree();

        //析构函数
        ~ThreadTree();
private:
        NodePointer root;
};

//取二叉树的根指针
template <typename elemtype>
typename ThreadTree<elemtype>::NodePointer ThreadTree<elemtype>::getRoot(){
        return root;
}



//中序穿线二叉树构造函数重载
template <typename elemtype>
ThreadTree<elemtype>::ThreadTree(){
        root = NULL;
}


//创建中序穿线二叉树
template <typename elemtype>
void ThreadTree<elemtype>::CreateThreadTree(){
        CreateThreadTree_aux(root);
}

//创建中序穿线二叉树的辅助函数
template <typename elemtype>
void ThreadTree<elemtype>::CreateThreadTree_aux(NodePointer &p){
        elemtype value;
        cout << "请输入结点的值(输入零代表叶子的终结):";
        cin >> value;
        if (value == 0){
                p = NULL;
        }
        else{
                p = new ThreadTNode;
                assert(p != 0);
                p->data = value;
                CreateThreadTree_aux(p->left);
                CreateThreadTree_aux(p->right);
        }
}


//删除中序穿线二叉树
template <typename elemtype>
void ThreadTree<elemtype>::clear(){
        clear_aux(root);
}

//删除中序穿线二叉树的辅助函数
template <typename elemtype>
void ThreadTree<elemtype>::clear_aux(NodePointer p){
        if (p){
                if (p->ltag == LINK){
                        clear_aux(p->left);
                }
                if (p->rtag == LINK){
                        clear_aux(p->right);
                }
                delete p;
                cout << "删除结点..." << endl;
        }
}

//析构函数
template <typename elemtype>
ThreadTree<elemtype>::~ThreadTree(){
        clear();
        root = NULL;                                //根指针置空
}


//中序遍历中序穿线二叉树
template <typename elemtype>
void ThreadTree<elemtype>::inOrderTraverse_ThreadTree(){
        inOrderTraverse_ThreadTree_aux(root);
}

//中序遍历中序穿线二叉树操作
template <typename elemtype>
void ThreadTree<elemtype>::inOrderTraverse_ThreadTree_aux(NodePointer p){
        while (p){
                //首先沿着其左子树的左指针向下滑动，直到某结点有左线索为止
                while (p->ltag == LINK){
                        p = p->left;
                }
                //访问该结点
                cout << p->data << "\t";
                //如果该结点有右线索，那么沿着右线索一直往上爬，访问右线索上的每一个结点
                //直到某结点不再是右线索，而有右指针为止
                while (p->rtag == THREAD && p->right){
                        p = p->right;
                        cout << p->data << "\t";
                }
                //进入右子树
                p = p->right;
        }
}




//递归求二叉树深度
template <typename elemtype>
int ThreadTree<elemtype>::depth(){
        return depth_aux(root);
}

//求二叉树深度的辅助函数
template <typename elemtype>
int ThreadTree<elemtype>::depth_aux(NodePointer p){
        int lDep, rDep;                                //预存放左右子树的深度
        if (!p){
                return 0;
        }
        else{
                if (p->ltag == LINK){                                                //如果指针p不为空且所指向的结点有左指针
                        lDep = depth_aux(p->left);                                //那么用左指针自递归求左子树的深度
                }
                else{                                                                                //如果指针p不为空且所指结点有左线索
                        lDep = 0;                                                                //其左子树的深度为0
                }
                if (p->rtag == LINK){                                                //如果指针p不为空且所指向的结点有右指针
                        rDep = depth_aux(p->right);                                //那么用右指针自递归求左子树的深度
                }
                else{                                                                                //如果指针p不为空且所指结点有右线索
                        rDep = 0;                                                                //其右子树的深度为0
                }

                return (lDep > rDep ? lDep : rDep) + 1;
        }
}



//中序穿线二叉树的穿线操作
template <typename elemtype>
void ThreadTree<elemtype>::seqToThreadTree(){
        seqToThreadTree_aux(root);
}

//中序穿线二叉树穿线操作的辅助函数
template <typename elemtype>
void ThreadTree<elemtype>::seqToThreadTree_aux(NodePointer &p){
        //当前结点按中序遍历的前驱的指针，初始化为空
        static NodePointer pre = NULL;

        if (p){
                //如果当前结点不为空，那么对以其为根的子树进行中序穿线
                //用当前结点的left自递归，完成左子树的线索化
                seqToThreadTree_aux(p->left);
                if (!p->left){
                        //如果当前结点的left为空，那将其作为中序的前驱线索
                        p->ltag = THREAD;
                        p->left = pre;
                }
                if (pre&&!pre->right){
                        //如果当前结点按中序遍历的前驱的right为空，那么将其用作中序的后继线索
                        pre->rtag = THREAD;
                        pre->right = p;
                }
                pre = p;                                //更新当前结点按照中序遍历的前驱指针

                //用当前结点的right自递归，完成右子树的线索化
                seqToThreadTree_aux(p->right);

        }
        if (p == root){
                //如果当前结点等于根节点，那么完成了所有结点的中序穿线
                //最后一个结点的右标记标注为线索，且右线索设置为空
                //当前结点按照中序遍历前驱的指针置空，以便再次调用此函数做线索化
                if (pre){
                        pre->rtag = THREAD;
                        pre->right = NULL;
                }
                pre = NULL;
        }
}

//找指定结点
template <typename elemtype>
bool ThreadTree<elemtype>::searchNode(elemtype key, NodePointer &p){
        p = root;
        while (p){
                while (p->ltag == LINK){
                        p = p->left;
                }
                //判断该结点的数据域是否等于要查找的值
                if (p->data == key){
                        return true;
                }
                //如果该节点有右线索，则沿着右线索一直向上爬，知道某节点出现右指针为止
                //判断右结点上每个结点的数据域是否和key值相等
                while (p->rtag == THREAD && p->right){
                        p = p->right;
                        if (p->data == key){
                                return true;
                        }
                }
                //进入右子树
                p = p->right;
        }

        return false;
}

//找指定结点的前驱
template <typename elemtype>
bool ThreadTree<elemtype>::searchPriorNode(elemtype key, elemtype &prior){
        NodePointer p;                                                        //预指向待查节点的指针
        if (searchNode(key, p)){                                //此时这里已经有p的地址了
                if (p->ltag == THREAD){                        
                        if (!p->left){
                                return false;
                        }
                        else{
                                prior = p->left->data;
                        }
                }
                else{
                        p = p->left;
                        while (p->rtag == LINK){
                                p = p->right;
                        }
                        prior = p->data;
                }
        }
        return true;
}


//找指定结点中序的后继
template <typename elemtype>
bool ThreadTree<elemtype>::searchNextNode(elemtype key, elemtype& next){
        NodePointer p;
        if (searchNode(key, p)){
                if (p->rtag == THREAD){
                        if (!p->right){
                                return false;
                        }
                        else{
                                next = p->right->data;
                        }
                }
                else{
                        p = p->right;
                        while (p->ltag == LINK){
                                p = p->left;
                        }
                        next = p->data;
                }
        }
        return true;
}



int main(void){
        ThreadTree<int> tt1;
        tt1.CreateThreadTree();                                //创建中序穿线二叉树框架
        tt1.seqToThreadTree();                                //穿线操作
        tt1.inOrderTraverse_ThreadTree();
        cout << endl;
        cout << "深度为:" << endl;
        cout << tt1.depth() << endl;

        cout << "请输入要查找的指定结点的值:";
        int key;
        cin >> key;

        ThreadTree<int>::NodePointer p = tt1.getRoot();                //获取root指针

        if (tt1.searchNode(key, p)){
                cout << "有这个结点" << endl;
                cout << "其中序前驱的值是:";
                int prior;
                tt1.searchPriorNode(key, prior);
                cout << prior << endl;

                cout << "其中序后继的值是:";
                int next;
                tt1.searchNextNode(key, next);
                cout << next << endl;
        }

        return 0;
}

溯影

中序穿线二叉树原来在线索化过程中结点指针指向变了，所以进行中序遍历的时候要用线索来循环遍历，在删除结点的时候也要用线索，线索化完成后二叉树全部指针域只有两个是空，一个是中序遍历开始结点左指针区域指向为空，另一个是中序遍历最后一个结点右指针域为空，怪不得要是线索化完成后按照普通的二叉树中序自递归遍历会无限递归爆栈