1. If the deleted node has no subtree, delete it directly and modify the pointer of the corresponding parent node to be empty.
2. For the case where there is only one subtree, consider taking its child tree as its parent node's child tree. Whether it is left or right, it is determined based on the deleted node.
3. The most complicated thing is that there are two sub-numbers. You can consider two methods, both of which are the same idea: use the rightmost node of the left sub-tree of node A or the leftmost node of the right sub-tree of A as the node of A, and modify the pointer of the parent node of the corresponding leftmost or rightmost node. The modification method is similar to 2, and there is no detailed discussion.
/***************Delete of nodes in binary tree************/
/*********This program describes the process from recursively building a binary tree to finding *******/
/********* and the entire process of deletion can also be regarded as the previous few **********/
/*********Combined learning and summary of the program***************************/
#include<>
#include<>
#define Maxsize 16
//Define the binary tree node
struct treenode
{
int data;
struct treenode* left;
struct treenode* right;
};
typedef treenode Node;
typedef Node* btree;
//Recursively create a binary tree
btree create_btree(int* nodelist,int postion)
{
btree newnode;
if(nodelist[postion]==0||postion>=Maxsize)
return NULL;
else
{
newnode=(btree) malloc(sizeof(Node));
newnode->data=nodelist[postion];
newnode->left=create_btree(nodelist,postion*2);
newnode->right=create_btree(nodelist,postion*2+1);
return newnode;
}
}
/*********Looking for nodes of binary tree*********/
btree search(btree root,int node)
{
btree point;
point=root;
if(point==NULL)
return root;
else
if(point->data==node)
return point;
else
if(point->data>node)
search(point->left,node);
else
search(point->right,node);
}
/*********The second search method is to record the value of its parent node**********/
btree binary_search(btree point,int node,int *postion)
{
btree parent;
parent=point;
*postion=0;
while(point!=NULL)
{
if(point->data==node)
return parent;
else
{
parent=point;
if(point->data>node)
{
point=point->left;
*postion=-1;
}
else
{
point=point->right;
*postion=1;
}
}
}
return NULL;
}
/************Operation of deleting binary tree node***************/
btree deletenode(btree root,int node)
{
btree parent;
btree point;
btree child;
int postion;
parent=binary_search(root,node,&postion);
//The binary tree is empty
if(parent==NULL)
return root;
else
{
switch(postion)
{ case -1:point=parent->left;break;
case 1 :point=parent->right;break;
case 0 :point=parent;break;
}
if(point->left==NULL&&point->right==NULL)
{
switch(postion)
{
case -1:parent->left=NULL;break;
case 1:parent->right=NULL;break;
case 0:parent=NULL;break;
}
free(point);
return root;
}
if(point->left==NULL&&point->right!=NULL)
{
if(postion==-1)
parent->left=point->right;
else
if(postion==1)
parent->right=point->right;
else
root=root->right;
free(point);
return root;
}
if(point->left!=NULL&&point->right==NULL)
{
if(postion==-1)
parent->left=point->left;
else
if(postion==1)
parent->right=point->left;
else
root=root->left;
return root;
}
if(point->left!=NULL&& point->right!=NULL)
{
parent=point;
child=point->left;
while(child->right!=NULL)
{
parent=child;
child=child->right;
}
point->data=child->data;
if(parent->left=child)
parent->left=child->left;
else
parent->right=child->left;
free(child);
return root;
}
}
}
/*********In-order traversal binary tree******************/
void Inorder(btree point)
{
if(point!=NULL)
{
Inorder(point->left);
printf("[%2d]",point->data);
Inorder(point->right);
}
}
/********* Main program test function***************/
void main()
{
btree root=NULL;
int deletetree;
int nodelist[16]={0,5,4,6,2,0,0,8,1,3,0,0,0,0,7,9};
root=create_btree(nodelist,1);
printf("/n the original tree is");
Inorder(root);
printf("/n");
printf("Input the value of the number /n");
int test;
scanf("%d",&test);
root=deletenode(root,test);
printf("/n the deleted tree is /n");
Inorder(root);
printf("/n");
}