adt_bithrtree.h

out< "please input the number of the nodes"<<endl cin>>nodesNum cout<<"pl

//中序线索化二叉树的抽象数据类型。
#include <iostream.h>
#include<malloc.h>
#include<stdlib.h>
#define OK 1
#define YES 1
#define FALSE 0
#define ERROR 0
#define OVERFLOW -2
typedef char TElemType; 
typedef enum PointerTag{Link,Thread};//Link为指针，Thread为线索。
typedef struct BiThrNode{
	TElemType data;                   //关键字
	struct BiThrNode *lchild,*rchild;//左右孩子指针
	PointerTag LTag,RTag;            //左右标志
}BiThrNode,* BiThrTree;

//----------------------------------------基本操作的算法实现---------------------------

//--按照先序序列构造未线索化的以二叉链表为存储结构的二叉树T----
short CreateBiThrTree(BiThrTree &T){
//按照先序次序输入的二叉树中结点的值,#表示空树。
//按照其他遍例方式行不通或则很复杂。
	TElemType c;
	cout<<"请输入按照先序次序输入的二叉树的当前结点值"<<endl;
	cin>>c;
	if(c=='#') 
		T=NULL;
	else{
		T=(BiThrNode *)malloc(sizeof(BiThrNode));
		if(!T) return ERROR;
		T->data=c;              
		T->LTag=T->RTag=Link;     //生成根节点
		CreateBiThrTree(T->lchild);
		CreateBiThrTree(T->rchild);
	}//else
	return OK;
}//CreateBiThrTree

//--对T进行中序线索化-------
short InOrderThreading(BiThrTree & thrt,BiThrTree T){
    void InThreading(BiThrTree p,BiThrNode * & pre1);//子函数声明
	BiThrNode *pre; 
	if(!(thrt=(BiThrTree )malloc(sizeof(BiThrNode)))) return ERROR;
	thrt->LTag=Link;thrt->RTag=Thread;  //建立头结点
	thrt->rchild=thrt;  //右指针回指
    if(!T) thrt->lchild=thrt; //如果树空，则左指针回指
	else{
		  thrt->lchild=T;
		  pre=thrt;
		  InThreading(T,pre); //中序遍历进行中序线索化
		  pre->RTag=Thread;pre->rchild=thrt;
		  thrt->rchild=pre;
	  }//else
	return OK;
}//InOrderThreading

//InOrderThreading的子函数
void InThreading(BiThrTree p,BiThrNode * & pre1){
	if(p){ 
		  InThreading(p->lchild,pre1);
		  if(!p->lchild){p->LTag=Thread;p->lchild=pre1;}
		  if(!pre1->rchild){pre1->RTag=Thread;pre1->rchild=p;}
		  pre1=p;
		  InThreading(p->rchild,pre1);
		  }//if
}//InThreading

//---在中序线索二叉树上寻找一个结点的前驱------
BiThrNode * PreNode(BiThrNode * p){
	if(!p) return ERROR;
	else{
		if(p->LTag==Thread) return p->lchild;//若p的左指针是线索，则为所求。
		else{                                //若p存在左子树。
			p=p->lchild;
			while(p->RTag==Link) p=p->rchild; //则所求的前驱为p的左子树的最右结点。
			return p;
		}//else
	}//else
}//PreNode

//--在中序线索二叉树上寻找一个结点的后继------
BiThrNode * PostNode(BiThrNode *p){
     if(!p) return ERROR;
	 else{
		  if(p->RTag==Thread) return p->rchild;
		  else{
			  p=p->rchild;
			  while(p->LTag==Link) p=p->lchild;
			  return p;
		  }//else
	 }//else
}//PostNode

//----中序遍历一棵中序线索二叉树-----
void InOrderBiThrTree(BiThrTree thrt,void(* visit)(TElemType e)){
//中序遍历带头结点的中序线索二叉树thrt的非递归算法，对每个数据元素调用函数visit
  BiThrTree p=thrt->lchild;
	  while(p!=thrt){
		  while(p->LTag==Link)
			  p=p->lchild;
          (* visit)(p->data);
          while(p->RTag==Thread && p->rchild!=thrt){
			  p=p->rchild;
			  (* visit)(p->data);
		  }//while
          p=p->rchild;
	  }//while
}//InOrderBiThrTree

//----前序遍历一棵中序线索二叉树，不用递归和栈----
void PreOrderBiThrTree(BiThrTree thrt,void(* visit)(TElemType e)){
//前序遍历带头结点的中序线索二叉树thrt的非递归算法，对每个数据元素调用函数visit
    BiThrTree p=thrt->lchild;
	while(p!=thrt){
		while(p->LTag==Link){
			(* visit)(p->data);
			p=p->lchild;
		}//while
		(* visit)(p->data);
        while(p->RTag==Thread && p->rchild!=thrt)
			p=p->rchild;
	    p=p->rchild;
	}//while
}//PreOrderBiThrTree

//--判断一棵已经中序线索化的二叉树是否为空
short BiThrTreeEmpty(BiThrTree thrt){
	if(thrt->lchild==thrt) return YES;//空
	else  return ERROR;//不空
}//BiThrTreeEmpty

//--带头结点的中序线索化二叉树的深度---
short BiThrTreeDepth(BiThrTree thrt,int k){
      static int max=0;//max表示当前的最大层数
	  if(thrt->lchild==thrt) return 0;
	  else{
		  if(thrt->LTag==Link) BiThrTreeDepth(thrt->lchild,k+1);
	      if(thrt->RTag==Link) BiThrTreeDepth(thrt->rchild,k+1);
	      if(thrt->LTag==Thread && thrt->RTag==Thread){
			  if(k>max) max=k;
		  }//if
	  }//else
	  return max;//递归函数里用return，当整个函数被外界调用时返回的是整个主调函数（它调用自己）的return的值
}