threadtree.cpp

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

#include "ThreadTree.h"
template <class T>
void ThreadTree<T>::createInThread () {
     ThreadNode<T> *pre = NULL;    //前驱结点指针
	 if (root != NULL) {   	         //非空二叉树, 线索化
          createInThread (root, pre);				    //中序遍历线索化二叉树
	      pre->rightChild = NULL;  pre->rtag = 1;		   //后处理中序最后一个结点
	 }
};
template <class T>
void ThreadTree<T>::
createInThread (ThreadNode<T> *current,
    ThreadNode<T> *& pre) {
//通过中序遍历, 对二叉树进行线索化
     if (current == NULL) return;
     createInThread (current->leftChild, pre);
		//递归, 左子树线索化
	 if (current->leftChild == NULL) {				//建立当前结点的前驱线索
          current->leftChild = pre;   current->ltag = 1; 
     }
     if (pre != NULL && pre->rightChild == NULL) 	    //建立前驱结点的后继线索
        { pre->rightChild = current;   pre->rtag = 1; }	
     pre = current;							   //前驱跟上,当前指针向前遍历
	 createInThread (current->rightChild,  pre);		  //递归, 右子树线索化
};

template <class T> 
ThreadNode<T> * ThreadTree <T> :: 
First (ThreadNode<T> * current) {
//函数返回以*current为根的线索化二叉树中的中
//序序列下的第一个结点
    ThreadNode<T> * p = current;
    while (p->ltag == 0) p = p->leftChild;
    return p;
};

template <class T> 
ThreadNode<T> * ThreadTree <T>:: 
Next (ThreadNode<T> * current) {
//函数返回在线索化二叉树中结点*current在中序
//下的后继结点
    ThreadNode<T> *p = current->rightChild;
    if (current->rtag == 0) return First (p);
 	//rtag == 0, 表示有右子女
    else return p;
	//rtag == 1, 直接返回后继线索
};  

template <class T>
ThreadNode<T> *ThreadTree<T>::Last(ThreadNode<T> *current) {
	//函数返回以*current为根的中序线索二叉树中中序序列下的最后一个结点。
	ThreadNode<T> * p = current;
	while (p->rtag == 0) p = p->rightChild;	//最右下结点（不一定是叶结点）
	return p;
};

template <class T>
ThreadNode<T> *ThreadTree<T>::Prior(ThreadNode<T> *current) {
	//函数返回在中序线索二叉树中结点current在中序下的前驱结点。
	ThreadNode<T> *p = current->leftChild;
	if ( current->ltag == 0) return Last(p);	//在左子树中找中序最后一个结点
		else  return p;								//ltag==1, 直接返回前驱线索
};

template <class T>
void ThreadTree <T> ::InOrder (void (*visit) (ThreadNode<T> *t)) {
//线索化二叉树的中序遍历
     ThreadNode<T> * p;  
     for (p = First(root);  p != NULL;  p = Next (p) ) 
         visit (p);
};

template <class T>
void ThreadTree<T>::PreOrder(void (*visit) (ThreadNode<T> *t)) {
	ThreadNode<T> *p = root;  
	while (p != NULL) {
		visit(p);									//访问根结点
		if (p->ltag == 0) p = p->leftChild;		//有左子女,即为后继
		else if (p->rtag == 0) p = p->rightChild;	//否则有右子女,即后继
		else {
			while (p != NULL && p->rtag == 1)	//沿后继线索检测,
				p = p->rightChild;				//直到有右子女的结点
			if (p != NULL) p = p->rightChild;	//右子女即为后继
		}
	}
};

template <class T>
void ThreadTree<T>::PostOrder(void (*visit)(ThreadNode<T> *p)) {
	ThreadNode<T> *t = root;
	while (t->ltag == 0 || t->rtag == 0)			//寻找后序第一个结点
		if (t->ltag == 0) t = t->leftChild;
		else if (t->rtag == 0) t = t->rightChild;
	visit(t);										//访问第一个结点
	ThreadNode<T> *p;
	while ((p = parent(t)) != NULL) {
		if (p->rightChild == t || p->rtag == 1)	//*t是*p的后序后继
			t = p;
		else {										//否则
			t = p->rightChild;						//t移到*p的右子树
			while (t->ltag == 0 || t->rtag == 0)
				if (t->ltag == 0) t = t->leftChild;
				else if (t->rtag == 0) t = t->rightChild;
		}
		visit(t);
	}
};

template <class T>
ThreadNode<T> *ThreadTree<T>::parent(ThreadNode<T> *t) {
	ThreadNode<T> *p;
	if (t == root) return NULL;						//根结点无父结点
	for (p = t; p->ltag == 0; p = p->leftChild);	//求*t为根子树第一个结点
	if (p->leftChild != NULL)
		for (p = p->leftChild; p->leftChild != t && p->rightChild != t;
			p = p->rightChild);
	else {
		for (p = t; p->rtag == 0; p = p->rightChild);
			for (p = p->rightChild; p->leftChild != t && p->rightChild != t; p = p->leftChild);
	}
	return p;
};