0

下面是一个程序，它首先从中序和前序构建二叉树，然后找到包含最大平衡树的节点。

我的两个功能都是正确的Buildtree。IsBalanced

我正在从input.txt文件中读取顺序和预购；所以在第一次迭代中，我的程序显示正确的输出，但在第二次迭代中，它不起作用。

我认为删除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

当使用树或层次结构（集合）时，您应该将“根”变量保留在“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

看来您在 buildTree 中有一个由第二组数据触发的错误。该错误导致无限递归，您会得到“stackoverflow”:-)并且您的程序崩溃。您可以通过将第 3 行和第 4 行与第二个 input.txt 示例数据的第 1 行和第 2 行交换来确认这一点，然后您的程序将在第一次迭代时终止。您可以使用 gdb 运行您的程序并捕获 stackoverflow。您还可以在 buildTree 中放置一个 print 语句，并会看到它陷入了无限递归。

于 2012-07-17T11:43:15.417 回答