PATプログラム設計問題——甲級1004遍歴木ノード(木の各層の葉ノード数を計算する)
5149 ワード
試験問題のリンクは以下の通りです:クリックしてリンクを開きます
プログラム入力:最初の行はツリーの総ノード数N(<100)、非リーフノード数Mとして入力され、スペースで区切られます.その後、M行を入力します.各行のフォーマットは以下の通りです.
ID K ID[1] ID[2]...ID[K]
1番目のIDは1つの非リーフノードの2桁の番号を表し、2桁未満は0で埋め込まれ、Kはそのノードのサブノード数を表し、その後のK個のIDはサブノードの2桁の番号を表す.現定rootルートノードIDは01です.
プログラム出力:ツリーの各層におけるリーフノードの個数を算出し,ルートノードが存在する層から徐々に下層に向かい,スペースで区切る.
例:
input:
2 1
01 1 02
output:
0 1
コードは以下のように設計されています.
プログラム入力:最初の行はツリーの総ノード数N(<100)、非リーフノード数Mとして入力され、スペースで区切られます.その後、M行を入力します.各行のフォーマットは以下の通りです.
ID K ID[1] ID[2]...ID[K]
1番目のIDは1つの非リーフノードの2桁の番号を表し、2桁未満は0で埋め込まれ、Kはそのノードのサブノード数を表し、その後のK個のIDはサブノードの2桁の番号を表す.現定rootルートノードIDは01です.
プログラム出力:ツリーの各層におけるリーフノードの個数を算出し,ルートノードが存在する層から徐々に下層に向かい,スペースで区切る.
例:
input:
2 1
01 1 02
output:
0 1
コードは以下のように設計されています.
#include
#include
#include
typedef struct TreeNode
{
char value;
TreeNode** childList;
int childCapacity;
int childNumber;
TreeNode( char value )
{
childNumber = 0;
childCapacity = 5;
this->value = value;
childList = (TreeNode**)malloc(childCapacity*sizeof(TreeNode*));
}
~TreeNode()
{
free(childList);
childList = NULL;
}
void SetNodeValue( char value )
{
this->value = value;
}
void SetNodeList( TreeNode** list )
{
childList = list;
}
char GetNodeValue()
{
return this->value;
}
TreeNode** GetNodeList()
{
return childList;
}
TreeNode* GetNodeListItem(int index)
{
return childList[index];
}
int AddChild( TreeNode* node )
{
if ( childNumber == childCapacity )
{
TreeNode** old = childList;
childList = (TreeNode**)realloc( childList, 2*sizeof(TreeNode*)*childCapacity );
if ( childList == NULL )
{
childList = old;
return false;
}
childCapacity = 2*childCapacity;
}
childList[childNumber++] = node;
return true;
}
}TREE_NODE,*PTREE_NODE;
typedef struct LevelInfo
{
int* number;
int size;
int capacity;
LevelInfo()
{
size = 0;
capacity = 5;
number = (int*)malloc(capacity*sizeof(int));
for ( int i = 0; i < capacity; i++ )
{
number[i] = 0;
}
}
~LevelInfo()
{
free(number);
}
void SetLevelCapacity( int count )
{
if ( capacity < count )
{
int* old = number;
number = (int*)realloc( number, capacity*2 );
if ( number == NULL )
{
number = old;
return;
}
for ( int i = capacity; i < 2*capacity; i++ )
{
number[i] = 0;
}
capacity *= 2;
}
}
void SetLevelSize( int level, int number )
{
this->number[level] = number;
if ( level > size ) size = level;
}
int GetLevelSize( int level )
{
return number[level];
}
void ResetAnaly()
{
for ( int i = 0; i < capacity; i++ )
{
number[i] = 0;
}
size = 0;
}
}LEVEL_INFO,*PLEVELINFO;
class CTreeLevelAnaly
{
public:
CTreeLevelAnaly()
{
InitTree();
}
~CTreeLevelAnaly()
{
UninitTree(m_pTreeRoot);
delete m_pTreeRoot;
}
int InitTree()
{
printf( "Please input the number of node and non-leaf node:
");
scanf( "%d %d", &m_iAllNodeCount, &m_iNonLeafNodeCount );
TreeNode** tempList = (TreeNode**)malloc( m_iAllNodeCount*sizeof(TreeNode*) );
for ( int i = 0; i < m_iAllNodeCount; i++ )
{
TreeNode* pNode = new TreeNode( (i+1) );
tempList[i] = pNode;
}
printf( "Please input %d lines describe the parent and chidren
", m_iNonLeafNodeCount );
for ( int k = 0; k < m_iNonLeafNodeCount; k++ )
{
char* dot = NULL;
char buffer[100] = {0};
int* list = (int*)malloc( 100*sizeof(int) );
int used = 0;
printf( "the %d line:
", k+1 );
getchar();
scanf( "%[^
]", buffer );
dot = strtok( buffer, " " );
while ( dot != NULL )
{
list[used++] = atoi(dot);
dot = strtok( NULL, " ");
}
list[used] = -1;
for ( int j = 2; j < used; j++ )
{
int index = list[j];
int pos = list[0];
tempList[ pos - 1 ]->AddChild( tempList[ index - 1 ] );
}
}
m_pTreeRoot = tempList[0];
free(tempList);
return 0;
}
void UninitTree( TreeNode* node )
{
for (int i = 0; i < node->childNumber; i++ )
{
UninitTree( node->childList[i] );
delete node->childList[i];
}
}
TreeNode* GetRootNode()
{
return m_pTreeRoot;
}
int PrintLevelAnaly()
{
int size = m_kLevelCount.size;
for ( int i = 0; i <= size; i++ )
{
printf("Level %d has %d Leaf-Node
", i, m_kLevelCount.number[i] );
}
return false;
}
// ,
int dfsRecursiveLevelCount( TreeNode* node, int level )
{
printf("visiting: value:%c;level:%d
", node->value, level );
m_kLevelCount.SetLevelCapacity(level);
//
if ( node->childNumber == 0 )
{
int temp = m_kLevelCount.GetLevelSize( level );
if ( temp == 0 )
{
temp = 1;
}
else
{
temp++;
}
m_kLevelCount.SetLevelSize( level, temp );
}
for (int i = 0; i < node->childNumber; i++ )
{
dfsRecursiveLevelCount( node->childList[i], level + 1 );
}
return 0;
}
protected:
private:
TreeNode* m_pTreeRoot;
LevelInfo m_kLevelCount;
int m_iAllNodeCount;
int m_iNonLeafNodeCount;
};
int main()
{
CTreeLevelAnaly* tree = new CTreeLevelAnaly;
printf("----------- , ------------
");
tree->dfsRecursiveLevelCount( tree->GetRootNode(), 0 );
tree->PrintLevelAnaly();
delete tree;
printf("
");
return 0;
}