【数据结构与算法】二叉树的创建,插入,遍历,删除,删除节点实现

标签: 二叉树

二叉树是每个结点最多有两个子树的树结构。使用广泛,使用C来实现对二叉树的操作。

示例:代码实现构造如下二叉树

#include <iostream>

using namespace std;

typedef struct  BinaryTree
{
	int data;
	struct BinaryTree* lchild;
	struct BinaryTree* rchild;
}BiTNode;


/************************************
@ Brief:		二叉树中插入节点
@ Author:		woniu201 
@ Created:		2019/07/10
@ Return:            
************************************/
void insertNode(BiTNode** node, int val)
{
	BiTNode* tmpNode = NULL;
	if (!(* node))
	{
		tmpNode = (BiTNode*)malloc(sizeof(BiTNode));
		memset(tmpNode, 0, sizeof(BiTNode));
		tmpNode->data = val;
		*node = tmpNode;
		return;
	}
	if (val < (*node)->data)
	{
		insertNode(&(*node)->lchild, val);
	}
	else if (val > (*node)->data)
	{
		insertNode(&(*node)->rchild, val);
	}
	return;
}

/************************************
@ Brief:		删除节点
@ Author:		woniu201
@ Created:		2019/07/10
@ Return:       参考:https://blog.csdn.net/Future_LL/article/details/79968437
************************************/
void delNode(BiTNode* node, int val)
{
	BiTNode *L, *LL;    //在删除左右子树都有的结点时使用;  
	BiTNode *p = node;
	BiTNode *parent = node;
	
	int child = 0;  //0表示左子树,1表示右子树;  
	
	if (!node)    //如果排序树为空,则退出;  
	{
		return;
	}	
	while (p)  //二叉排序树有效;  
	{
		if (p->data == val)
		{
			if (!p->lchild && !p->rchild)  //叶结点(左右子树都为空);  
			{
				if (p == node)  //被删除的结点只有根结点;  
					free(p);
				else if (child == 0)
				{
					parent->lchild = NULL;  //设置父结点左子树为空;  
					free(p);   //释放结点空间;  
				}
				else   //父结点为右子树;  
				{
					parent->rchild = NULL;  //设置父结点右子树为空;  
					free(p);  //释放结点空间;  
				}
			}

			else if (!p->lchild)  //左子树为空,右子树不为空;  
			{
				if (child == 0)    //是父结点的左子树;  
					parent->lchild = p->rchild;
				else      //是父结点的右子树;  
					parent->rchild = p->rchild;
				free(p);  //释放被删除的结点;  
			}

			else if (!p->rchild)  //右子树为空,左子树不为空;  
			{
				if (child == 0)  //是父结点的左子树;  
					parent->lchild = p->lchild;
				else      //是父结点的右子树;  
					parent->rchild = p->lchild;
				free(p);  //释放被删除的结点;  
			}

			else
			{
				LL = p;  //保存左子树的结点;  
				L = p->rchild;  //从当前结点的右子树进行查找;  
				if (L->lchild)  //左子树不为空;  
				{
					LL = L;
					L = L->lchild;   //查找左子树;  
					p->data = L->data;  //将左子树的数据保存到被删除结点;  
					LL->lchild = L->lchild;  //设置父结点的左子树指针为空;  
					for (; L->lchild; L = L->lchild);
					L->lchild = p->lchild;
					p->lchild = NULL;
				}
				else
				{
					p->data = L->data;
					LL->rchild = L->rchild;
				}
			}
			p = NULL;
		}
		else if (val < p->data)  //需删除记录的关键字小于结点的数据;  
		{
			//要删除的结点p是parent的左子树;  
			child = 0;  //标记在当前结点左子树;  
			parent = p;//保存当前结点作为父结点;  
			p = p->lchild;  //查找左子树;  
		}
		else  //需删除记录的关键字大于结点的数据;  
		{
			//要删除的结点p是parent的右子树;  
			child = 1;  //标记在当前结点右子树查找;  
			parent = p;  //保存当前结点作为父结点;  
			p = p->rchild;  //查找右子树;  
		}
	}
	return;
}

/************************************
@ Brief:		删除树
@ Author:		woniu201 
@ Created:		2019/07/10
@ Return:            
************************************/
void delTree(BiTNode* node)
{
	if (node)
	{
		delTree(node->lchild);
		delTree(node->rchild);
		free(node);
		node = NULL;
	}
}

/************************************
@ Brief:		前序遍历
@ Author:		woniu201 
@ Created:		2019/07/10
@ Return:            
************************************/
void proorder(BiTNode* node)
{
	if (node)
	{
		printf("%d	", node->data);
		proorder(node->lchild);
		proorder(node->rchild);
	}
}

/************************************
@ Brief:		中序遍历
@ Author:		woniu201 
@ Created:		2019/07/10
@ Return:            
************************************/
void inorder(BiTNode* node)
{
	if (node)
	{
		inorder(node->lchild);
		printf("%d	", node->data);
		inorder(node->rchild);
	}
}

/************************************
@ Brief:		后序遍历
@ Author:		woniu201 
@ Created:		2019/07/10
@ Return:            
************************************/
void postorder(BiTNode* node)
{
	if (node)
	{
		postorder(node->lchild);
		postorder(node->rchild);
		printf("%d	", node->data);
	}
}

int main()
{
	BiTNode* node = NULL;
	insertNode(&node, 10);
	insertNode(&node, 15);
	insertNode(&node, 8);
	insertNode(&node, 9);
	insertNode(&node, 17);
	insertNode(&node, 6);
	insertNode(&node, 11);

	//前序遍历
	printf("先序遍历:\n");
	proorder(node);

	//中序遍历
	printf("\n中序遍历:\n");
	inorder(node);


	//后序遍历
	printf("\n后序遍历:\n");
	postorder(node);

	//删除节点
	delNode(node, 15);

	//删除树
	delTree(node);

	return 1;
}

版权声明:本文为woniu211111原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/woniu211111/article/details/95333540

智能推荐

说说 Python Django 应用的基础目录结构

通过以下 django-admin 指令创建应用之后,就会生成应用的基础目录结构。 比如,我们建立了一个叫 ‘first’ 的应用,它的目录结构是这样的: 目录或文件 说明 最外层的 first/ 这是新应用的根目录,所有与该应用相关的内容都放在这里。 manage.py 用于管理 Django 项目的命令行工具。 里面一层的 first/ 目录 是一个...

Springboot整合rabbitMQ

依赖: 配置文件application.yml RabbitConfig 消息生产者RabbitProducer 消息消费者RabbitCustomer 通过Controller进行调用 启动项目后调用接口: 结果:...

Thread.join()方法的使用

如果一个线程A执行了thread.join()语句,代表当前线程A等待thread线程终止后才从thread.join()方法返回 并且这个方法具有超时特性,可以添加参数设置 输出结果: jdk中Thread.join()方法的源码(进行了部门调整)   每个线程终止的条件是前驱线程的终止,每个线程等待前驱线程终止后,才从join()方法返回,  当线程终止时,会调用自身的no...

linux服务器部署jenkins笔记

安装jenkins参考文档:https://blog.csdn.net/tomatocc/article/details/83930714 1. 打开jenkins官网:https://jenkins.io/download/ 将war包下载到本地 **ps:**这里要注意的是要下载左边下方的war包,不要下载右边下面的war包。左边是稳定版本,右边是最新版本,建议大家使用稳定版本(我刚开始下载的...

k8s部署elasticsearch集群

百度营销大学     环境准备 我们使用的k8s和ceph环境见: https://blog.51cto.com/leejia/2495558 https://blog.51cto.com/leejia/2499684 ECK简介 Elastic Cloud on Kubernetes,这是一款基于 Kubernetes Operator 模式的新型编排产品,用户可使用该产品在...

猜你喜欢

saas-export项目-AdminLTE介绍与入门

AdminLTE介绍 (1)AdminLTE是什么? AdminLTE是一款建立在bootstrap和jquery之上的开源的模板主题工具 (2)AdminLTE有什么特点? 提供一系列响应的、可重复使用的组件, 并内置了多个模板页面 自适应多种屏幕分辨率,兼容PC和移动端 快速的创建一个响应式的Html5网站 AdminLTE 不但美观, 而且可以免去写很大CSS与JS的工作量 AdminLTE...

MyBatis中ResultMap结果集映射

用于解决属性名和字段名不一致的情况: resultMap 元素是 MyBatis 中最重要最强大的元素。...

编写一个shell

编写shell的过程: 1.从标准输入中读入一个字符串。 2.解析字符串 3.创建一个子进程的执行程序。 4.子进程程序替换。 5.父进程等待子进程退出。...

WEB自动化测试中Xpath定位方法

前言: Xpath是在XML文档中查找信息的一种语言,使用路径表达式来选取XML文档中的节点或节点集,由于XML与HTML结构类似(前者用于传输数据,后者用于显示数据),所以Xpath也常用于查找HTML文档中的节点或节点集。 一  路径表达式: 路径以“/”开始     表示找到满足该绝对路径的元素; 路径以//”开始  ...

力扣困难难度 第4题 寻找两个正序数组的中位数

先看一眼题 我的思路: 设置下标i,j分别用于遍历两个数组,初始值均为0,直到找到两个数组中从小到大的第第length/2个数为止结束循环,length为两个数组长度之和。 ·每次比较nums[i]nums[j],如果前者小则i++,否则j++ ·循环结束时,如果count已经达到length/2,则说明已经找到了中位数,[注意:此时有可能正好其中一个数组遍历完了!所以...