二叉树基本操作 c++

硅谷探秘者 5130 0 0

二叉树基本操作 c++

class node{
public :
	int data;
	node * left;
	node * right;
	node();
	node(int data);
	node(int data,node * left,node * right);
};
#include "node.h"
class trytree{
private:
	node * head;
public:
	trytree();
	void add(int data);//添加二叉树节点
	void preprintf();//先序遍历
	void seqprintf();//中序遍历
	void subprintf();//后序遍历
	void del(int data);
	node * getnode(int data);
};
#include<iostream>
#include"trytree.h"
using namespace std;
node::node(int data){//初始化node节点
	this->data=data;
	this->left=NULL;
	this->right=NULL;
}
node::node(int data,node * left,node * right){
	this->data=data;
	this->left=left;
	this->right=right;
}
trytree::trytree(){//初始化树
	head=NULL;
}
void trytree::add(int data){//添加二叉树节点(easy)
	if(head==NULL){
		head=new node(data);
	}else{
		node * n=head;
		while(n!=NULL){
			if(data<n->data){//向左
				if(n->left!=NULL){//左方不为空
					n=n->left;
				}else{//左方为空
					node * l=new node(data);
					n->left=l;
					return ;
				}
			}else{//向右
				if(n->right!=NULL){
					n=n->right;
				}else{
					node * l=new node(data);
					n->right=l;
					return ;
				}
			}
		}
	}
}
void trytree::del(int data){//删除节点(较为复杂)
	node * n=head;
	node * parent;
	while(n!=NULL){//寻找待删除节点
		if(data>n->data){//向右找
			parent=n;
			n=n->right;
		}else if(data<n->data){//向左找
			parent=n;
			n=n->left;
		}else{//相等即待除节点
			if(n->left!=NULL&&n->right==NULL){//左节点不为空右节点为空
				if(parent->left==n){
					parent->left=n->left;
					delete(n);
					return;
				}else{
					parent->right=n->left;
					delete(n);
					return;
				}
			}else if(n->left==NULL&&n->right!=NULL){//右节点不为空左节点为空
				if(parent->left==n){
					parent->left=n->right;
					delete(n);
					return;
				}else{
					parent->right=n->right;
					delete(n);
					return;
				}
			}else if(n->left==NULL&&n->right==NULL){//待删除的节点为叶子节点
				if(parent->left==n){
					parent->left=NULL;
					delete(n);
					return;
				}else{
					parent->right=NULL;
					delete(n);
					return;
				}
			}else{//左右孩子节点都不为空
				node * sub=n->right;
				if(sub->left==NULL){//sub为后继节点
					sub->left=n->left;
					if(parent->left==n){
						parent->left=sub;
						delete(n);
						return;
					}else{
						parent->right=sub;
						delete(n);
						return;
					}
				}else{
					node * p=sub;//后继节点的父节点
					while(sub->left!=NULL){//寻找后继节点
						p=sub;
						sub=sub->left;
					}
					p->left=NULL;
					if(parent->left==n){
						sub->left=n->left;
						sub->right=n->right;
						parent->left=sub;
						delete(n);
						return;
					}else{
						sub->left=n->left;
						sub->right=n->right;
						parent->right=sub;
						delete(n);
						return;
					}	
				}
			}
		}
	}
	cout<<"没有找到"<<endl;
	return;
}
node * trytree::getnode(int data){
	node * n=head;
	while(n!=NULL){//寻找节点
		if(data>n->data){//向右找
			n=n->right;
		}else if(data<n->data){//向左找
			n=n->left;
		}else{//该节点
			return n;
		}
	}
	return NULL;
}
void pre(node * n){
	if(n==NULL){
		return;
	}
	cout<<n->data<<"  ";
	pre(n->left);
	pre(n->right);
}
void seq(node * n){
	if(n==NULL){
		return;
	}
	seq(n->left);
	cout<<n->data<<"  ";
	seq(n->right);
}
void sub(node * n){
	if(n==NULL){
		return;
	}
	sub(n->left);
	sub(n->right);
	cout<<n->data<<"  ";
}
void trytree::preprintf(){//先序遍历
	cout<<"先序遍历:";
	pre(head);
	cout<<endl;
}
void trytree::seqprintf(){//中序遍历
	cout<<"中序遍历:";
	seq(head);
	cout<<endl;
}
void trytree::subprintf(){//后序遍历
	cout<<"后序遍历:";
	sub(head);
	cout<<endl;
}
int main(){//测试
	trytree * t=new trytree();
	t->add(10);
	t->add(4);
	t->add(20);
	t->add(2);
	t->add(6);
	t->add(15);
	t->add(30);
	t->add(18);
	t->add(25);
	t->del(25);
	t->preprintf();
	t->seqprintf();
	t->subprintf();
	cout<<endl;
	cout<<t->getnode(10)->data<<endl;
	return 0;
}

image.png


评论区
请写下您的评论...
暂无评论...
猜你喜欢
数据结构与算法 2489 链式队列的c++classnode{public:intdata;node*next;node*prev;};#include"node.h"classqueue{private:node
数据结构与算法 3433 删除节点c++先看一个简单的图删除节点是分以下几种情况:1.待删节点为叶子节点:此种情况下直接删除叶子节点即可2.待删节点只有左子,或只有右子,那么将左子或右子的根节点替换该节点即可
数据结构与算法 3088 链式栈的出栈入栈c++描述于双向链表//节点classnode{public:intdata;node*next;node*prev;};//双向链表#include"node.h
official 1044 题中,一棵高度平衡定义为:一个每个节点的左右两个子的高度差的绝对值不超过1。示例1案例输入:root=[3,9,20,null,null,15,7],输出:true示例2案例输入:r
linux系统 3763 ctrl+c和ctrl+z都是中断命令,但是他们的用却不一样.ctrl+c强制中断程序ctrl+z的是将任务中断,挂起的状态,ctrl+c是强制中断程序的执行。ctrl+z的是将任务中断.但是此任
数据结构与算法 4248 ),任一节点的平衡因子是-1,0,1之一2.avlAVL查找一样,这里我们关注的是两个变化很大的:插入和删除!AVL不仅是一颗查找,它还有其他的性质。如果我们按照一般
数据结构与算法 3096 packageavlTree;importjava.util.LinkedList;/***avl(平衡)*@authorAdministrator**/publicclassAvlTree
weblog 3923 值类型的传值参数方法执行时会为实参创建一个副,方法内改变形参的值时不会改变实参的值。引用类型的传值参数方法会为实参创建一个副引用,形参和实参指向的是同一个对象的内存地址,当形参引用的内存地址改变
归档
2018-11  12 2018-12  33 2019-01  28 2019-02  28 2019-03  32 2019-04  27 2019-05  33 2019-06  6 2019-07  12 2019-08  12 2019-09  21 2019-10  8 2019-11  15 2019-12  25 2020-01  9 2020-02  5 2020-03  16 2020-04  4 2020-06  1 2020-07  7 2020-08  13 2020-09  9 2020-10  5 2020-12  3 2021-01  1 2021-02  5 2021-03  7 2021-04  4 2021-05  4 2021-06  1 2021-07  7 2021-08  2 2021-09  8 2021-10  9 2021-11  16 2021-12  14 2022-01  7 2022-05  1 2022-08  3 2022-09  2 2022-10  2 2022-12  5 2023-01  3 2023-02  1 2023-03  4 2023-04  2 2023-06  3 2023-07  4 2023-08  1 2023-10  1 2024-02  1 2024-03  1 2024-04  1
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础 xxl-job rabbitmq haproxy srs 音视频 webrtc javascript
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。