二叉树基本操作 c++
二叉树基本操作 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;
}
猜你喜欢
blog
链式队列的基本操作 c++
数据结构与算法
1262
链式队列的基本操作c++classnode{public:intdata;node*next;node*prev;};#include"node.h"classqueue{private:node
blog
二叉树删除节点 c++
数据结构与算法
1610
二叉树删除节点c++先看一个简单的树图删除节点是分以下几种情况:1.待删节点为叶子节点:此种情况下直接删除叶子节点即可2.待删节点只有左子树,或只有右子树,那么将左子树或右子树的根节点替换该节点即可
blog
链式栈的出栈入栈操作c++描述
数据结构与算法
1894
链式栈的出栈入栈操作c++描述基于双向链表//节点classnode{public:intdata;node*next;node*prev;};//双向链表#include"node.h
ofc
平衡二叉树
official
13
树。本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。示例1案例输入:root=[3,9,20,null,null,15,7],输出:true示例2案例输入:r
blog
avl树的旋转
数据结构与算法
3013
),任一节点的平衡因子是-1,0,1之一2.avl树的操作AVL树的操作基本和二叉查找树一样,这里我们关注的是两个变化很大的操作:插入和删除!AVL树不仅是一颗二叉查找树,它还有其他的性质。如果我们按照一般
linux系统
2242
ctrl+c和ctrl+z都是中断命令,但是他们的作用却不一样.ctrl+c强制中断程序ctrl+z的是将任务中断,挂起的状态,ctrl+c是强制中断程序的执行。ctrl+z的是将任务中断.但是此任
blog
avl树的插入和删除操作
数据结构与算法
1851
packageavlTree;importjava.util.LinkedList;/***avl树(平衡二叉树)*@authorAdministrator**/publicclassAvlTree
ofc
c#方法参数传值问题
weblog
3049
值类型的传值参数方法执行时会为实参创建一个副本,方法内改变形参的值时不会改变实参的值。引用类型的传值参数方法会为实参创建一个副本引用,形参和实参指向的是同一个对象的内存地址,当形参引用的内存地址改变
最近发表
归档
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月
4
标签
算法基础
linux
前端
c++
数据结构
框架
数据库
计算机基础
储备知识
java基础
ASM
其他
深入理解java虚拟机
nginx
git
undefined
undefined
sdf
sdf
dsdf
sdfasdfasd
sdf
ppp
sdf
fggdgsd
kkk
kkk
kkk
sdddf
456