0

以下は、最初に inorder と preorder から二分木を構築し、次に最大の平衡木を含むノードを見つけるプログラムです。

私の両方の機能BuildtreeとIsBalanced正しいです。

input.txtファイルから inorder と preorder を読み込んでいます。そのため、最初の反復では私のプログラムは正しい出力を示していますが、2 回目の反復では機能しません。

rootの削除に問題があると思います。

上記のプログラムを実行すると、私が話している問題が発生します。

/* Tree - Program to find largest Balanced tree in given tree
@Date : 15 July 2012

This program works only for one input sample
*/
#include<stdio.h>
#include<stdlib.h>
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
using namespace std;
struct node
{
  char data;
  struct node* left;
  struct node* right;
};

/* Prototypes for utility functions */
int search(string arr, int strt, int end, char value);
struct node* newNode(char data);

int isBalanced(struct node *root, int* height,int *max_size_ref, bool *is_bal_ref,char *val)
{
  /* lh = Height of left subtree ,rh = Height of right subtree */   
  int lh = 0, rh = 0;  
 int left_flag=0;
 int right_flag=0;
  /* l will be true if left subtree is balanced 
    and r will be true if right subtree is balanced */
  int l = 0, r = 0;

  if(root == NULL)
  {
    *height = 0;
    *is_bal_ref = 1;
     return 0;
  }

  l = isBalanced(root->left, &lh, max_size_ref,is_bal_ref, val);

  if (*is_bal_ref == 1)
  left_flag=true;

  r = isBalanced(root->right,&rh, max_size_ref,is_bal_ref, val);
  if (*is_bal_ref == 1)
  right_flag = true;

  *height = (lh > rh? lh: rh) + 1;
  if((lh - rh >= 2) || (rh - lh >= 2))
  *is_bal_ref= 0;

  /* If this node is balanced and left and right subtrees 
    are balanced then return true */
  if(left_flag && right_flag && *is_bal_ref ){
  *is_bal_ref= 1;
  if (l + r + 1 > *max_size_ref)
  {  
        *max_size_ref = l + r+ 1;
        *val = root->data;}
        return l + r + 1;
  }
  else
  {
    //Since this subtree is not Balanced, set is_bal flag for parent calls
     *is_bal_ref = 0; 
     return 0;
  }
}


struct node* buildTree(string in, string pre, int inStrt, int inEnd)
{
  static int preIndex = 0;

  if(inStrt > inEnd)
     return NULL;

  /* Pick current node from Preorder traversal using preIndex
    and increment preIndex */
  struct node *tNode = newNode(pre[preIndex++]);

  /* If this node has no children then return */
  if(inStrt == inEnd)
    return tNode;

  int inIndex = search(in, inStrt, inEnd, tNode->data);

  /* Using index in Inorder traversal, construct left and
     right subtress */
  tNode->left = buildTree(in, pre, inStrt, inIndex-1);
  tNode->right = buildTree(in, pre, inIndex+1, inEnd);

  return tNode;
}


/* Function to find index of value in arr[start...end]
   The function assumes that value is present in in[] */

int search(string arr, int strt, int end, char value)
{
  int i;
  for(i = strt; i <= end; i++)
  {
    if(arr[i] == value)
      return i;
  }
}

/* Helper function  */
struct node* newNode(char data)
{
  struct node* node = new (struct node);
  node->data = data;
  node->left = NULL;
  node->right = NULL;

  return(node);
}

/* This function is for inorder traversal */
void printInorder(struct node* node)
{
  if (node == NULL)
     return;


  printInorder(node->left);


  printf("%c ", node->data);


  printInorder(node->right);
}

// function to free binary tree
void freeT(struct node* t ) //get root
{
    if( t == NULL ) 
        return;
    if( t->left != NULL )
        freeT( t->left );
    if( t->right != NULL )
        freeT( t->right);

    delete(t);       /* free(t) if c */

    return;
}



/* Driver program to test above functions */
int main()
{

 string line , inorder;
 ifstream myfile ("input.txt");
 ofstream myofile ("output.txt" );
 if (myfile.is_open())
 { 
   int len=0;
   char data=NULL;
   int height=0;
   int max_size_ref=0;
   bool is=false;
   int size=0;
   struct node *root = NULL;
   while ( myfile.good() )
    {
      getline (myfile,line);
      //cout << line << endl;
      inorder=line;
      getline (myfile,line);
      //cout << line << endl;

      len = line.size();
      //cout<<"len="<<len;

      root= buildTree(inorder, line, 0, len - 1);

      data=NULL;
      height=0;
      max_size_ref=0;
      is=false;
      size=isBalanced(root, &height ,&max_size_ref, &is, &data);
      if(data!=NULL)
      {
      myofile<<data;
      myofile<<"\n";
      //std::cout<<data;
      }
      else
      {
      myofile<<-1;
      myofile<<"\n";
      }
      //printf("\n Inorder traversal of the constructed tree is \n");
      //printInorder(root);
      getchar();
      //freeT(root);
      //root=NULL;
   }
    myfile.close();
    myofile.close();
  }

  //getchar();
  return 0;
}

最初に、以下の内容を含む input.txt を使用してこのプログラムを実行し、output.txt を参照してください。

FDBGEHAC
ABDFEGHC

次に、上記のプログラムを実行します

    FDBGEHAC
    ABDFEGHC
    FDCEBAJHGI
    ABCDFEGHJI

output.txt を参照してください

あなたは私が本当に欲しいものを手に入れるでしょう。

4

2 に答える 2

0

ツリーまたは階層構造 ( collection ) を使用する場合、「root」変数を「while」ループまたは他のノードの外側に保持する必要があります。

これは疑似コードであり、完全に有効なコードを意図したものではなく、単なる例です。

int main()
{
   ...

   struct node *root = NULL;

   while ( myfile.good() )
   {

     // load tree, maybe change root

   } // while

   ...
} // int main()

あなたがすでにチェックしているように。「ルート」は構造体へのポインタであり、それによってどのノードがルートになるかが変わる可能性がある場合でも、外部変数が必要です。

于 2012-07-15T16:29:08.053 に答える
0

2 番目のデータ セットによってトリガーされる buildTree にバグがあるようです。このバグにより無限再帰が発生し、「stackoverflow」が発生して :-)、プログラムがクラッシュします。これを確認するには、3 行目と 4 行目を 2 番目の input.txt サンプル データの 1 行目と 2 行目に置き換えます。プログラムは最初の繰り返しで停止します。プログラムを gdb で実行すると、stackoverflow がキャッチされます。buildTree に print ステートメントを入れることもでき、無限再帰に引っかかることがわかります。

于 2012-07-17T11:43:15.417 に答える