Delete from binary tree
May 26, 2012 at 10:52am UTC
Hi,
I was trying to hands on binary tree. I was able to successfully create and print the binary.But when I trying to delete node than it is going to infinite loop.
I could not resolve this issue. any input into below program.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152
/* Height of tree :Number of element */
#include<iostream>
using namespace std;
class node
{
public :
int data;
node *left;
node *right;
};
class tree
{
public :
node *root;
tree();
void create_tree(int data);
void print_path(node *root);
int height_tree(node *root);
void delete_tree(int data);
};
tree::tree()
{
root=NULL;
}
void tree::create_tree(int data)
{
cout<<"create" <<endl;
node *temp = new node;
temp->data = data;
temp->left =NULL;
temp->right =NULL;
if (root==NULL)
root=temp;
else
{
node *p=root;
node *trail =NULL;
while (p!=NULL)
{
trail=p;
if (p->data > data)
p=p->left;
else
p=p->right;
}
if (trail->data > data)
trail->left = temp;
else
trail->right = temp;
}
}
void tree::print_path(node *root)
{
if (root!=NULL)
{
print_path(root->left);
cout<<root->data<<" " ;
print_path(root->right);
}
}
int tree::height_tree(node *root)
{
if (root==NULL)
return 0;
else
return (height_tree(root->left)+1+height_tree(root->right));
}
void tree::delete_tree(int data)
{
node *p=root;
node *trail =NULL;
while (p!=NULL)
{
trail=p;
if (p->data > data)
p=p->left;
else if (p->data < data)
p=p->right;
else if (p->data == data)
{
cout<<"data match" ;
break ;
}
else
{
cout<<"data did not find" ;
break ;
}
}
if (trail->left ==NULL)
{
node *temp=trail;
trail=trail->right;
delete temp;
}
else if (trail->right ==NULL)
{
node *temp =trail;
trail=trail->left;
delete temp;
}
else
{
if (trail->left !=NULL && trail->right !=NULL)
{
node *temp = trail->right;
cout<<temp->data<<endl;
while (temp->left!=NULL)
temp=temp->left;
temp->left = trail->left;
temp=trail;
trail=trail->right;
cout<<temp->data<<endl;
cout<<trail->data<<endl;
delete temp;
}
}
}
int main()
{
tree t;
t.create_tree(10);
t.create_tree(5);
t.create_tree(3);
t.create_tree(8);
t.create_tree(15);
t.create_tree(17);
t.print_path(t.root);
cout<<"height :" <<t.height_tree(t.root);
t.delete_tree(5);
t.print_path(t.root);
}
Last edited on May 26, 2012 at 11:13am UTC
May 26, 2012 at 1:42pm UTC
After the 81-98 loop both p and trail have the same data. It could be null, or the node to be deleted.
Then you are screwed, as you cannot adjust the links
Lines 102, 108 and 125 do nothing.
May 26, 2012 at 1:58pm UTC
Any suggestion to fix this issue. I have gone through the book and try to implement algorithm in c++. or my delete_tree function is completely wrong which need to write again
May 26, 2012 at 2:27pm UTC
You need to be able to link them, so don't stop where you find the data, but on its parent.
Topic archived. No new replies allowed.