btree.cpp

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

#include <iostream>
#define MAX 100

using namespace std;

struct node {
	struct node *lchild;
	struct node *rchild;
	char data;
};  //结点型

typedef struct node* BTREE;

//递归算法建立二元树
void CreateBtree1(BTREE &T) {
	char ch;

	cin>>ch;
	if(ch == '#') T = NULL;
	else {
		if(!(T = new node)) exit(1);
		else {
			T->data = ch;
			CreateBtree1(T->lchild);
			CreateBtree1(T->rchild);
		}
	}
}

//非递归算法建立二元树
struct node *s[MAX];  //辅助指针数组，存放二元树结点指针
BTREE CreateBtree2(void) {
	int i, j;
	char ch;
	struct node *bt, *p;  //*bt为根，p用于建立结点
	bt = NULL;
	
	cin>>i>>ch;
	while(i != 0 && ch != '0') {
		p = new node;
		p->data = ch;
		p->lchild = NULL;
		p->rchild = NULL;
		s[i] = p;
		
		if(i == 1) bt = p;
		else {
			j = i / 2;  //父结点的编号
			if(i % 2 == 0) s[j]->lchild = p;  //i是j的左儿子
			else           s[j]->rchild = p;  //i是j的右儿子
		}
		cin>>i>>ch;
	}

	return bt;
}

//递归先序遍历
void Preorder(BTREE T) {
	 if(T != NULL) {
		 cout<<T->data;
		 Preorder(T->lchild);                                
		 Preorder(T->rchild);                              
	 }
}

//递归中序遍历
void Inorder(BTREE T) {
	 if(T != NULL) {
		 Inorder(T->lchild);
		 cout<<T->data;
		 Inorder(T->rchild);
	 } 
}

//递归后序遍历
void Postorder(BTREE T) {
	if(T != NULL) {
		Postorder(T->lchild);
		Postorder(T->rchild);
		cout<<T->data;
	} 
}

//非递归先序遍历
void PreOrder(BTREE T) {
	BTREE stack[MAX], p;
	int top = -1;
	
	if(T != NULL) {
		 top++;
		 stack[top] = T;                    //根节点进栈
		 
		 while(top > -1) {                  //栈不为空时循环
			 p = stack[top];                //退栈并访问该节点
			 top--;
			 cout<<p->data;
			 if(p->rchild != NULL) {                //右儿子进栈
				 top++;
				 stack[top] = p->rchild;
			 }
			 if(p->lchild != NULL) {                //左儿子进栈
				 top++;
				 stack[top] = p->lchild;
			 }
		 }                          
	 }
}

//非递归中序遍历
void InOrder(BTREE T) {
	BTREE stack[MAX], p;
	int top = -1;
	
	p = T;
	while(p != NULL || top != -1) {
		if(p != NULL) {
			top++;
			stack[top] = p;
			p = p->lchild;
		}                              //根节点进栈，遍历左子树
		else {                         //根节点退栈，访问根节点，遍历右子树
			p = stack[top];
			top--;
			cout<<p->data;
			p = p->rchild;
		}
	}
}

//非递归后序遍历
void PostOrder(BTREE T) {
	BTREE stack[MAX], p;
	int flag, top = -1;

	do {
		while(T != NULL) {
			top++;
			stack[top] = T;
			T = T->lchild;
		}                                //所有左节点进栈
		p = NULL;                        //p总是指向当前节点的前一个已经访问过的节点
		flag = 1;                        //flag为1表示当前节点已经访问过了
		while(top != -1 && flag) {
			T = stack[top];
			if(T->rchild==p) {           //右子树不存在或者已经被访问过时
				cout<<T->data;
				top--;
				p = T;                   //调整p指针
			}
			else {
				T = T->rchild;
				flag = 0;                //调整访问标志
			}
		}
	} while(top != -1);
}

//输出二元树
void DisplayTree(BTREE T) {
	if(T != NULL) {
		cout<<T->data;
        if(T->lchild != NULL || T->rchild != NULL) {
			cout<<"(";
			DisplayTree(T->lchild);
			if(T->rchild != NULL) cout<<",";
			DisplayTree(T->rchild);
			cout<<")";
		}
	}
}

void main() {
	BTREE T = NULL;
	char yn = 'y';
	int i, j;

	while (yn == 'y' || yn == 'Y') {
		cout<<"欢迎使用本程序！您可以进行建立二元树，递归与非递归先序、中序、后序遍历二元树，输出二元树的操作。\n";
		cout<<"请选择：１、递归建立二元树　　２、非递归建立二元树：";
		cin>>i;
		
		switch(i) {
		case 1:
			cout<<"请按先序序列输入二元树，#表示空：";
			CreateBtree1(T);
			break;
		case 2:
			cout<<"请按完全二元树层次输入二元树，0 0表示结束：";
			T = CreateBtree2();
			break;
		default:
			break;
		}

		if (T == NULL) cout<<"二元树为空！\n";
		else {
			cout<<"符号化输出此二元树为：";
			DisplayTree(T);
			cout<<"\n";
	
			cout<<"请选择：１、递归先序遍历　　２、递归中序遍历　　３、递归后序遍历\n";
			cout<<"　　　　４、非递归先序遍历　５、非递归中序遍历　６、非递归后序遍历\n";
			cin>>j;
		
			switch(j) {
			case 1:
				cout<<"递归先序遍历二元树：";
				Preorder(T);
				cout<<"\n";
				break;
			case 2:
				cout<<"递归中序遍历二元树：";
				Inorder(T);
				cout<<"\n";
				break;
			case 3:
				cout<<"递归后序遍历二元树：";
				Postorder(T);
				cout<<"\n";
				break;
			case 4:
				cout<<"非递归先序遍历二元树：";
				PreOrder(T);
				cout<<"\n";
				break;
			case 5:
				cout<<"非递归中序遍历二元树：";
				InOrder(T);
				cout<<"\n";
				break;
			case 6:
				cout<<"非递归后序遍历二元树：";
				PostOrder(T);
				cout<<"\n";
				break;
			default:
				break;
			}
		}
		
		getchar();
		cout<<"是否继续使用本程序？(Y/N):";
		cin>>yn;
		cout<<"\n";
	}
}