《数据结构》第五章树和二叉树 树的操作示例代码1

为了大家熟悉树的操作，现参照课本给出一个树的存储操作示例。

将下面的树存入计算机，并前序和后序输出各个结点数据。为了方便，本树输入结点数据为整数。

#include <iostream>
using namespace std;
const int Max = 100;

//---------------------------------------//
//-------     定义结点类型   ------------//
//---------------------------------------//
struct TNode
{
  int data;
  TNode *firstchild,*rightsib;
};

//---------------------------------------//
//-------      声明树类tree  ------------//
//---------------------------------------//
class Tree
{
public:
	Tree( );
	~Tree( ){Release(root);}          //析构函数，释放各结点的存储空间
	void PreOrder( ){PreOrder(root);}
	void PostOrder( ){PostOrder(root);}
private:
	TNode *root;
	void PreOrder(TNode *bt);
	void PostOrder(TNode *bt);
	void Release(TNode *bt);
};

//---------------------------------------//
//-------  树类tree的函数定义 -----------//
//---------------------------------------//
Tree::Tree( )
{
	TNode *Q[Max] = {NULL};           //初始化队列 
	int mom = 0,child = 0;
	int front = -1,rear = -1;
	TNode *p = NULL,*q = NULL;
	cout<<"输入根的数据：";
	cin>>mom;
	p = new TNode; p->data =mom;         //建立根结点
	p->firstchild = p->rightsib = NULL;  //根结点左孩和后兄弟指针为空
	root = p;                            //root指向根
	Q[++rear] = p;                        //根指针入队 
    cout<<"输入每一个双亲和子女对，以空格分隔，输入0表示结束：";
	cin>>mom;                              //输入双亲子女对
	cin>>child;
 
	while (mom != 0 || child != 0)       
	{	p = new TNode; p->data = child;     //建立子女结点
		p->firstchild = p->rightsib = NULL;
		Q[++rear] = p;                      //子女指针入队
		while (front < rear)
		{
			q = Q[front + 1];               //取队头指针元素
			if (q->data != mom)             //队头数据不是输入的数据对的双亲
				front++;                    //队头指针后移，出队
			else 
			{
				if (q->firstchild == NULL)
					q->firstchild = p;          //接上第一个孩子
				else
				{ while (q->rightsib != NULL)     //接右孩子
					q = q->rightsib;
					q->rightsib = p;
				}
				break;
			}
		}
		cout<<"输入每一个双亲子女对，以空格分隔：输入0表示结束：";
		cin>>mom;
    	cin>>child;
	}
}

void Tree::Release(TNode *bt)
{
	if (bt == NULL)  return;     //递归调用的结束条件
	else
	{
		Release(bt->firstchild);  //后序递归释放bt的第一棵子树  
		Release(bt->rightsib);    //后序递归释放bt的右兄弟子树  
		delete bt;                //释放根结点
	}
}

void Tree::PreOrder(TNode *bt)
{
	if (bt == NULL)  return;     //递归调用的结束条件
	else
	{
		cout<<bt->data<<"  ";         //访问根结点的数据域
		PreOrder(bt->firstchild);    //前序递归遍历root的第一棵子树    
		PreOrder(bt->rightsib);      //前序递归遍历root的右兄弟子树  
	}
}

void Tree::PostOrder(TNode *bt)
{
	if (bt == NULL)  return;         //递归调用的结束条件
	else
	{
		PostOrder(bt->firstchild);  //后序递归遍历root的第一棵子树  
		PostOrder(bt->rightsib);    //后序递归遍历root的右兄弟子树  
		cout<<bt->data<<"  ";         //访问根结点的数据域
	}
}

//---------------------------------------//
//----------    主函数     --------------//
//---------------------------------------//
int main( )
{	Tree t1;                               //定义一棵树对象t1  
	cout<<"前序遍历序列："<<endl;
	t1.PreOrder();
	cout<<endl;
	cout<<"后序遍历序列："<<endl;
	t1.PostOrder();
	cout<<endl;
	return 0;
}

输入根： ? ? ? ? ? ? ? ? ? ? ? ? ? 1

输入数据双亲子女对：【1 ? ?2】【1 ? 3】【1 ? 4】【2 ? 5】【2 ? ?6】【2 ? ?7】 【3 ? ?8】【4 ? 9】【4 ? ?10 】

输入结束标志 ? ? ? ? ? ? ? ? ? ? 0 ? ? ?0

运行后输出结果为：

? ? 前序遍历序列： ? 1 2 5 6 7 3 8 4 9 10

? ? 后序遍历序列： ?5 6 7 2 8 3 9 10 4 1

请大家分析结果；祝大家写程序成功！

（编辑：温州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!