我需要創建多棵樹來比較它們的形狀并計算我得到了多少不同形狀的樹（相同的形式將被視為一種形式）。
輸入將是：
樹（需要多少棵樹（從 1 到 50）層（一棵樹中有多少節點（從 1 到 20））
值（每棵樹中的值（從 1 到 1000000））
輸入影像：
5 3
3 8 2
4 2 5
2 6 10
3 7 6
10 8 4
必須有五棵樹，每棵樹有三個節點。[![在此處輸入影像描述][1]][1]
前兩棵樹的形狀相同，其他的則不同。
輸出：4
輸入示例：
2 2
1 2
2 1
所以必須有兩棵樹，每棵樹都有兩個節點。
答案是2，因為可以有 2 種不同形式的樹
另一個輸入示例：
6 7
7 6 3 5 4 2 1
1 3 2 4 7 5 6
4 7 1 2 5 3 6
5 1 6 7 2 4 3
1 3 2 5 6 4 7
6 7 1 5 4 2 3
答案：6
我能夠用結構創建一棵樹，但我不知道如何創建幾個以及如何比較它們的形狀
也許我不需要多棵樹。也許我會創建一棵樹，向它寫入值，然后以某種方式“保存”它的形狀，清除它，然后將下一棵樹寫入它。
最好的方法是什么？
UPD：
如何正確釋放分配的記憶體？（我知道free()但我不知道在這種情況下如何使用它）
==1835523==
==1835523== HEAP SUMMARY:
==1835523== in use at exit: 768 bytes in 32 blocks
==1835523== total heap usage: 34 allocs, 2 frees, 5,888 bytes allocated
==1835523==
==1835523== 768 (192 direct, 576 indirect) bytes in 8 blocks are definitely lost in loss record 4 of 4
==1835523== at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==1835523== by 0x1091C1: create_node (in /home/os724nv/prog-6824/ps3/isolation)
==1835523== by 0x109222: insertnumber (in /home/os724nv/prog-6824/ps3/isolation)
==1835523== by 0x109458: main (in /home/os724nv/prog-6824/ps3/isolation)
==1835523==
==1835523== LEAK SUMMARY:
==1835523== definitely lost: 192 bytes in 8 blocks
==1835523== indirectly lost: 576 bytes in 24 blocks
==1835523== possibly lost: 0 bytes in 0 blocks
==1835523== still reachable: 0 bytes in 0 blocks
==1835523== suppressed: 0 bytes in 0 blocks
==1835523==
這是我的代碼：
#include <stdio.h>
#include <stdbool.h>
#include <time.h>
#include <stdlib.h>
struct node {
int item;
struct node* left;
struct node* right;
};
struct node *create_node(int item){
struct node* result = malloc(sizeof(struct node));
if (result != NULL){
result->left = NULL;
result->right = NULL;
result->item = item;
}
return result;
}
bool insertnumber(struct node **rootptr, int item){
struct node *root = *rootptr;
if(root == NULL){
(*rootptr) = create_node(item);
return true;
}
if(item == root->item){
return false;
}
if( item < root->item){
return insertnumber(&(root->left),item);
}else{
return insertnumber(&(root->right),item);
}
}
void fast_input(int* int_input)
{
*int_input=0;
char next_char=0;
while( next_char < '0' || next_char > '9' ){ // Skip non-digits
next_char = getchar();
}
while( next_char >= '0' && next_char <= '9' )
{
(*int_input) = ((*int_input)<<1) ((*int_input)<<3) next_char - '0';
next_char = getchar();
}
}
bool IdenticalTreeShape(struct node *tree1, struct node *tree2)
{
if (!tree1 && !tree2) {
return true;
}
if ( (!tree1)
||(!tree2)
||(tree1->left && !tree2->left)
||(tree1->right && !tree2->right)
||(!IdenticalTreeShape(tree1->left, tree2->left))
||(!IdenticalTreeShape(tree1->right, tree2->right)) ) {
return false;
}
return true;
}
int main(){
struct node *treeList[50] = {0,0,0};
int trees;
int layers;
fast_input(&trees);
fast_input(&layers);
int item;
int nbUniq = trees;
for( int y = 0; y < trees; y ){
for(int x = 0; x < layers; x ){
fast_input(&item);
insertnumber(&treeList[y], item);
}
}
int first_tree = 0;
int second_tree = 1;
for( ; first_tree < trees - 1; first_tree ){
second_tree = first_tree 1;
for ( ; second_tree < trees; second_tree ){
if(IdenticalTreeShape(treeList[first_tree],treeList[second_tree])){
nbUniq--;
if (nbUniq < 1){
nbUniq = 1;
}
break;
}
}
}
printf("%d\n",nbUniq);
}
uj5u.com熱心網友回復：
對于比較功能：
bool IdenticalTreeShape(struct node *tree1, struct node *tree2)
{
if (!tree1 && !tree2) {
return true;
}
if ( (!tree1)
||(!tree2)
||(!IdenticalTreeShape(tree1->left, tree2->left)
||(!IdenticalTreeShape(tree1->right, tree2->right) ) {
return false;
}
return true;
}
現在，您需要保留找到的每個 uniq 形狀，以查看新命題是否為 uniq。您可以通過多種方式做到這一點。
例如 ：
有一個您將輸入的樹數的陣列arrayUniq。將整數 nbUniq 設定為 0。
在 arrayUniq[nbUniq] 中輸入并創建你的樹
比較從“0”到“nbUniq - 1”的所有樹形與 arrayUniq[nbUniq]。如果沒有一棵樹是相同的，則增加 nbUniq。
完畢 ：）
uj5u.com熱心網友回復：
偽代碼（評論太長）：
bool SameShape(node* tree1, node* tree2)
{
if (isNull(tree1))
if isNull(tree2))
return true;
else
return false;
else
if (!isNull(tree2))
return false;
if (isNull(tree1->left) != isNull(tree2->left))
return false;
if (isNull(tree1->right) != isNull(tree2->right))
return false;
bool same = true;
if (!isNull(tree1->left))
same = SameShape(tree1->left, tree2->left);
if (same && !isNull(tree1-right)
same = SameShape(tree1-right, tree2->right);
return same;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/455489.html
下一篇：替代“空”值