用队列实现的带度数的后根次序恢复树 算法思想： 从左向右扫描数组，每遇到一个结点都进队列，当结点度数degree不为0时，则从队列中出degree个结点作为其子结 点，由于是先进先出，出队列的顺序正好是从左到右的子树顺序。 但要注意，出队列的结点应是队列中最后的degree个，所以要不断进行出队列、入队列操作直到找到正确的子结点。 //queue.cpp#include"iostream.h"#include"math.h"class BinNode{public: BinNode(char e) { left=NULL; right=NULL; elem=e; } char elem; BinNode* left; BinNode* right;};class Queue{public: BinNode* *listarray; int size; int front; int rear;// int queuenum; Queue(int n) { size=n; front=rear=0; listarray=new BinNode*[size]; } ~Queue() { delete [] listarray; } bool isEmpty() const { return front==rear; } void enqueue(BinNode* p) { rear=(rear+1)%size; listarray[rear]=p; } BinNode* dequeue() { front=(front+1)%size; return listarray[front]; } int queuenum() { if(front<rear) return rear-front; else return rear+size-front; }};struct DegreeNode{ int degree; char info;};BinNode* settree(DegreeNode tree[100],int n){ Queue Q(n+1); BinNode *ps,*pc,*rt; int i,j; for(i=0;i<n;i++) { ps=new BinNode(tree[i].info); //建立新二叉树结点 for(j=0;j<Q.queuenum()-tree[i].degree;j++) //如果度数大于队列中元素，则通过不断出入队列把应有的子结点找出 { pc=Q.dequeue(); Q.enqueue(pc); } Q.enqueue(ps); for(j=0;j<tree[i].degree;j++) //链入子结点 { pc=Q.dequeue(); if(j==0) //j=0时为最左结点 ps->left=pc; else //否则为右兄弟结点 ps->right=pc; ps=pc; } } pc=Q.dequeue(); //把多棵树连起来 rt=pc; //第一个出队列的是返回的数根 ps=pc; while(!Q.isEmpty()) { pc=Q.dequeue(); ps->right=pc; } return rt;}void visit(BinNode* rt,int flag){ if(rt==NULL) return; if(flag) cout<<rt->elem; visit(rt->left,flag); if(!flag) cout<<rt->elem; visit(rt->right,flag);}void main(){ int n,i; BinNode *rt; DegreeNode tree[100]; cout<<"请输入结点个数"; cin>>n; for(i=0;i<n;i++) { cout<<"请输入第"<<i+1<<"个结点的内容"; cin>>tree[i].info; cout<<"请输入第"<<i+1<<"个结点的度数"; cin>>tree[i].degree; } rt=settree(tree,n); cout<<"此二叉链表的前序序列为"; visit(rt,1); cout<<endl; cout<<"此二叉链表的中序序列为"; visit(rt,0); cout<<endl;} //队列.cpp #include"iostream.h"class BinNode{public: BinNode(char e) { left=NULL; right=NULL; elem=e; } char elem; BinNode* left; BinNode* right;};class Queue{public: BinNode* *listarray; int size; int front; int rear;// int queuenum; Queue() { size=50; front=rear=0; listarray=new BinNode*[size]; } ~Queue() { delete [] listarray; } bool isEmpty() const { return front==rear; } void enqueue(BinNode* p) { rear=(rear+1)%size; listarray[rear]=p; } BinNode* dequeue() { front=(front+1)%size; return listarray[front]; } int queuenum() { return (rear-front)%size; }};struct DegreeNode{ int degree; char info;};BinNode* settree(DegreeNode tree[100],int n){ Queue Q; BinNode *ps,*pc,*rt; int i,j; for(i=0;i<n;i++) { ps=new BinNode(tree[i].info); for(j=0;j<Q.queuenum()-tree[i].degree;j++) { pc=Q.dequeue(); Q.enqueue(pc); } Q.enqueue(ps); for(j=0;j<tree[i].degree;j++) { pc=Q.dequeue(); if(j==0) ps->left=pc; else ps->right=pc; ps=pc; } } pc=Q.dequeue(); rt=pc; ps=pc; while(!Q.isEmpty()) { pc=Q.dequeue(); ps->right=pc; } return rt;}void visit(BinNode* rt,int flag){ if(rt==NULL) return; if(flag) cout<<rt->elem; visit(rt->left,flag); if(!flag) cout<<rt->elem; visit(rt->right,flag);}void main(){ int n,i; BinNode *rt; DegreeNode tree[100]; cout<<"请输入结点个数"; cin>>n; for(i=0;i<n;i++) { cout<<"请输入第"<<i+1<<"个结点的内容"; cin>>tree[i].info; cout<<"请输入第"<<i+1<<"个结点的度数"; cin>>tree[i].degree; } rt=settree(tree,n); cout<<"此二叉链表的前序序列为"; visit(rt,1); cout<<endl; cout<<"此二叉链表的中序序列为"; visit(rt,0); cout<<endl;}
评论