thtree.cpp

数据结构经典算法的C语言实现 计算机专业数据结构课程实验

#include <iostream.h>
#include <string>

typedef char elemtype;

enum Boolean{FALSE,TRUE};
struct node {
	elemtype data;
	node *lchild;
	node *rchild;
	Boolean ltag, rtag;
};  //结点型

typedef struct node* THTREE;

//全局量
node *p = NULL;
node *pre = NULL;

//递归建立二元树
void CreatBtree(THTREE &T) {
	char ch;
	
	cin>>ch;
	if (ch == '#')
		T = NULL;
	else {
		T = new node;
		if (T == NULL)
			exit(1);
		T->data = ch;
		T->ltag = TRUE;
		T->rtag = TRUE;
		CreatBtree(T->lchild);
		CreatBtree(T->rchild);
	}
}
//中序线索化二元树
void InorderTh(THTREE p) {
	if(p != NULL) {
		InorderTh(p->lchild);
        if(p->lchild == NULL) {
			p->lchild = pre;
			p->ltag = FALSE;
		}
		if(pre != NULL && pre->rchild == NULL) {
			pre->rchild = p;
			pre->rtag = FALSE;
		}
		pre = p;
		InorderTh(p->rchild);
	}
}
//后继
THTREE Innext(THTREE a) {
	THTREE Q;
	Q = a->rchild;
	if(a->rtag == 1) {
		while(Q->ltag == 1)
			Q = Q->lchild;
	}
	return Q;
}
//中序遍历线索二元树
void THINORDER(THTREE T) {
	THTREE temp;
	char ch;
	temp = T;
	do {
		temp = Innext(temp);
		if(temp != T) {
			ch = temp->data;
		    cout<<ch;
		}
	} while(temp != T);

}
//符号化输出二元树
void DisplayBtree(THTREE T) {
    if(T != NULL) {
		cout<<T->data;
		if(T->lchild != NULL || T->rchild != NULL) {
			cout<<"(";
		    DisplayBtree(T->lchild);   
			if(T->rchild != NULL)
				cout<<",";
	        DisplayBtree(T->rchild);  
				cout<<")";
		}
	}
}

void main() {   
	THTREE T, head;
	char yn;
	
label:
	cout<<"请按先序序列输入二元树，#表示空：";
	
	CreatBtree(p);
	T = p;
	
	if(T != NULL) {
		cout<<"此二元树为："<<endl;
		DisplayBtree(T);
		cout<<endl;
		InorderTh(p);           //线索化二元树
	}
	else {
		cout<<"此二元树为空！"<<endl;
		goto label;
	}
	
	head = new node;      //增加头结点
	if(T == NULL) {
		head->lchild = head;
		head->rchild = head;
		head->rtag = TRUE;
		head->ltag = FALSE;
	}	
	if(T != NULL ) {
		head->lchild = T;
		head->rchild = head;
		head->rtag = TRUE;
		head->ltag = TRUE;
	}
	p = T;
	while(p->lchild != NULL)
		p = p->lchild;
	p->lchild = head;
	p->ltag = FALSE;
	p = T;
	while(p->rchild != NULL)
		p = p->rchild;
	p->rchild = head;
	p->rtag = FALSE;
	
	cout<<"中序遍历线索化二元树的结果为："<<endl;
	THINORDER(head);
	cout<<endl;

	cout<<"是否继续？继续使用请选y，退出请选n：";
	cin>>yn;
	if(yn == 'y' || yn == 'Y')
		goto label;
}