C++ RSS C++ RSS

complete binary tree using an array help

Please support our C++ advertiser: Intel Parallel Studio Home
Thread Solved

•
•
Join Date: Jul 2006
Posts: 32
Reputation: schmidty169 is an unknown quantity at this point 
Solved Threads: 0
schmidty169's Avatar
schmidty169 schmidty169 is offline Offline
Light Poster

complete binary tree using an array help

 
0
  #1
Jul 16th, 2006
This is what I have to do
We will initialize the tree by hard coding the values illustrated below. You will need to write, test and execute a driver program that will use the complete binary tree implementation.

// this will initialize the tree node values
treenodes[0]=5;
treenodes[1]=10;
treenodes[2]=2;
treenodes[3]=5;
treenodes[4]=7;
treenodes[5]=12;
treenodes[6]=3;
treenodes[7]=9;
treenodes[8]=8;
treesize=9;
print leftchild(3);
print height();
print isleaf(7);
print isleaf(2);
print parent(5);
traverseinorder();
This is what I got:
C++ Syntax (Toggle Plain Text) 
  1. // CPP btree.cpp : Defines the entry point for the console application.
  2. //
  3.  
  4. #include "stdafx.h"
  5.  
  6. class BTree 
  7. {
  8. public:
  9.         int treenodes[1000];  // structure to store the tree nodes values
  10.  
  11.         int size;  // the number of nodes in the tree
  12.  
  13.         BTree(void);  // the "constructor"
  14.  
  15.         bool isleaf(int nodeindex);  // returns true if the node is a leaf
  16.         int parent(int nodeindex);  // returns the index of the parent
  17.         int leftchild(int nodeindex);  // returns the index of the left child
  18.         int rightchild(int nodeindex);  // returns the index of the right child
  19.  
  20.         int height();  // returns the height of the tree
  21.         int traverseinorder(int);  // a recursive function to print the nodes values based on an inorder traversal
  22. };
  23.  
  24. bool BTree::isleaf(int nodeindex) //returns true if the node is a leaf
  25. {
  26.     return (BTree::leftchild(nodeindex)==NULL && BTree::rightchild(nodeindex)==NULL) ;
  27. }
  28.  
  29. int BTree::parent(int nodeindex)  // returns the index of the parent
  30. {
  31.         int rv =0; 
  32.  
  33.     rv = (nodeindex - 1) / 2; 
  34.     if (rv >= size)  
  35.         rv = -1 ;
  36.  
  37.     return rv ;
  38. }
  39.  
  40. int BTree::leftchild(int nodeindex)  // returns the index of the left child
  41. {
  42.     int rv =0; 
  43.  
  44.     rv = (nodeindex +1) *2 - 1; 
  45.     if (rv >= size)  
  46.         rv = -1 ;
  47.  
  48.     return rv ;
  49. }
  50.  
  51. int BTree::rightchild(int nodeindex)  // returns the index of the right child
  52. {
  53.     int rv =0; 
  54.  
  55.     rv = (nodeindex +1) * 2; 
  56.     if (rv <= size)  
  57.         rv = -1 ;
  58.  
  59.     return rv ;
  60. }
  61.  
  62. int BTree::traverseinorder(int nodeindex)  // a recursive function to print the nodes values based on an inorder traversal
  63. {
  64.     if (nodeindex == -1)  return -1 ;
  65.     return traverseinorder(leftchild(nodeindex)) ;
  66.  
  67.     //print the treenode values 
  68.     cout << "Tree node " << nodeindex << " = " << treenodes[nodeindex] << endl;
  69.  
  70.     traverseinorder(rightchild(nodeindex)); 
  71. }
  72.  // end traverseinorder()
  73.  
  74. int BTree::height()
  75. {
  76.     return 0;
  77. }  
  78.  
  79. int main(int argc, char* argv[])
  80. {
  81.     BTree tree1;
  82.  
  83.         tree1.treenodes[0]=5;
  84.         tree1.treenodes[1]=10;
  85.         tree1.treenodes[2]=2;
  86.         tree1.treenodes[3]=5;
  87.         tree1.treenodes[4]=7;
  88.         tree1.treenodes[5]=12;
  89.         tree1.treenodes[6]=3;
  90.         tree1.treenodes[7]=9;
  91.         tree1.treenodes[8]=8;
  92.  
  93.         //set the size here.  size is a member of the bTree class so we need our object.member syntax
  94.         tree1.size = 9;
  95.  
  96.         cout << "The left child of node 3 is:  " << tree1.leftchild(3) << endl;
  97.         //cout << "The height of the tree is:    " << tree1.height() << endl;
  98.         cout << "The node 7 is a leaf:         " << tree1.isleaf(7) << endl;
  99.         cout << "The node 2 is a leaf:         " << tree1.isleaf(2) << endl;
  100.         cout << "The parent of node 5 is:      " << tree1.parent(5) << endl;
  101.  
  102.         cout << "Values for inorder traversal: " <<  endl;
  103.         cout << tree1.traverseinorder(0);
  104.  
  105.         return 0;
  106. }

If I put in the Btree(void); it get CPP btree error LNK2019: unresolved external symbol "public: __thiscall BTree::BTree(void)" (??0BTree@@QAE@XZ) referenced in function _main
Ok so I take it out. With it out I have a few problems with the inordertraversal. One if I take out the search of the rightchild it works. If I put in the rightchild it gives me really wierd values. I even tried to take out the left and all I get on the right in 0 = 5? This tells me I'm getting a rightside tree. I still don't have the height done either.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jul 2006
Posts: 32
Reputation: schmidty169 is an unknown quantity at this point 
Solved Threads: 0
schmidty169's Avatar
schmidty169 schmidty169 is offline Offline
Light Poster

Re: complete binary tree using an array help

 
0
  #2
Jul 16th, 2006
I solved the height
C++ Syntax (Toggle Plain Text) 
  1. int BTree::height()
  2. {
  3.  
  4.     return sizeof(leftchild(0));
  5. }
Reply With Quote Quick reply to this message  
•
•
Join Date: Jul 2006
Posts: 32
Reputation: schmidty169 is an unknown quantity at this point 
Solved Threads: 0
schmidty169's Avatar
schmidty169 schmidty169 is offline Offline
Light Poster

Re: complete binary tree using an array help

 
0
  #3
Jul 17th, 2006
Ok I took care of the overload error by adding
C++ Syntax (Toggle Plain Text) 
  1. BTree::BTree(void)  // builds the "constructor"
  2. {
  3.     for(int i = 0; i < 1000; ++i) treenodes[i] = -1;
  4. }
But the inorder traversal still has a problem. I don't think it is the traversal but something with how the right side is not being built right. If I take out the traverseinorder(rightchild(nodeindex)); then the left side displays perfect to the root. If I run the traverseinorder(rightchild(nodeindex)); only I get only the root.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jul 2006
Posts: 32
Reputation: schmidty169 is an unknown quantity at this point 
Solved Threads: 0
schmidty169's Avatar
schmidty169 schmidty169 is offline Offline
Light Poster

Re: complete binary tree using an array help

 
0
  #4
Jul 18th, 2006
C++ Syntax (Toggle Plain Text) 
  1. // CPP btree.cpp : Defines the entry point for the console application.
  2. //
  3.  
  4. #include "stdafx.h"
  5.  
  6. class BTree 
  7. {
  8. public:
  9.         int treenodes[1000];  // structure to store the tree nodes values
  10.  
  11.         int size;  // the number of nodes in the tree
  12.         int count;            // the number of filled nodes in the tree
  13.         int level;            // the current depth
  14.  
  15.         BTree(void);  // the "constructor"
  16.  
  17.         bool isleaf(int nodeindex);  // returns true if the node is a leaf
  18.         int parent(int nodeindex);  // returns the index of the parent
  19.         int leftchild(int nodeindex);  // returns the index of the left child
  20.         int rightchild(int nodeindex);  // returns the index of the right child
  21.  
  22.         int height();  // returns the height of the tree
  23.         int traverseinorder(int);  // a recursive function to print the nodes values based on an inorder traversal
  24. };
  25.  
  26. BTree::BTree(void)  // builds the "constructor"
  27. : size(sizeof(treenodes)/sizeof(int))
  28.     , count(0)
  29.     , level(0)
  30. {
  31.     for(int i = 0; i < size; ++i)
  32.         treenodes[i] = -1;   // set all nodes empty
  33. }
  34.  
  35. bool BTree::isleaf(int nodeindex) //returns true if the node is a leaf
  36. {
  37.     return leftchild(nodeindex)==-1 && rightchild(nodeindex)==-1;
  38. }
  39.  
  40. int BTree::parent(int nodeindex)  // returns the index of the parent
  41. {
  42.     int rv = (nodeindex - 1) / 2;
  43.  
  44.     return (rv >= size || treenodes[rv] == -1)? -1 : rv;
  45. }
  46.  
  47. int BTree::leftchild(int nodeindex)  // returns the index of the left child
  48. {
  49.     int rv = (nodeindex +1) *2 - 1;
  50.  
  51.     return (rv >= size || treenodes[rv] == -1)? -1 : rv;
  52. }
  53.  
  54. int BTree::rightchild(int nodeindex)  // returns the index of the right child
  55. {
  56.     int rv = (nodeindex +1) * 2;
  57.  
  58.     return (rv >= size || treenodes[rv] == -1)? -1 : rv;
  59. }
  60.  
  61. int BTree::traverseinorder(int nodeindex)  // a recursive function to print the nodes values based on an inorder traversal
  62. {
  63.     if (nodeindex == -1)  return -1 ;
  64.         traverseinorder(leftchild(nodeindex));
  65.  
  66.      //print the treenode values
  67.      cout << "Tree node " << nodeindex << " = " << treenodes[nodeindex] << endl;
  68.  
  69.      traverseinorder(rightchild(nodeindex)); 
  70. }
  71.  // end traverseinorder()
  72.  
  73. int BTree::height()
  74. {
  75.     return level;
  76. }  
  77.  
  78. int main(int argc, char* argv[])
  79. {
  80.     BTree tree1;
  81.  
  82.         tree1.treenodes[0]=5;
  83.         tree1.treenodes[1]=10;
  84.         tree1.treenodes[2]=2;
  85.         tree1.treenodes[3]=5;
  86.         tree1.treenodes[4]=7;
  87.         tree1.treenodes[5]=12;
  88.         tree1.treenodes[6]=3;
  89.         tree1.treenodes[7]=9;
  90.         tree1.treenodes[8]=8;
  91.  
  92.         //set the size here.  size is a member of the bTree class so we need our object.member syntax
  93.         tree1.size = 9;
  94.  
  95.         cout << "The left child of node 3 is:  " << tree1.leftchild(3) << endl;
  96.         cout << "The height of the tree is:    " << tree1.height() << endl;
  97.         cout << "The node 7 is a leaf:         " << tree1.isleaf(7) << endl;
  98.         cout << "The node 2 is a leaf:         " << tree1.isleaf(2) << endl;
  99.         cout << "The parent of node 5 is:      " << tree1.parent(5) << endl;
  100.  
  101.         cout << "Values for inorder traversal: " <<  endl;
  102.         tree1.traverseinorder(0);
  103.  
  104.         return 0;
  105. }
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread has been marked solved.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the C++ Forum
Thread Tools Search this Thread



api array based beginner binary bitmap c++ c/c++ calculator char char* class code coding compile compiler console conversion count database delete deploy desktop developer directshow dll download dynamic dynamiccharacterarray email encryption error file forms fstream function functions game givemetehcodez google graph gui homeworkhelp homeworkhelper iamthwee ifstream input int java lib linkedlist linker list loop looping loops map math memory multiple news node number numbertoword output parameter pointer problem program programming project python random read recursion recursive reference rpg sorting string strings temperature template templates test text text-file tree unix url variable vector video visualstudio win32 windows winsock word wordfrequency wxwidgets
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC