急急急求一道数据结构课程设计题

跪求：设计树结构的相关函数库，以便在程序设计中调用。要求：（1）包括树的存储结构及各种基本函数以及常用函数；（2）给出1-2个例子，通过调用自己的库函数来实现问题的求解。

6 个解决方案

#1

小弟弟，你怎么不做啊？

#2

#include <iostream>
using namespace std;
typedef char ElemType;

struct BTreeNode {
	ElemType data;
	BTreeNode *left;
	BTreeNode *right;
};

//二叉树的建立
void Create(BTreeNode* &BT)
{
	ElemType ch;
	cin.get(ch);
	if (ch == ' ')
		BT = NULL;
	else
	{
		BT = new BTreeNode;
		BT->data = ch;		
		Create(BT->left);
		Create(BT->right);
	}
}

//前序遍历算法
void PreOrder(BTreeNode *BT)
{
	if (BT != NULL)
	{
		cout<< BT->data<< ' ';
		PreOrder(BT->left);
		PreOrder(BT->right);
	}
}

//中序遍历
void InOrder(BTreeNode *BT)
{
	if (BT != NULL)
	{
		InOrder(BT->left);
		cout<< BT->data<< ' ';
		InOrder(BT->right);
	}
}

//后序遍历
void PostOrder(BTreeNode *BT)
{
	if (BT != NULL)
	{
		PostOrder(BT->left);
		PostOrder(BT->right);
		cout<< BT->data<< ' ';
	}
}
//前序非递归遍历
void Previous(BTreeNode *BT)
{
	//建立栈
	const int MaxSize = 20;
	BTreeNode* stack[MaxSize];
	int top = -1;
	if (BT != NULL)
	{
		BTreeNode *p = BT;
		do{
			//访问根节点，并入栈，连续访问左子树
			while (p != NULL)
			{
				cout<< p->data<< ' ';
				++top;
				stack[top] = p;
				p = p->left;
			}
			//回退，出栈
			if (top != -1)
			{
				p = stack[top--];
				p = p->right;
			}
		}while(top != -1 || p != NULL);
	}
}

//中序非递归遍历
void Middle(BTreeNode *BT)
{
	//定义栈
	const int MaxSize = 20;
	BTreeNode* stack[MaxSize];
	int top = -1;
	if (BT == NULL)
		return;
	BTreeNode *p = BT;
	while (p != NULL || top != -1)
	{
		//遍历左子树，并将跟节点入栈
		while (p != NULL)
		{
			stack[++top] = p;
			p = p->left;
		}
		//遍历到没有左子树为空的节点，回退，出栈
		if (top != -1)
		{
			p = stack[top--];
			cout<< p->data<< ' ';
			p = p->right;
		}
	}
}

//后序非递归遍历
void Post(BTreeNode *BT)
{
	const int MaxSize = 20;
	BTreeNode* stack[MaxSize];
	int top = -1;
	int s[MaxSize];     //可以看做与指针栈相对应的一个栈，用来回退时候是否输出当前根节点的
	if (BT == NULL)
		return;
	BTreeNode *p = BT;
	while (p != NULL || top != -1)
	{
		//遍历左子树，入栈
		while (p != NULL)
		{
			stack[++top] = p;
			s[top] = 1;  //1表示当前节点并没有被输出过，稍后的2表示当前节点输出。用来判断是否输出的
			p = p->left;
		}
		//回退，出栈，访问右子树
		if (top != -1)
		{
			p = stack[top--];
			int k = s[top+1];
			//将p节点从新入栈，因其并未被输出，访问完右节点之后还要输出，要回退，并且设标示为2，回退时输出
			if (k == 1){
				stack[++top] = p;
				s[top] = 2;
				p = p->right;
			}
			else{
				cout<< p->data<< ' ';
				p = NULL;
			}
		}
	}
}

//二叉树按层遍历算法
void LevelOrder(BTreeNode *BT)
{
	const int MaxSize = 10;
	BTreeNode* q[MaxSize];
	int front = 0, rear = 0;
	if (BT == NULL)
		return;
	BTreeNode *p = BT;
	//将根节点入栈
	if (BT != NULL)
	{
		rear = (rear + 1)%MaxSize;
		q[rear] = BT;
	}
	while (front != rear)
	{
		front = (front+1)%MaxSize;
		p = q[front];
		//输出其节点数据
		cout<< p->data<< ' ';
		//如有左子树，左子树进队列
		if (p->left != NULL)
		{
			rear = (rear+1)%MaxSize;
			q[rear] = p->left;
		}
		//如存在右子树，右子树进队列
		if (p->right != NULL)
		{
			rear = (rear+1)%MaxSize;
			q[rear] = p->right;
		}
	}
}

//广义表形式建立二叉树
void CreateBTree(BTreeNode* &BT, char *a)
{
	const int MaxSize = 10;
	BTreeNode *s[MaxSize];
	int top = -1;
	BT = NULL;
	BTreeNode *p;
	int k;   //标示来处理左右子树，1为左子树，2为右子树
	int i = 0;
	while (a[i])
	{
		switch (a[i])
		{
			case ' ':
				break;
			case '(':   //遇见左括号，入栈
				s[++top] = p;
				k = 1;
				break;
			case ')':  //出栈
				top--;
				break;
			case ',':  //遇见， 处理右子树
				k = 2;
				break;
			default:
				p = new BTreeNode;
				p->data = a[i];
				p->left = p->right = NULL;
				//作为根节点插入
				if (BT == NULL)
					BT = p;
				else
				{
					if (k == 1)
						s[top]->left = p; //作为左节点插入
					else
						s[top]->right = p;  //作为右节点插入
				}
		}
		i++;
	}
}
//求二叉树的深度
int DepthBTree(BTreeNode *BT)
{
	if (BT == NULL)
		return 0;
	else
	{
		int dep1 = DepthBTree(BT->left);
		int dep2 = DepthBTree(BT->right);
		if (dep1 > dep2)
			return dep1+1;
		else
			return dep2+1;
	}
}

//查找x，若存在由x带回，否则返回假
bool FindBTree(BTreeNode *BT, ElemType &x)
{
	if (BT == NULL)
		return false;
	if (BT->data == x)
	{
		x = BT->data;
		return true;
	}
	else
	{
		if (FindBTree(BT->left, x)) 
			return true;
		if (FindBTree(BT->right, x))
			return true;
		return false;
	}
}
//输出二叉树
void PrintBTree(BTreeNode *BT)
{
	if (BT != NULL)
	{
		cout<< BT->data;
		if (BT->left != NULL || BT->right != NULL)
		{
			cout<< '(';
			PrintBTree(BT->left);
			if (BT->right != NULL)
				cout<< ',';
			PrintBTree(BT->right);
			cout<< ')';
		}
	}
}

void ClearBTree(BTreeNode* &BT)
{
	if (BT != NULL)
	{
		ClearBTree(BT->left);
		ClearBTree(BT->right);
		delete BT;
		BT = NULL;
	}
}

int main()
{
	/*BTreeNode *BT;
	Create(BT);
	PreOrder(BT);
	cout<< endl;
	Previous(BT);
	cout<< endl;
	InOrder(BT);
	cout<< endl;
	Middle(BT);
	cout<< endl;
	PostOrder(BT);
	cout<< endl;
	Post(BT);
	cout<< endl;
	LevelOrder(BT);
	cout<< endl;*/
	char *s = "A(B(C),D(E(F,G),H(,I)))";
	BTreeNode *HL;
	CreateBTree(HL, s);
	PreOrder(HL);
	cout<< endl;
	int i = DepthBTree(HL);
	PrintBTree(HL);
	cout<< endl;
	return 0;
}

#3

嘿嘿，我数据结构学得不太好

#4

多谢2楼的答案，不过和我给出的题目有些出入，但是基本上帮我解决问题啦

#5

 还有答案吗？急用？谢谢发过来

#6

看到了，不用发了