线索二叉树的基本操作

线索二叉树的结构体

//线索二叉树定义
typedef struct ThreadTreeNode{
    int data;
    int ltag,rtag;
    struct ThreadTreeNode *lchild,*rchild,*parent;
}ThreadTreeNode,*ThreadTree;

线索二叉树的基本操作

//带父结点的二叉树的建立
ThreadTree createWP(){
	int data;
	scanf("%d",&data);
	ThreadTree t = NULL;
	if(data!=-1){
		t = (ThreadTreeNode*)malloc(sizeof(ThreadTreeNode));
		t->ltag = t->rtag = 0;
		t->data = data;
		t->lchild = createWP();
		//父节点绑定 
		if(t->lchild){
			t->lchild->parent = t;
		} 
		t->rchild = createWP();
		//父节点绑定 
		if(t->rchild){
			t->rchild->parent = t;
		}
	}else{
		return t;
	}
} 

////对二叉树中序线索化
//递归子函数 
void InThreadBiTree(ThreadTree &t,ThreadTree &p){
	if(t){
		InThreadBiTree(t->lchild,p);
		if(t->lchild==NULL){
			t->lchild = p;
			t->ltag = 1;
		} 
		if(t->rchild==NULL){
			t->rchild = p;
			t->rtag = 1;
		}
		p = t;
		InThreadBiTree(t->rchild,p);
	}
}
//主函数
void CreateInThread(ThreadTree t){
	ThreadTree p = NULL;
	if(t){
		InThreadBiTree(t,p);
		p->rchild = NULL;
		p->rtag = 1;
	} 
} 

////中序线索二叉树的遍历
//求中序线索二叉树序列中的第一个结点
ThreadTree FirstNode(ThreadTree t){
	//寻找最左下的结点 
	while(t->ltag == 0){
		//有左孩子就向左移动 
		t = t->lchild;
	}
	return t;
} 

//求中序线索二叉树中某个结点的后继
ThreadTree NextNode(ThreadTree t){
	if(t->rtag != 1){
		return FirstNode(t->rchild); //没有直接后继，就找右子树中最靠左的结点 
	};
	return t->rchild;
} 

//遍历中序线索二叉树
void printInThreadTree(ThreadTree t){
	for(ThreadTree p=FirstNode(t);p!=NULL;p=NextNode(t)){
		printf("%d",p->data);
	}
} 
////对二叉树的前序线索化
//递归子函数
void PreThreadBiTree(ThreadTree &t,ThreadTree &p){
	if(t){
		if(t->lchild==NULL){
			t->lchild = p;
			t->ltag = 1;
		}
		if(t->rchild==NULL){
			t->rchild = p;
			t->rtag = 1;
		}
		p = t;
		//一定得有判断条件，防止转圈
		//（例如去掉条件，t->ltag是1时没有判断条件，前驱结点与本结点构成一个环，不停循环) 
		if(t->ltag == 0)PreThreadBiTree(t->lchild,p);
		if(t->rtag == 0)PreThreadBiTree(t->rchild,p);
	}
}
//主函数
void PreThread(ThreadTree t){
	ThreadTree p = NULL;
	if(t){
		PreThreadBiTree(t,p);
		p->rchild = NULL;
		p->rtag = 1;
	}
} 
////前序结果二叉树的遍历
//求前序结点二叉树的某个结点的前驱
ThreadTree PrePNode(ThreadTree t){
	if(t->ltag==1){	
		return t->lchild;
	}else{
		//分三种情况,需要用到父结点
		//如果t是父结点的左结点，根据NLR，其前驱为其父节点 
		if(t->parent->lchild==t){
			return t->parent;
		//如果t是父节点的右结点，且父节点无左子结点，则前驱依然是父结点 
		}else if(t->parent->ltag == 1){
			return t->parent;
		//前面两个条件都失效，证明该结点为右结点且父结点有左孩子，前驱应该是左孩子的最右下结点 
		//并且该节点一定是一个叶子节点，所以左右线索都应为1 
		}else{
			ThreadTree p = t->parent->lchild;
			//遍历（难点）
			while(p->rtag != 1 || p->ltag != 1){
	   		//向右不停查找，直到节点无右子树 
	   		    while(p->rtag == 0)p = p->rchild;
	   		    //找到无右子树的节点，检查是否有左子树 
	   		    if(p->ltag == 0)
	   		    //若有左子树，向左走一步，继续向右走，直到找到最右下节点 
	   		    p = p->lchild;
		    } 
			return p;
		}
		
	}
} 
//求前序结点二叉树的某个结点的后继
ThreadTree PostPNode(ThreadTree t){
	if(t->rtag==1){
		//有后继线索，直接返回 
		return t->rchild; 
	}else{
		//该节点有右孩子，分两种情况讨论 
		//该节点有左孩子，返回左孩子 
		if(t->rtag==0)return t->lchild;
		//否则该节点无左孩子，返回右孩子为其后继 
		else return t->rchild; 
	}
}
//遍历前序结点二叉树 
void PrintPTTree(ThreadTree t){
	for(ThreadTree p = t;p!=NULL;p = PostPNode(p)){
		printf("%d",p->data);
	}
}

////对二叉树的后序线索化
//递归子函数
ThreadTree PostThreadBiTree(ThreadTree &t,ThreadTree &p){
	 if(t){
	 	if(t->ltag==0)
	 	PostThreadBiTree(t->lchild,p);
	 	if(t->rtag==0)
		PostThreadBiTree(t->rchild,p);
		p = t;
		if(t->lchild==NULL){
			t->lchild = p;
			t->ltag = 1;
		} 
		if(t->rchild == NULL){
			t->rchild = p;
			t->rtag = 1;
		}
	 }
}
//主函数
void PostThread(ThreadTree t){
	ThreadTree p = NULL;
	if(t){
		PostThreadBiTree(t,p);
		p->rchild = NULL;
		p->rtag = 1;
	}
} 
////前序结果二叉树的遍历
//求前序结点二叉树的某个结点的前驱
ThreadTree PrePostNode(ThreadTree t){
	if(t->ltag == 1){
		//有直接后继 
		return t->lchild;
	}else{
		//有左孩子，先看有没有右孩子 
		if(t->rtag==0)return t->rchild;
		else return t->lchild;
	}
}

//求前序结点二叉树的某个结点的后继
ThreadTree PostPostNode(ThreadTree t){
	if(t->rtag == 1){
		//有直接后继 
		return t->rchild;
	}else{
		//父节点的右孩子是否为本节点，是的话直接返回父节点 
		if(t->parent->rchild == t){
			return t->parent;
		//父节点无右孩子，本节点是左孩子，是的话也直接返回父节点
		}else if(t->parent->rtag == 1){
			return t->parent;
		}else{
		//后继节点应为父节点右孩子的最左下节点，且应为叶节点 
			ThreadTree p = t->parent->rchild;
			while(p->ltag == 0 && p->rtag == 0){
				while(p->ltag == 0){
					p = p->lchild;
				}
				//是否还有右子节点，有的话则不为叶子节点，向右走一下 
				if(p->rtag == 0){
					p = p->rchild;
				}
			} 
			return p;
		}
	}
} 

//后序线索二叉树的打印
void printPost(ThreadTree t){
	int stack[MAXSIZE],top=-1;
	//由于后续二叉树的特性LRN，打印出来应该是后序节点排列的倒序
	//利用栈后进先出的特点，我们选用一个栈来存储数据 
	for(ThreadTree p = t;t!=NULL;t=PrePostNode(t)){
		stack[++top] = p->data;
	}
	while(top>=0){
		printf("%d",stack[top--]); 
	}
}