为了大家熟悉树的操作,现参照课本给出一个树的存储操作示例。
将下面的树存入计算机,并前序和后序输出各个结点数据。为了方便,本树输入结点数据为整数。
#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
请大家分析结果;祝大家写程序成功!