使用动态数组的二叉树 [英] binary trees using dynamic arrays
问题描述
按照以下URL中的规范设计和实现二叉树的类http://www.cs.colorado.edu/~main/chapter10/bt_class.h
您的设计应该使用动态数组来保存节点中的数据，方式与通常表示完整二叉树的方式相同。但是，这些二叉树不需要完整。相反，您应该有第二个私有成员变量，它是一个名为is_present的布尔值的动态数组。 is_present数组指示树中实际存在哪些节点。例如，如果树具有根节点，则位置is_present [0]为真。如果根有左子，则is_present [1]为真。如果root有一个正确的孩子，那么is_present [2]是真的。
这里是我的代码，我需要有人来帮助我纠正它：
Design and implement a class for binary trees, following the specification at the following URL http://www.cs.colorado.edu/~main/chapter10/bt_class.h
Your design should use a dynamic array to hold the data from the nodes in the same way that a complete binary tree is usually represented. However, these binary trees do not need to be complete. Instead, you should have a second private member variable that is a dynamic array of Boolean values called is_present. The is_present array indicates which nodes actually exist in the tree. For example, if the tree has a root node, then location is_present[0] is true. If the root has a left child, then is_present[1] is true. If the root has a right child, then is_present[2] is true.
here is my code and i need someone to help me correct it :
#include <<iostream>>
using namespace std;
class binary_tree
{
public:
binary_tree( );
void create_first_node(const int entry);
void shift_to_root( );
void shift_up( );
void shift_left( );
void shift_right( );
void change(const int entry);
void add_left(const int entry);
void add_right(const int entry);
int size( );
void print();
int retrieve( ) ;
bool has_parent( ) ;
bool has_left_child( ) ;
bool has_right_child( ) ;
private:
int no_leaves;
int current_node;
int* BT;
bool* is_present;
};
binary_tree::binary_tree( ){
no_leaves=0;
current_node=0;
BT=NULL;
is_present=false;
}
void binary_tree::create_first_node(const int entry)
{
//tree must be empty to insert the first node
if (size()==0){
BT=new int [10];
BT[0]=entry;
cout<<BT[0]<<" is the first node"<<endl; //creates new node and inserts as root ptr
is_present=new bool[true];
is_present[0]=true;
//update current node
no_leaves++;
} //tree has one node
else return;
}
void binary_tree::shift_to_root( ){
if(size()>0)
current_node=0;
}
void binary_tree::shift_up( ){
if(has_parent()==true){
current_node=current_node/2;
}
else return;
}
void binary_tree::shift_left( )
{
if( has_left_child() == true)
{ //must have left child to shift left
//current node is now the left child of the original current node
current_node=2*current_node+1;
}
else return;
}
void binary_tree::shift_right( )
{
if(has_right_child() == true){//must have right child to shift right
//current node is now the right child of original current node
current_node=2*current_node+2;
}
else return;
}
bool binary_tree::has_left_child( )
{
if( size()>0 && (2*current_node+1)!=0)
{
//current node has a left child
is_present[2*current_node+1]=true;
return true;
}
else
//current node does not have left child
return false;
}
bool binary_tree::has_right_child( )
{
if( size()>0 && (2*current_node+2)!=0)
{
//current node has right child
is_present[2*current_node+2]=true;
return true;
}
else
//current node does not have right child
return false;
}
bool binary_tree::has_parent( )
{
if( size() > 0 && current_node==0)
{
//root node does not have a parent
return false;
}
else{
is_present[current_node/2]=true;
//all other nodes have parents
return true;
}
}
void binary_tree::add_left(const int entry)
{
//tree must be nonempty
//current node must not have left child
if( size()> 0 && has_left_child()==true){
//create new left child node
BT[2*current_node+1]= entry;
int e=entry;
cout<<e<<" is added to the left"<<endl;
//update number of nodes in tree
no_leaves++;
}
else cout<<" nothing changed"<<endl;
}
void binary_tree::add_right(const int entry)
{
//tree must be nonempty
//current node cannot have right child
if( size()> 0 && has_right_child()==true){
BT[2*current_node+2]= entry;
int e=entry;
cout<<e<<" is added to the right"<<endl;
//update number of nodes in tree
no_leaves++;
}
else cout<<"nothing changed"<<endl;
}
void binary_tree::change(const int entry)
{
if(size() > 0){ //must have nonempty tree
//the current node's data is changed to the new entry
BT[current_node]=entry;
}
}
int binary_tree::size( )
{
//return number of nodes in tree
return no_leaves;
}
int binary_tree::retrieve( )
{
if( size()> 0){
cout<<BT[current_node]<<" value of the current node"<<endl;
return BT[current_node];
//returns data from current node
}
else return 0;
}
void binary_tree:: print(){
cout<<"BT array: ";
for(int i=0;i<size();i++){>
cout<<BT[i]<<" ";
}
cout<<endl;
cout<<"is_present array: ";
for(int j=0;j<size();j++){>
cout<<is_present[j]<<" ";
}
}
int main (void){
binary_tree b1;
b1.create_first_node(3);
b1.add_left(2);
b1.shift_left();
b1.retrieve();
b1.print();
return 0;
}
推荐答案
好吧，祝你好自己的功课。
Well, good luck with your own homework.
这篇关于使用动态数组的二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
