`
暮云凌轩
  • 浏览: 9009 次
  • 性别: Icon_minigender_2
  • 来自: 上海
社区版块
存档分类
最新评论

二叉树遍历及线索化

 
阅读更多
#include <stdio.h>
#include <stdlib.h>
#define STACK_INCREMENT 10
#define STACK_INIT_SIZE 10
enum Status{OK,ERROR}; 
typedef char Element;
typedef struct Node{
	Element data;
	struct Node* left;
	struct Node* right;
	int Ltag;
	int Rtag;
}BitNode,*BitTree; 

typedef BitTree SElemType; 

struct SqStack{
	SElemType *top;
	SElemType *base;
	int stacksize; 
};
 
BitTree pre;

void InitStack(SqStack &S)
 { // 构造一个空栈S
//   if(!(S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType))))
//     exit(OVERFLOW); // 存储分配失败
   S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
   S.top=S.base;
   S.stacksize=STACK_INIT_SIZE;
 }
Status GetTop(SqStack S,SElemType &e)
 { // 若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR
   if(S.top>S.base)
   {
     e=*(S.top-1);
     return OK;
   }
   else
     return ERROR;
 }
void Push(SqStack &S,SElemType e)
 { // 插入元素e为新的栈顶元素
   if(S.top-S.base>=S.stacksize) // 栈满,追加存储空间
   {
     S.base=(SElemType *)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType));
//     if(!S.base)
//       exit(OVERFLOW); // 存储分配失败
     S.top=S.base+S.stacksize;
     S.stacksize+=STACK_INCREMENT;
   }
   *(S.top)++=e;
 }

 Status Pop(SqStack &S,SElemType &e)
 { // 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR
   if(S.top==S.base)
     return ERROR;
   e=*--S.top;
   return OK;
 }

bool IsEmpty(SqStack S){
	if(S.top==S.base)
		return true;
	else return false;	
}

void Visit(BitTree &T){
	printf(" %c", T->data);
}

void CreateTree(BitTree &T){//先序生成树 
	Element ch;
	 scanf("%c",&ch);  
		if(ch=='#')
			T = NULL;
		else{
			T = (BitTree)malloc(sizeof(BitNode));  
//			if(!T)  
//            	exit(OVERFLOW);  
        	T->data = ch;  
        	T->Ltag = 0;  
        	T->Rtag = 0;  
        	CreateTree(T->left);  
        	CreateTree(T->right);  
		} 	

}
 
void InOrder_Query(BitTree &T){
	if(T!=NULL){
		InOrder_Query(T->left);
		printf("%c",T->data); 
		InOrder_Query(T->right);
	}
}

void InOrder_Query2(BitTree &T){
	SqStack s;
	InitStack(s);
	if(!IsEmpty(s) || T!=NULL){
		if(T!=NULL){
			Push(s,T);
			T = T->left;
		}else{
			Pop(s,T);
			Visit(T);
			T = T->right;
		}
	}
}



void PreOrder_Query(BitTree &T){
	if(T!=NULL){
		printf(" %c",T->data); 
		InOrder_Query(T->left);
		InOrder_Query(T->right);
	}
}

void PreOrder_Query2(BitTree &T){
	SqStack s;
	InitStack(s);
	while(!IsEmpty(s) || T!=NULL){
		if(T!=NULL){
			printf("%c",T->data);
			Push(s,T);
			T = T->left;
		}else{
			Pop(s,T);
			T = T->right;
		}
	}
	
}
void PostOrder_Query(BitTree &T){
	if(T!=NULL){
		PostOrder_Query(T->left);
		PostOrder_Query(T->right);
		printf(" %c",T->data); 
	}
}

void PostOrder_Query2(BitTree &T){
	BitTree r;
	SqStack s;
	InitStack(s);
	while(!IsEmpty(s) || T!=NULL){
		if(T!=NULL){
			Push(s,T);
			T = T->left;
		}else{
			GetTop(s,T);
			if(NULL!=T->right && T->right!=r){
				T = T->right;
			}else{
				Pop(s,T);
				r = T;
				Visit(T);
				T = NULL;
			}
		}
	}
}


void In_threading(BitTree &T){
	if(T!=NULL){
		In_threading(T->left);
		if(T->left==NULL){
			T->left = pre;
			T->Ltag = 1;
		}
		if(pre->right==NULL){
			pre->right=T;
			pre->Rtag = 1;
		}
		pre = T;
		In_threading(T->right);
	}
}



void InOrder_thr(BitTree &H,BitTree &T){
	H = (BitTree)malloc(sizeof(BitNode));  
	H->data = 0;
	H->Ltag = 0;
	H->Rtag = 1;
	H->right = H;
	if(T==NULL){
		H->left = H;
	}else{
		H->left = T;
		pre = H;
		In_threading(T);
		pre->right = H;
		pre->Rtag = 1;
		H->right = pre;
	}
}

void InOrder_thr_query(BitTree &T){
	
    BitTree	p = T->left;
	while(p!=T){
		while(0==p->Ltag){
			p = p->left;
		}
		printf(" %c",p->data);
		while(1==p->Rtag && p->right!=T){
			p = p->right;
			printf(" %c",p->data);
		}
		p = p->right;
	}	
}


void Pre_threading(BitTree &T){
	
	if(T!=NULL){
		if(T->left==NULL){
			T->left = pre;
			T->Ltag = 1;
		}
		if(pre->right==NULL){
			pre->right=T;
			pre->Rtag = 1;
		}
		pre = T;
		if(0 == T->Ltag) {
				Pre_threading(T->left);
		}
		if(0 == T->Rtag){
			Pre_threading(T->right);
		}	
	}
}

void PreOrder_thr(BitTree &H,BitTree &T){
	H = (BitTree)malloc(sizeof(BitNode));  
	H->data = 0;
	H->Ltag = 0;
	H->Rtag = 1;
	H->right = H;
	if(T==NULL){
		H->left = H;
	}else{
		H->left = T;
		pre = H;
		Pre_threading(T);
		pre->right = H;
		pre->Rtag = 1;
		H->right = pre;
	}
}

void PreOrder_thr_query(BitTree &T){
	
    BitTree	p = T->left;
	while(p!=T){
		printf(" %c",p->data);	
		if(0==p->Ltag){
			p = p->left;		
		}
		else{
			p = p->right;
		}
	}	
}

void Post_threading(BitTree &T){
	if(T!=NULL){
		Post_threading(T->left);
		Post_threading(T->right);
		if(T->left==NULL){
			T->left = pre;
			T->Ltag = 1;
		}
		if(pre->right==NULL){
			pre->right=T; 
			pre->Rtag = 1;
		}
		pre = T;
	}
}



void PostOrder_thr(BitTree &H,BitTree &T){
	H = (BitTree)malloc(sizeof(BitNode));  
	H->data = 0;
	H->Ltag = 0;
	H->Rtag = 1;
	H->right = H;
	if(T==NULL){
		H->left = H;
	}else{
		H->left = T;
		pre = H;
		Post_threading(T);
		pre->right = H;
		pre->Rtag = 1;
		H->right = pre;
	}
}

BitTree Parent(BitTree &p,BitTree &T){
//根右左
	BitTree temp = T;
	if(T->left==p)
		return T;
	else{
		temp = temp->left;
		while(temp->left != p && temp->right != p){
			 if(temp->Rtag == 0)  
                temp = temp->right;  
            else  
                temp = temp->left;
		}
	}	
	 return temp;  
}

void PostOrder_thr_query(BitTree &T){
    BitTree	p = T->left;
    BitTree	par = NULL;
	while(true){
		while(0==p->Ltag)
			p = p->left;
		if(0==p->Rtag)
			p = p->right;
		else 
			break;		
	}
	while(p!=T){
		printf(" %c",p->data);
		par = Parent(p,T);
		if(par == T){//结束
			p = T;
		}else if(1==par->Rtag || p==par->right){//无右子树
			p = par;
		}else{
			while(0==par->Rtag){//遍历右子树
				par = par->right;
				while(0==par->Ltag){
					par = par->left;
				}
			}
		p = par;
		}
	}	
}


int main(int argc, char** argv) {
	BitTree H,T;  
	printf("请输入前序二叉树的数据,例('ABDH##I##EJ###CF##G##')\n");  
	CreateTree(T);
//	printf("二叉树的数据,中序查询结果:\n");  
//	InOrder_Query(T); 
//	InOrder_Query(T); 
//	printf("中序线索化二叉树\n");  
//	InOrder_thr(H,T);
//	printf("遍历中序线索化二叉树\n");  	
//	InOrder_thr_query(H);

//	printf("二叉树的数据,前序查询结果:\n");  
//	PreOrder_Query(T); 
//	PreOrder_Query2(T);
//	printf("前序线索化二叉树\n");  
//	PreOrder_thr(H,T);
//	printf("遍历前序线索化二叉树\n");  	
//	PreOrder_thr_query(H);

//	printf("二叉树的数据,后序查询结果:\n");  
//	PostOrder_Query(T);
//	printf("二叉树的数据,后序查询(非递归)结果:\n");  
//	PostOrder_Query2(T); 
//	printf("后序线索化二叉树\n");  
//	PostOrder_thr(H,T);
//	printf("遍历后序线索化二叉树\n");  	
//	PostOrder_thr_query(H);
	return 0;
}
 
 
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics