当前位置： 首页 > news >正文

二叉树及其应用（增删改查）

news 来源：原创 2024/5/3 2:00:30

一、树的概念

树(tree)是n（n>0）个结点的有限集.在任何一个非空树中

        1）有且仅有一个特定的称为根的结点

        2）当n>1时，其余结点可分为m个互不相交的有限集T1、T2,,,Tm

        其中每个集合本身也是一颗树，叫根的子树

树的结点包含一个数据元素以及若干个指向其子树的分支

结点的度：结点拥有的子树的数量，称之为结点的度。度为0的结点称之为叶子结点或者终端结点。

度不为0的结点，称之为分支结点或者非终端结点

结点的层次：从根开始定义起，根为第一层，根的孩子为第二层，树中结点的最大层次叫树的深度或者高度

二、二叉树

二叉树是一种树状结构，它的特点是每个结点最多只有两颗子树，也就是二叉树不存在度大于2的结点。

并且二叉树的子树有左右之分，不能随意颠倒次序

二叉树的五种形态

1、空二叉树（一个结点都没有的二叉树）

2、只有一个根结点的二叉树

3、只有左子树

4、只有右子树

5、完全二叉树

 

三、二叉树的性质

1、在二叉树的第i层上至多有2^(i-1)个结点（i>=1）

2、深度为K的二叉树最多有(2^k)-1个结点

3、对于任意一颗二叉树，如果其终端节点数为n0，度为2的结点为n2，则有n2=n0-1

        1)满二叉树：一颗深度为K且具有(2^K)-1个结点的二叉树，满二叉树

        2)完全二叉树：满足以下条件的二叉树

                a:除去最后一层为满二叉树

                b：最后一层的结点必须依次从左往右紧密排列

练习：结点数699的完全二叉树的叶子结点（终端结点）的数量为多少？

2^9-1=511

699-511=188

K=9+1=10层

10层最多为1024

4、具有n个结点的完全二叉树的深度为(log2N)+1

四、二叉树的存储结构

1、顺序存储结构

把一颗普通二叉树，填补成完全二叉树，然后按自上向下，从左往右进行编号（可能造成浪费内存空间）

                                

                                       

 

2、链式存储结构

typedef int TElemType_t

struct BiTNode

{

TElemType_t data;//数据域

struct BiTNode *lchild;//left 存储当前结点的左子结点的地址

struct BiTNode *rchild;//right 存储当前结点的右子结点的地址

};

五、二叉树的遍历

如何按照某条搜索路径访问树中的每个结点，使每个结点都被访问一次，而且仅被访问一次

先序遍历：根 左 右

中序遍历：左 根 右

后序遍历：左 右 根

        1）先序 中序 后序都是针对“根”的位置来讲的

        2）若左右不是终端结点，则进去递归遍历

 

六、二叉排序树也叫二叉查找树

1、概念

二叉排序树，要么是空树，要么具有以下的性质的二叉树

1)若它的左子树不为空，则左子树上所有的结点的值都小于它的根结点

2)若它的右子树不为空，则右子树上所有的结点的值都大于它的根结点

3)它的左右子树也分别为二叉排序树

                                 

2、编程实现
1)设计

typedef int TElemType_t
typedef struct BiTNode
{
    TElemType_t data;//数据域
    struct BiTNode *lchild;//left 存储当前结点的左子结点的地址
    struct BiTNode *rchild;//right 存储当前结点的右子结点的地址
}BiTNode_t;
//在r为根结点的二叉排序树中,插入值为inputdata的结点
BiTNode_t *insert_nodeToTree(BiTNode_t *r,TElemType_t inputdata)
{
    //1.新建结点
    BiTNode_t *newNode=malloc(sizeof(BiTNode_t));
    if(newNode==NULL)
    {
        printf("malloc newNode error\n");
        return r;
    }
    //2.初始化新结点
    newNode->data=inputdata;
    newNode->lchild=newNode->rchild=NULL;
    //3.遍历二叉排序树，找到合适的位置插入新结点
    //1）从无到有----新结点就是树的根节点
    if(r==NULL)
    {
        r=newNode;
    }
    //2)从少到多
    else
    {
        BiTNode_t *p=r;
        while(p)
        {
            //插入的数据比当前遍历结点的数据小，那么就去当前结点左子树中查找
            if(inputdata<p->data)
            {
                //如果当前结点的左子结点为NULL，直接插入
                if(p->lchild==NULL)
                {
                    p->lchild=newNode;
                    break;//插入成功后退出
                }
                else//如果不为空，往下面遍历
                {
                   p=p->lchild;
                }
            }
            //插入的数据比当前遍历结点的数据大，那么就去当前结点右子树中查找
            else if(inputdata>p->data)
            {
                //如果当前结点的右子结点为NULL，直接插入
                if(p->rchild==NULL)
                {
                    p->rchild=newNode;
                    break;//插入成功后退出
                }
                else//如果不为空，往下面遍历
                {
                   p=p->rchild;
                }
            }
            //如果是相等的就直接退出
            else
            {
                printf("此时结点是相等的，冲突\n");
                free(newNode);
                break;
            }
        }
    }
    //4.返回根结点
    return r;
}


//2、创建二叉树排序树

BiTNode_t *create_sort_tree()
{
    BiTNode_t *r=NULL;
    //1、从键盘获取数据，将这个数据作为新结点的值，接着将新结点插入二叉树中
    printf("please inputData\n");
    while(1)
    {
        TElemType_t inputData;
        scanf("%d",&inputData);
        if(inputData==-1)
            break;
        //插入到二叉排序中
        r=insert_nodeToTree(r,inputData);
    }
    //返回根结点
    return r;
}


//先序遍历：根 左 右

void pre_allToTree(BiTNode_t *r)
{
    if(r==NULL)
        return;
    printf("%d",r->data);
    pre_allToTree(r->lchild);
    pre_allToTree(r->rchild);
}


//中序遍历：左 根 右

void mid_allToTree(BiTNode_t *r)
{
    
    if(r==NULL)
        return;
    pre_allToTree(r->lchild);
    printf("%d",r->data);
    pre_allToTree(r->rchild);
}


//后序遍历：左 右 根

void post_allToTree(BiTNode_t *r)
{
    if(r==NULL)
        return;
    pre_allToTree(r->lchild);
    pre_allToTree(r->rchild);
    printf("%d",r->data);
}


//查找

bool find_nodeToTree(BiTNode_t *r,TElemType_t findData)
{
    //1.先做判断
    if(r==NULL)
    return false;
    //遍历
    BiTNode_t *P=r;
    while(p)
    {
        if(findData==p->data)
            return true;
        else if(findData<p->data)
        {
            p=p->lchild;
        }
        else if(findData>p->data)
        {
            p=p->rchild;
        }
    }
    return true;
}

七、二叉树增删改查例子---demo.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>


typedef int TElemType_t;

typedef struct BiTNode
{
	TElemType_t data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode_t;

BiTNode_t *insert_nodeToTree(BiTNode_t *r,TElemType_t inputdata)
{
	BiTNode_t *newNode = malloc(sizeof(BiTNode_t));
	if(newNode == NULL)
	{
		printf("malloc newNode errror!\n");
		return r;
	}
	newNode->data = inputdata;
	newNode->lchild = NULL;
	newNode->rchild = NULL;
	
	if(r == NULL)
	{
		r = newNode;
	}
	else
	{
		BiTNode_t *p = r;
		while(p)
		{
			if(inputdata < p->data)
			{
				//如果当前结点的左子节点为NULL，直接插入
				if(p->lchild == NULL)
				{
					p->lchild = newNode;
					break;
				}
				else//如果不为NULL，往下遍历，找到为止
				{
					p = p->lchild;
				}
			}
			else if(inputdata > p->data)
			{
				//如果当前结点的右子节点为NULL，直接插入
				if(p->rchild == NULL)
				{
					p->rchild = newNode;
					break;
				}
				else//如果不为NULL，往下遍历，找到为止
				{
					p = p->rchild;
				}
			}
			else//相等,直接退出
			{
				printf("此时结点的值是相等的，直接退出！\n");
				free(newNode);
				break;
			}
		}
	}
	return r;//返回新结点
}

BiTNode_t *creat_sort_tree()
{
	BiTNode_t *r = NULL;
	
	printf("请输入你的数据：\n");
	while(1)
	{
		TElemType_t inputdata;
		scanf("%d",&inputdata);
		if(inputdata == -1)
			break;
		
		r = insert_nodeToTree(r,inputdata);
	}
	return r;
}

void pre_allToTree(BiTNode_t *r)//先序遍历：根->左->右
{
	if(r == NULL)
		return;
	printf("%d->",r->data);
	pre_allToTree(r->lchild);
	pre_allToTree(r->rchild);
}

void mid_allToTree(BiTNode_t *r)//中序遍历：左->根->右
{
	if(r == NULL)
		return;
	mid_allToTree(r->lchild);
	printf("%d->",r->data);
	mid_allToTree(r->rchild);
}

void last_allToTree(BiTNode_t *r)//后序遍历：左->右->根
{
	if(r == NULL)
		return;
	last_allToTree(r->lchild);
	last_allToTree(r->rchild);
	printf("%d->",r->data);
}

/*查找*/
bool find_nodeToTree(BiTNode_t *r,TElemType_t findData)
{
	if(r == NULL)
		return false;
	
	//遍历
	BiTNode_t *p = r;
	while(p)
	{
		if(findData == p->data)
			return true;
		else if(findData < p->data)
		{
			p = p->lchild;
		}
		else if(findData > p->data)
		{
			p = p->rchild;
		}
	}
	return false;
}

/*从根为r的二叉排序树中删除值为delData的结点*/
BiTNode_t *delete_nodeToTree(BiTNode_t *r, TElemType_t delData)
{
	printf("请输入要删除的数据：\n");
	scanf("%d",&delData);
	
	if(r == NULL)
		return r;
	//找到要删除的结点P和删除节点的上一个结点pre
	BiTNode_t *p = r;
	BiTNode_t *pre = NULL;
	while(p)
	{
		if(p->data == delData)
			break;
		else if(delData < p->data)
		{	
			pre = p;//先记录父节点
			p = p->lchild;
		}
		else if(delData > p->data)
		{	
			pre = p;//先记录父节点
			p = p->rchild;
		}
	}
	if(p == NULL)
	{
		printf("傻逼！没有这个数据找不到，无法删除！\n");
		return r;
	}
	else//找到这个待删除的节点
	{
		//不同情况不同的处理
		//1、(终端结点)删除节点没有左、右孩子
		if(p->lchild == NULL && p->rchild == NULL)
		{
			//(1)p是根节点，直接释放
			if(p == r)
			{
				free(p);
				return NULL;
			}
			//(2)p是父结点的左孩子，则p为NULL
			else if(p == pre->lchild)
			{
				pre->lchild = NULL;
				free(p);
			}
			//(3)p是父结点的左孩子，则p为NULL
			else if(p == pre->rchild)
			{
				pre->rchild = NULL;
				free(p);
			}
		}
		//2、删除结点有左、右孩子
		else if(p->lchild != NULL && p->rchild != NULL)
		{
			//方法：找到删除节点p的左子树中最大的结点p2，p2与删除节点交换数据，删除p2结点
			BiTNode_t *p2 = p->lchild;
			BiTNode_t *pre2 = p;
			while(p2->rchild)
			{
				pre2 = p2;
				p2 = p2->rchild;
			}
			//对p2位置不同的处理
			if(p2 == p->lchild)
			{
				//交换值
				TElemType_t temp = p->data;
				p->data = p2->data;
				p2->data = temp;
				
				p->lchild = p2->lchild;
				p2->lchild = NULL;//断开链接
				free(p2);
			}
			else
			{
				TElemType_t temp = p->data;
				p->data = p2->data;
				p2->data = temp;
				pre2->rchild = p2->lchild;
				p2->lchild = NULL;
				free(p2);
			}
			
		}
		//删除节点只有一个孩子
		else
		{
			//只有左孩子
			if(p->lchild)//p->lchild!=NULL
			{
				if(p == r)//情况1
				{
					r = p->lchild;
					p->lchild = NULL;//断开链接
					free(p);
				}
			
				else if(p == pre->lchild)//情况2
				{
					pre->lchild = p->lchild;
					p->lchild = NULL;
					free(p);
				}
				else if(p == pre->rchild)//情况3
				{
					pre->rchild = p->lchild;
					p->lchild = NULL;
					free(p);
				}
			}
			//只有右孩子
			else if(p->lchild)//p->rchild!=NULL
			{
				if(p == r)//情况1
				{
					r = p->lchild;
					p->lchild = NULL;//断开链接
					free(p);
				}
			
				if(p == pre->rchild)//情况2
				{
					pre->rchild = p->rchild;
					p->rchild = NULL;
					free(p);
				}
				else if(p == pre->lchild)//情况3
				{
					pre->lchild = p->rchild;
					p->rchild = NULL;
					free(p);
				}
			}
		}
	}
	return r;
}

int main(int argc,char *argv[])
{
	BiTNode_t *r = creat_sort_tree();
	printf("\n");
	pre_allToTree(r);
	printf("\n");
	
	TElemType_t delData;
	r = delete_nodeToTree(r,delData);
	pre_allToTree(r);
	printf("\n");
	// mid_allToTree(r);
	// printf("\n");
	// last_allToTree(r);
	// printf("\n");
	// if(find_nodeToTree(r,5))
		// printf("找到！\n");
	// else
		// printf("找不到！\n");
	
	return 0;
}

在gcc编译器下编译该代码，一次输入二叉树顺序数据下的运行结果：

相关文章：

  • 分库分表二：ShardingJDBC进阶实战案例上
  • ClickHouse(06)ClickHouse的数据表创建语句详细解析
  • 银纳米团簇-荧光Ag25团簇以及衍生团簇（直径1-2nm）
  • Jmeter-Windows环境配置
  • BZOJ4756 Promotion Counting（线段树合并）
  • 【重识云原生】第六章容器6.3.1节——K8S核心组件总述
  • python中常用的魔术方法总结（二）
  • 《Autosar_MCAL高阶配置》总目录_培训教程持续更新中...
  • python基础知识点
  • Python的collections原来这么好用
  • Python学习：encode()和decode()方法：字符串编码转换
  • Python深拷贝(deepcopy)、浅拷贝（copy）、等号拷贝的深入理解----看了还不懂找我
  • 【论文研读】-Defining the Ethereum Virtual Machine for Interactive Theorem Provers
  • HIVE 3 使用 MR 引擎多表关联 (JOIN) 导致丢数的问题复现、问题根源及解决方案 (附代码)
  • 计算机毕业设计Java网上求职招聘系统（源码+系统+mysql数据库+Lw文档）
  • JAVA 学习IO流
  • MySQL主从复制读写分离及奇怪的问题
  • PHP的类修饰符与访问修饰符
  • 从输入URL到页面加载发生了什么
  • 回顾2016
  • 那些被忽略的 JavaScript 数组方法细节
  • 吐槽Javascript系列二：数组中的splice和slice方法
  • 我看到的前端
  • 优化 Vue 项目编译文件大小
  • 由插件封装引出的一丢丢思考
  • 数据库巡检项
  • !$boo在php中什么意思,php前戏
  • #include＜初见C语言之指针（5）＞
  • #控制台大学课堂点名问题_课堂随机点名
  • #我与Java虚拟机的故事#连载12：一本书带我深入Java领域
  • (12)Hive调优——count distinct去重优化
  • （145）光线追踪距离场柔和阴影
  • （27）4.8 习题课
  • （3）nginx 配置(nginx.conf)
  • （Java岗）秋招打卡！一本学历拿下美团、阿里、快手、米哈游offer
  • (zt)基于Facebook和Flash平台的应用架构解析
  • （编译到47%失败）to be deleted
  • （顺序）容器的好伴侣 --- 容器适配器
  • （完整代码）R语言中利用SVM-RFE机器学习算法筛选关键因子
  • .NET CF命令行调试器MDbg入门（二） 设备模拟器
  • .net websocket 获取http登录的用户_如何解密浏览器的登录密码？获取浏览器内用户信息？...
  • .NET/C# 使用反射注册事件
  • .net程序集学习心得
  • .NET关于 跳过SSL中遇到的问题
  • .net和jar包windows服务部署
  • .net和php怎么连接,php和apache之间如何连接
  • .NET简谈互操作(五：基础知识之Dynamic平台调用)
  • .vue文件怎么使用_我在项目中是这样配置Vue的
  • @Autowired注解的实现原理
  • @我的前任是个极品 微博分析
  • [ Linux ] Linux信号概述 信号的产生
  • [] 与 [[]], -gt 与 ＞ 的比较
  • [20150321]索引空块的问题.txt
  • [ACTF2020 新生赛]Include
  • [Angular 基础] - 数据绑定(databinding)