开发者社区> 问答> 正文

数据结构(二叉树的插入与删除) 400 请求报错 

定义一个10个元素(25,12,10,15,55,60,45,70,11,13)的数组以二叉树结构存储,在排序过后删除其中任意元素,删除55的过程中出错,请大家帮忙看看问题,谢谢...

//Tree.h
#include<iostream>
using namespace std;
#ifndef TREE_H
#define TREE_H

template<class T>
class Tree
{
public:
	Tree();
	bool insert(const T& x);
	bool search(const T& x) const;
	bool deleteItem(const T& x);
	void display() const;
private:
	struct TreeNode
	{
		T item;
		TreeNode* left;
		TreeNode* right;
	};
	TreeNode* root;
	bool insert(TreeNode*& aroot,const T& x);
	bool search(TreeNode* aroot,const T& x) const;
	bool deleteItem(TreeNode*& aroot,const T& x);
	void display(TreeNode* aroot) const;
};
#endif

template<class T>
Tree<T>::Tree()
{
	root = NULL;
}

template<class T>
bool Tree<T>::insert(const T& x)
{
	return insert(root,x);
}

template<class T>
bool Tree<T>::search(const T& x) const
{
	return search(root,x);
}

template<class T>
bool Tree<T>::deleteItem(const T& x)
{
	return deleteItem(root,x);
}

template<class T>
void Tree<T>::display() const
{
	display(root);
	cout << endl;
}

template<class T>
bool Tree<T>::insert(TreeNode*& aroot, const T& x)
{
	if(aroot == NULL)
	{
		aroot = new TreeNode;
		aroot -> left = NULL;
		aroot -> right = NULL;
		aroot -> item = x;
		return true;
	}
	else if(aroot -> item == x)
	{
		cout << "元素已存在!" << endl;
		return false;
	}
	else if(aroot -> item > x)
		return insert(aroot -> left,x);
	else
		return insert(aroot -> right,x);
}

template<class T>
bool Tree<T>::search(TreeNode* aroot, const T& x) const
{
	if(aroot == NULL)
	{
		cout << "未找到" << endl;
		return false;
	}
	else if(aroot -> item == x)
	{
		cout << "已找到!" << endl;
		return true;
	}
	else if(aroot -> item > x)
		return search(aroot -> left,x);
	else
		return search(aroot -> right,x);
}

template<class T>
bool Tree<T>::deleteItem(TreeNode*& aroot, const T& x)
{
	if(aroot == NULL)
	{
		cout << "没有要删除的元素!" << endl;
		return false;
	}
	else if(aroot != NULL && aroot -> item == x)
	{
		TreeNode* oldNode = aroot;
		if(aroot -> left == NULL)
		{
			if(aroot -> right == NULL)
			{
				aroot = NULL;
				oldNode = NULL;
				delete aroot;
				delete oldNode;
				return true;
			}
			else
			{	
				oldNode = NULL;
				aroot = aroot -> right;
				aroot -> right = aroot -> right;
				delete oldNode;
				return true;
			}
		}
		else if(aroot -> right == NULL)
		{
			if(aroot -> left == NULL)
			{
				aroot = NULL;
				oldNode = NULL;
				delete oldNode;
				delete aroot;
				return true;
			}
			else
			{
				oldNode = NULL;
				aroot = aroot -> left;
				aroot -> left = aroot -> left;
				delete oldNode;
				return true;
			}
		}
		else 
		{
			TreeNode* newNode = aroot;
			oldNode = NULL;
			aroot = aroot -> left;
			aroot -> left = aroot -> left;
			aroot -> right = aroot -> right;
			if(newNode -> right != NULL)
				aroot -> right -> right = newNode -> right;
			delete oldNode;
			return true;
		}
	}
	else if(aroot -> item > x)
		return deleteItem(aroot -> left,x);
	else
		return deleteItem(aroot -> right,x);
}

template<class T>
void Tree<T>::display(TreeNode *aroot) const
{
	if(aroot != NULL)
	{
		display(aroot -> left);
		cout << aroot -> item << " ";
		display(aroot -> right);
	}
}
//Tree.cpp
#include<iostream>
#include"Tree.h"
using namespace std;

typedef Tree<int> Treelist;
int main()
{
	Treelist tl;
	int a[10] = {25,12,10,15,55,60,45,70,11,13};

	for(int i = 0;i < 10;i++)
		tl.insert(a[i]);
	tl.display();
	tl.deleteItem(12);
	tl.display();
	system("pause");
	return 0;
}

展开
收起
kun坤 2020-05-30 15:10:16 757 0
1 条回答
写回答
取消 提交回答
  • 看不懂,cplusplus?######是的,就是声明一个模版类,然后插入数值,二叉树进行排序以后删除其他元素都行,就是删除55出错,或者你有什么好方法么?######删除之后仍然要保持有序么?######

    1. aroot = NULL;  
    2.                 oldNode = NULL;  
    3.                 delete aroot;  
    4.                 delete oldNode;
    5. //这代码问题很大,先置NULL,再delete,还存在重复delete的问题,好好查查吧
    ######是的,要保持有序,行,我再看看,谢谢...######155行--157行逻辑混乱了 aroot = aroot -> left; // 这时aroot已经改变成了原来的左枝  aroot -> left = aroot -> left;   // 这个就成了自己给自己原来的左枝 aroot -> right = aroot -> right;  // 这个就成了自己给自己原来的右而你构建的二叉树在这是          55   45          60 null null        70 那肯定出错了 而且删除也是有问题的,删除应该是保存了当前节点的上一级节点,将当前节点的下一级节点接到上一级节点上,然后删除当前节点,否则会出现断链,程序运行出错。 另外楼主没有重写一个拷贝函数,还要注意浅拷贝的问题。 ######说下自己的看法,(没有在机器上调试,如果有误请指出)。 代码写的有点儿小问题: 释放内存的时候是先delete,后指针赋空,否则泄漏. 下面的这种写法似乎没有什么效果吧: aroot -> left = aroot -> left;  aroot -> right = aroot -> right; 再说下思路,主要是delete操作。 当二叉树建成后,要delete一个结点。 如果结点没有左孩子,直接用右孩子替代要删除的结点。 如果没有右孩子,则直接用左孩子替代要删除的结点。 如果左右孩子同时存在,把左孩子放到  右孩子的最左边的叶子结点。 以上。######template<class T> bool Tree<T>::deleteItem(TreeNode*& aroot,const T& x) {     if (NULL == aroot)     {         cout << "Can't find item" << endl;     }     else     {         if (aroot->item == x)         {             if (aroot->left == NULL)             {                 TreeNode* p = aroot;                 aroot = aroot->right;                 delete p;                 p = NULL;             }             else if(aroot->right == NULL)             {                 TreeNode* p = aroot;                 aroot = aroot->left;                 delete p;                 p = NULL;             }             else             {                 TreeNode* p = aroot->right;                 while(NULL != p->left)                 {                     p = p->left;                 }                 p->left = aroot->left;                 p = aroot;                 aroot = aroot->right;                 delete p;                 p = NULL;             }         }         else if (aroot->item > x)             deleteItem(aroot->left, x);         else             deleteItem(aroot->right, x);     }     return true; }######恩,明白了,谢谢大家的帮助...######

    引用来自#9楼“晓寒”的帖子

    template bool Tree::deleteItem(TreeNode*& aroot,const T& x) {     if (NULL == aroot)     {         cout << "Can't find item" << endl;     }     else     {         if (aroot->item == x)         {             if (aroot->left == NULL)             {                 TreeNode* p = aroot;                 aroot = aroot->right;                 delete p;                 p = NULL;             }             else if(aroot->right == NULL)             {                 TreeNode* p = aroot;                 aroot = aroot->left;                 delete p;                 p = NULL;             }             else             {                 TreeNode* p = aroot->right;                 while(NULL != p->left)                 {                     p = p->left;                 }                 p->left = aroot->left;                 p = aroot;                 aroot = aroot->right;                 delete p;                 p = NULL;             }         }         else if (aroot->item > x)             deleteItem(aroot->left, x);         else             deleteItem(aroot->right, x);     }     return true; } 这种删除节点做法也是错误的。 当前节点如果有左右枝,而当前节点的上一个节点有左右枝,这个就不是简单的将当前节点的左右枝挂到上一节点的问题了。 楼主构建的树是这样的                                    25                         12                    55                     10    15            45       60                                                           70 考虑删除55这个节点,显然45和60是不能同时挂到25下的。应该将60挂到25的右枝,45挂到60的左枝。注意还要考虑60下本来就有左枝的情况。 删除后应该是  

                                       25

                            12                    60

                        10    15            45       70

    或者

     

                                       25

                            12                   45

                        10    15                      60

                                                              70

    也可以。

    因此当要删除节点55时应该有一个指针指在25上(注意这个25不一定就是root),这样才能完成将原来55下的节点挂到25下的操作。

    2020-05-30 15:10:40
    赞同 展开评论 打赏
问答分类:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
如何使用Tair增强数据结构构建丰富在线实时场景 立即下载
Apache Flink 流式应用中状态的数据结构定义升级 立即下载
低代码开发师(初级)实战教程 立即下载