データ構造とアルゴリズム実験実験6:二叉木ADTの二叉鎖式実現(完全な前順シーケンスから二叉木を作成/二叉木のノード数を求める/樹高/葉ノード数/先順中順後順層シーケンス遍歴)
40775 ワード
二叉数のデータ要素を文字と仮定し,二叉チェーンストレージ構造を採用する.二叉木の作成、二叉木の遍歴(深さ、広さ)、二叉木の深さ(高さ)の求め、二叉木の要素個数の計算、二叉木の葉数の計算、二叉木のフォーマット出力など、二叉木ADTを符号化して実装してください.
入力した記号に基づいて、対応する操作を実行します.次のようになります.
C:ツリーを作成し、「Created success!」を正常に出力します.2つの作成アルゴリズムの実装が要求される.「1」と入力すると、完全前系列に基づいて二叉木が作成され、#は空のノード(空のサブツリー)を表し、次の行は二叉木の完全前系列を入力します.「2」と入力すると、二叉木の前系列と中系列に基づいて二叉木が作成され、後ろに3行あり、それぞれ要素の個数、前系列と中系列を入力します.
H:二叉木の高さを求める;出力:Height=高さL:ツリーの葉数を計算する;出力:Leaves=リーフ数
N:ツリー内の要素の合計個数を計算する.出力:Nodes=ノード数
1:二叉木を順に遍歴する.出力:Preorder is:シーケンス.
2:中順に二叉木を遍歴する.出力:Inorder is:シーケンス.
3:後順に二叉木を遍歴する.出力:Postorder is:シーケンス.
4:広さは二叉木を遍歴する.出力:BFSorder is:シーケンス.
F:検索値xのノード数;出力:The count of x is個数.
P:すべてのノードをディレクトリ縮尺テキスト形式で出力します.出力:The tree is:(改行、次の行は出力のツリー)
X:終了
テスト例:入力:test 1:
result1:
test2:
result2:
test3:
result3:
タイトル:タイトルの中で理解しにくいのはその“P”です:“ディレクトリの縮尺のテキストの形式ですべてのノードを出力します”、サンプルを観察して私達は発見することができます:行の出力の順序によって見て、実は先のルートの順序の順で出力して、それから各ノードの前で現在のノードのありかの層の数l*2-2のスペースを持ちます
構想:先序と中序のシーケンスから木を建てるのはこの文章を参考にすることができて、ノードの数は私たちが木を建てる時に求めることができて、葉の数と木の高さは層序の遍歴を使って求めることができて、検索操作も層序の遍歴を通じて完成することができます.
入力した記号に基づいて、対応する操作を実行します.次のようになります.
C:ツリーを作成し、「Created success!」を正常に出力します.2つの作成アルゴリズムの実装が要求される.「1」と入力すると、完全前系列に基づいて二叉木が作成され、#は空のノード(空のサブツリー)を表し、次の行は二叉木の完全前系列を入力します.「2」と入力すると、二叉木の前系列と中系列に基づいて二叉木が作成され、後ろに3行あり、それぞれ要素の個数、前系列と中系列を入力します.
H:二叉木の高さを求める;出力:Height=高さL:ツリーの葉数を計算する;出力:Leaves=リーフ数
N:ツリー内の要素の合計個数を計算する.出力:Nodes=ノード数
1:二叉木を順に遍歴する.出力:Preorder is:シーケンス.
2:中順に二叉木を遍歴する.出力:Inorder is:シーケンス.
3:後順に二叉木を遍歴する.出力:Postorder is:シーケンス.
4:広さは二叉木を遍歴する.出力:BFSorder is:シーケンス.
F:検索値xのノード数;出力:The count of x is個数.
P:すべてのノードをディレクトリ縮尺テキスト形式で出力します.出力:The tree is:(改行、次の行は出力のツリー)
X:終了
テスト例:入力:test 1:
C
1
ABC##DE#G##F###
H
L
N
1
2
3
4
F
A
P
X
result1:
Created success!
Height=5
Leaves=3
Nodes=7
Preorder is:A B C D E G F .
Inorder is:C B E G D F A .
Postorder is:C G E F D B A .
BFSorder is:A B C D E F G .
The count of A is 1
The tree is:
A
B
C
D
E
G
F
test2:
C
1
+-*1##2##-3##4##/+5##6##*7##8##
H
L
N
1
2
3
4
F
+
P
X
result2:
Created success!
Height=4
Leaves=8
Nodes=15
Preorder is:+ - * 1 2 - 3 4 / + 5 6 * 7 8 .
Inorder is:1 * 2 - 3 - 4 + 5 + 6 / 7 * 8 .
Postorder is:1 2 * 3 4 - - 5 6 + 7 8 * / + .
BFSorder is:+ - / * - + * 1 2 3 4 5 6 7 8 .
The count of + is 2
The tree is:
+
-
*
1
2
-
3
4
/
+
5
6
*
7
8
test3:
C
2
6
abdcef
dbaecf
H
L
N
1
2
3
4
F
+
P
X
result3:
Created success!
Height=3
Leaves=3
Nodes=6
Preorder is:a b d c e f .
Inorder is:d b a e c f .
Postorder is:d b e f c a .
BFSorder is:a b c d e f .
The count of + is 0
The tree is:
a
b
d
c
e
f
タイトル:タイトルの中で理解しにくいのはその“P”です:“ディレクトリの縮尺のテキストの形式ですべてのノードを出力します”、サンプルを観察して私達は発見することができます:行の出力の順序によって見て、実は先のルートの順序の順で出力して、それから各ノードの前で現在のノードのありかの層の数l*2-2のスペースを持ちます
構想:先序と中序のシーケンスから木を建てるのはこの文章を参考にすることができて、ノードの数は私たちが木を建てる時に求めることができて、葉の数と木の高さは層序の遍歴を使って求めることができて、検索操作も層序の遍歴を通じて完成することができます.
#include
#include
#include
using namespace std;
struct node
{
char x;
node* lson;
node* rson;
int l;
node(){l=-1;}
};
char pre[1000],in[1000];
int Height=0,Nodes=0,Leaves=0;
void creat(node* &root,int l)///
{
root=new node;
char c;cin>>c;
if(c=='#') root=NULL;
else
{
root->x=c;
Nodes++;
Height=max(l,Height);///
creat(root->lson,l+1);
creat(root->rson,l+1);
}
}
node* recreat(int prel,int prer,int inl, int inr)///
{
if(prel>prer) return NULL;
node *root=new node;
root->x=pre[prel];
int k;
for(k=inl;k<inr;k++)
{
if(in[k]==pre[prel])
break;
}
int num=k-inl;
root->lson=recreat(prel+1,prel+1+num-1,inl,k-1);
root->rson=recreat(prel+num+1,prer,k+1,inr);
return root;
}
void order(node* Node,int type)///
{
if(Node==NULL) return;
if(type==1)cout<<Node->x<<" ";
order(Node->lson,type);
if(type==2)cout<<Node->x<<" ";
order(Node->rson,type);
if(type==3)cout<<Node->x<<" ";
}
int Findcnt=0;
char sign;
void LayerOrder(node* e,int type)///type=0 ,type=1 ,type=2 sign
{
if(type==1) cout<<"BFSorder is:";
if(e==NULL) return;
e->l=1;
queue<node*> q;
q.push(e);
while(!q.empty())
{
node* temp=q.front();
if(type==2&&temp->x==sign) Findcnt++;
q.pop();
if(type==1)printf("%c ",temp->x);
if(temp->lson)
{
temp->lson->l=temp->l+1;
if(type==1)Height=max(Height,temp->lson->l);
q.push(temp->lson);
}
if(temp->rson)
{
temp->rson->l=temp->l+1;
if(type==0)Height=max(Height,temp->rson->l);
q.push(temp->rson);
}
if(type==0&&!temp->rson&&!temp->lson)/// ,
Leaves++;
}
if(type==1) cout<<".
";
return;
}
void Porder(node* Node)///
{
if(Node==NULL) return;
for(int i=1;i<=Node->l*2-2;i++) cout<<' ';
cout<<Node->x<<'
';
Porder(Node->lson);
Porder(Node->rson);
}
int main()
{
node* root;
char c;
for(int i=1;i<=11;i++)
{
cin>>c;
if(c=='C')
{
Nodes=Leaves=Height=0;
int t;cin>>t;
if(t==1) creat(root,1);
if(t==2)
{
int n;cin>>n;Nodes=n;
for(int i=0;i<n;i++) cin>>pre[i];
for(int i=0;i<n;i++) cin>>in[i];
root=recreat(0,n-1,0,n-1);/// (0,n-1), (0,n); 0
}
LayerOrder(root,0);///
cout<<"Created success!"<<endl;
}
if(c=='H') cout<<"Height="<<Height<<endl;
if(c=='L') cout<<"Leaves="<<Leaves<<endl;
if(c=='N') cout<<"Nodes="<<Nodes<<endl;
if(c=='1'||c=='2'||c=='3')
{
if(c=='1')cout<<"Preorder is:";
if(c=='2')cout<<"Inorder is:";
if(c=='3')cout<<"Postorder is:";
order(root,c-'0');
cout<<".
";
}
if(c=='4') LayerOrder(root,1);
if(c=='F')
{
cin>>sign;
Findcnt=0;
LayerOrder(root,2);
cout<<"The count of "<<sign<<" is "<<Findcnt<<endl;
}
if(c=='P')
{
cout<<"The tree is:"<<endl;
Porder(root);
}
if(c=='X')return 0;
}
return 0;
}