二叉树模板,蒟蒻求调
  • 板块学术版
  • 楼主isop
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/3/30 10:40
  • 上次更新2024/3/30 13:10:51
查看原帖
二叉树模板,蒟蒻求调
1071516
isop楼主2024/3/30 10:40

插入之后无异常,但删除操作之后遍历跑不出来

#include<bits/stdc++.h>
using namespace std;
struct Tree
{
	int data;
	Tree *left;	
	Tree *right;
	Tree(int w=0):data(w),left(NULL),right(NULL){}
}tree;

inline Tree* setup(int w)//建树(节点) 
{
	Tree* root=new Tree;
	root->data=w;
	root->left=root->right=NULL;
	return root;
}

void remove(Tree* &root,int x)//删除 
{

	
	Tree* find=root;
	Tree* father=NULL;
	
	while(find!=NULL && find->data != x)
	{
		father=find;
		if(find->data>x) find=find->left;
		else find=find->right;
	}
	if(find==NULL) return;//没有找到 
	
	if(find->left != NULL && find->right != NULL)//有2子 
	{
		Tree* findright=find->right;
		Tree* finddata=find;
		while(findright->left !=NULL)//找最小右节点 
		{
			finddata=findright;
			findright=findright->left;
		}
		find->data=findright->data;
		find=findright;
		father=finddata;
	}
	
	Tree* child;//单子节点或无子节点
	if(find->left!=NULL) child=find->left;
	else if(find->right!=NULL) child=find->right;
	else child=NULL;
	
	if(father=NULL) root=child;
	else if(father->left==find) father->left=child;
	else father->right=child;
}

void insert(Tree* &root,int x)
{
	//插入
	if(root==NULL)
	{
		root=setup(x);
		return ;
	}
	if(root->data > x) insert(root->left,x);
	else insert(root->right,x);
}

void preorder(Tree* root)//前序 
{
	if(root==NULL) return;
	cout<<root->data<<" ";
	preorder(root->left);
	preorder(root->right);
}

void postorder(Tree* root)//中序 
{
	if(root==NULL) return;
	postorder(root->left);
	postorder(root->right);
	cout<<root->data<<" ";
}

void inorder(Tree* root)//后序 
{
	if(root==NULL) return;
	inorder(root->left);
	cout<<root->data<<" ";
	inorder(root->right);
}

int main()
{
	Tree* tree=NULL;
	int n;
	cin>>n;
	
	for(int i=0;i<n;i++)
	{	
		int x;
		cin>>x;
		insert(tree,x);
	}
	cout<<"操作前:"<<endl; 
	preorder(tree);//插入前 
	cout<<endl;
	inorder(tree);
	cout<<endl;
	postorder(tree);
	cout<<endl;

	int x;
	cout<<"插入:"; 
	cin>>x;
	insert(tree,x);
	
	int f;
	cout<<"删除:";
	cin>>f;
	remove(tree,f);
	
	cout<<"操作后:"<<endl; 
	preorder(tree);//插入后 
	cout<<endl;
	inorder(tree);
	cout<<endl;
	postorder(tree);
	cout<<endl;
 } 
/*data:
8
23 45 12 6 7 89 13 47
insert 17
romove 17
*/  
2024/3/30 10:40
加载中...