binary tree in array

binary tree in array, inorder travers, do not work properly,

Page 1 of 1

2 Replies - 15419 Views - Last Post: 23 November 2010 - 10:03 AM Rate Topic: -----

#1 zigurdis  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 05-November 09

binary tree in array

Posted 22 November 2010 - 08:21 AM

#include <iostream>

using namespace std;

int leftchild(int nodeindex) // returns the index of the left child
{
return  nodeindex *2 + 1 ;
}

int rightchild(int nodeindex) // returns the index of the right child
{
return nodeindex * 2 +2; 
}



int inorder(int *mas, int nodeindex, int i, int *arr) // a recursive function to print the nodes values, put in array
{
if (mas[nodeindex] == 0) return 0 ;
inorder(mas, leftchild(nodeindex), i, arr) ;
arr[i]=mas[nodeindex];

inorder(mas,  rightchild(nodeindex), i, arr);
}
     
     
int main () {

  
 int mas[93]={2,3,1,9,8,7,6,5};
 int arr[9];
inorder(mas, 0, 0, arr);

for (int k=0; k<10; k++)
cout <<"inorder " << arr[k] << endl;

    system("pause");
  return 0;
}

    



hey, all. this is my code for binary tree in array, for inorder traverse, i want put these nums in array, in inorder sequence,,,but it is not work
when i write cout, it works...there is somethink with i , i dont konow what

Is This A Good Question/Topic? 0
  • +

Replies To: binary tree in array

#2 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: binary tree in array

Posted 22 November 2010 - 02:17 PM

Your traversal of the tree is correct, but when you write to the output array you are always writing to the same element arr[0]. You can't send a constant array index to the recursive function. That index must be incremented by each node after it writes its own data. You need to send a reference (or pointer) to an index variable.

Added a few comments in the code below:

#include <iostream>

using namespace std;

int leftchild(int nodeindex) // returns the index of the left child
{
    return  nodeindex *2 + 1 ;
}

int rightchild(int nodeindex) // returns the index of the right child
{
    return nodeindex * 2 +2;
}


// changed i to a reference because left children must be able to increment it before node writes its own data
int inorder(int* mas, int nodeindex, int& i, int* arr) // a recursive function to print the nodes values, put in array
{
    if (mas[nodeindex] == 0) return 0 ;
    inorder(mas, leftchild(nodeindex), i, arr) ;
    arr[i]=mas[nodeindex];
                       
    inorder(mas,  rightchild(nodeindex), ++i, arr); // pre-incrementing the array index i for the right child
}


int main () {


    int mas[93]={2,3,1,9,8,7,6,5};  // only 8 non-zero elements
    int arr[9]={0}; // initializing arr; otherwise last element will be garbage
    int i = 0; // added index variable to pass to recursive function
    inorder(mas, 0, i, arr);

    for (int k=0; k<9; k++)   // k<9: you were overrunning the end of the array
        cout <<"inorder " << arr[k] << endl;

    system("pause");
    return 0;
}



Was This Post Helpful? 0
  • +
  • -

#3 zigurdis  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 15
  • Joined: 05-November 09

Re: binary tree in array

Posted 23 November 2010 - 10:03 AM

thanks ;)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1