二叉树基本操作 c++

硅谷探秘者 3984 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

猜你喜欢
数据结构与算法 1430 链式队列的c++classnode{public:intdata;node*next;node*prev;};#include"node.h"classqueue{private:node
数据结构与算法 1911 删除节点c++先看一个简单的图删除节点是分以下几种情况:1.待删节点为叶子节点:此种情况下直接删除叶子节点即可2.待删节点只有左子,或只有右子,那么将左子或右子的根节点替换该节点即可
数据结构与算法 2121 链式栈的出栈入栈c++描述于双向链表//节点classnode{public:intdata;node*next;node*prev;};//双向链表#include"node.h
official 148 题中,一棵高度平衡定义为:一个每个节点的左右两个子的高度差的绝对值不超过1。示例1案例输入:root=[3,9,20,null,null,15,7],输出:true示例2案例输入:r
linux系统 2488 ctrl+c和ctrl+z都是中断命令,但是他们的用却不一样.ctrl+c强制中断程序ctrl+z的是将任务中断,挂起的状态,ctrl+c是强制中断程序的执行。ctrl+z的是将任务中断.但是此任
数据结构与算法 3245 ),任一节点的平衡因子是-1,0,1之一2.avlAVL查找一样,这里我们关注的是两个变化很大的:插入和删除!AVL不仅是一颗查找,它还有其他的性质。如果我们按照一般
数据结构与算法 2068 packageavlTree;importjava.util.LinkedList;/***avl(平衡)*@authorAdministrator**/publicclassAvlTree
official 127 和一个head为第一个节点的链表。如果在中,存在一条一直向下的路径,且每个点的数值恰好一一对应以head为首的链表中每个节点的值,那么请你返回True,否则返回False。一直向下的路径的意思
归档
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
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo
目录