1019_ツリーの高さとノード数の計算
3548 ワード
ツリーの高さとノード数の計算
時間制限(通常/Java):1000 MS/3000 MS実行メモリ制限:65536 KByte総提出:1152テスト合格:355
試合の説明
ツリーは非常に重要なツリーデータ構造であり、ツリーの先頭シーケンス、中シーケンス、または後シーケンス遍歴シーケンスに基づいてツリーを構築することができます.例えば、シーケンスA B#D#C E#F#を入力すると、図1019−1に示すツリーを構築することができ、ここでは、図1019−2に示すように、空のツリーまたは空のツリーを表す#を用いる(別の言い方では、子供のノードがなければ、代わりに#を用いる).
図1019-1
図1019-2
遍歴に基づく二叉木演算を実現してください:高さを求めて、結点の数を計算します
入力
ツリーの先頭シーケンスは、空のツリーまたは空のサブツリーを#で表します.
しゅつりょく
合計5行
最初の3行は順に先順、中順、後順の遍歴シーケンスを出力し、
4行目の出力ツリーの高さは、
5行目は,二叉木の総括点数,葉の結点数,度が1の結点数を順次出力する.
サンプル入力
A B # D # # C E # # F # #
サンプル出力
PreOrder: A B D C E F InOrder: B D A E C F PostOrder: D B E F C A 3 6 3 1
ヒント
//先順遍歴シーケンスに基づいてツリーを作成!
template void BinaryTree::Create(BTNode*& t){ char c; cin>>c; if(c=='#') t=NULL; else{ t=new BTNode(c); Create(t->lChild); Create(t->rChild); } }
テーマソース
CHENZ
アルゴリズム構想:二叉木に関する問題は一般的に再帰アルゴリズムで解決される.
注意点:
1.#define Max(a,b)(a>b?a:b)後ろのかっこは捨てられないことに注意し、defineは文体置換を実行します.
2.二叉木接点の個数関係に注意:N 0=N 2+1,N=N 0+N 1+N 2,N 1=N-2*N 0+1
コードは次のとおりです.
オブジェクト向けプログラミングでは、これを参照してください.
時間制限(通常/Java):1000 MS/3000 MS実行メモリ制限:65536 KByte総提出:1152テスト合格:355
試合の説明
ツリーは非常に重要なツリーデータ構造であり、ツリーの先頭シーケンス、中シーケンス、または後シーケンス遍歴シーケンスに基づいてツリーを構築することができます.例えば、シーケンスA B#D#C E#F#を入力すると、図1019−1に示すツリーを構築することができ、ここでは、図1019−2に示すように、空のツリーまたは空のツリーを表す#を用いる(別の言い方では、子供のノードがなければ、代わりに#を用いる).
図1019-1
図1019-2
遍歴に基づく二叉木演算を実現してください:高さを求めて、結点の数を計算します
入力
ツリーの先頭シーケンスは、空のツリーまたは空のサブツリーを#で表します.
しゅつりょく
合計5行
最初の3行は順に先順、中順、後順の遍歴シーケンスを出力し、
4行目の出力ツリーの高さは、
5行目は,二叉木の総括点数,葉の結点数,度が1の結点数を順次出力する.
サンプル入力
A B # D # # C E # # F # #
サンプル出力
PreOrder: A B D C E F InOrder: B D A E C F PostOrder: D B E F C A 3 6 3 1
ヒント
//先順遍歴シーケンスに基づいてツリーを作成!
template
テーマソース
CHENZ
アルゴリズム構想:二叉木に関する問題は一般的に再帰アルゴリズムで解決される.
注意点:
1.#define Max(a,b)(a>b?a:b)後ろのかっこは捨てられないことに注意し、defineは文体置換を実行します.
2.二叉木接点の個数関係に注意:N 0=N 2+1,N=N 0+N 1+N 2,N 1=N-2*N 0+1
コードは次のとおりです.
#include <iostream>
using namespace std;
#define Max(a,b) (a>b?a:b)//
struct TreeNode
{
char name;
TreeNode * LChild;
TreeNode *RChild;
};
TreeNode *CreatTree();//
void PreOrder(TreeNode* root);//
void InOrder(TreeNode* root);//
void PostOrder(TreeNode* root);//
int HighOfTree(TreeNode* root);//
int NumOfNode(TreeNode* root);//
int NumOfLeaf(TreeNode* root);//
int main()
{
int num_node, num_leaf, num_1child, h;
TreeNode* root = CreatTree();
cout << "PreOrder:";
PreOrder(root);
cout << endl << "InOrder:";
InOrder(root);
cout << endl << "PostOrder:";
PostOrder(root);
cout << endl;
h = HighOfTree(root);
cout << h << endl;
num_node = NumOfNode(root);
num_leaf = NumOfLeaf(root);
if (root == NULL)
num_1child = 0;
else
num_1child = num_node - 2 * num_leaf + 1;//
cout << num_node << ' ' << num_leaf << ' ' << num_1child;
return 0;
}
TreeNode *CreatTree()
{
char c;
cin >> c;
TreeNode* node;
if (c == '#')
node = NULL;
else
{
node = new TreeNode();
node->name = c;
node->LChild=CreatTree();
node->RChild = CreatTree();
}
return node;
}
void PreOrder(TreeNode* root)
{
if (root!=NULL)
{
cout << ' ' << root->name;
PreOrder(root->LChild);
PreOrder(root->RChild);
}
}
void InOrder(TreeNode* root)
{
if (root!=NULL)
{
InOrder(root->LChild);
cout << ' ' << root->name;
InOrder(root->RChild);
}
}
void PostOrder(TreeNode* root)
{
if (root!=NULL)
{
PostOrder(root->LChild);
PostOrder(root->RChild);
cout << ' ' << root->name;
}
}
int HighOfTree(TreeNode* root)
{
if (root == NULL)
return 0;
else
return Max(HighOfTree(root->LChild), HighOfTree(root->RChild)) + 1;
}
int NumOfNode(TreeNode* root)
{
if (root == NULL)
return 0;
else
return 1 + NumOfNode(root->LChild) + NumOfNode(root->RChild);
}
int NumOfLeaf(TreeNode* root)
{
if (root == NULL)
return 0;
else if (root->LChild == NULL&&root->RChild == NULL)
return 1;
else
return NumOfLeaf(root->LChild) + NumOfLeaf(root->RChild);
}オブジェクト向けプログラミングでは、これを参照してください.