每天一点数据结构之二叉树的查找和删除

旧城等待， 2022-08-22 06:30 53阅读 0赞

# 每天一点数据结构之二叉树的查找 #

一.二叉树的查找我将它分为两类，一类是满足左子树的值小于根小于右子树，那么可以根据这个特性去查找会比较高效。

从根节点开始查找，如果当前值等于根则返回，如果小于根则沿左子树继续查找，如果大于根则沿右子树继续查找，直到找到为止，否则返回null。

BinaryTree.prototype.searchBalanceTree = function (data)
    {
    	var current = this.root;
    	while (current != null)
    	{
    		if (current.data == data)
    		{
    			return current;
    		}
    		else if (current.data > data)
    		{
    			current = current.left;
    		}
    		else 
    		{
    			current = current.right;
    		}
    	}
    	return null;
    }

但是如果二叉树并不满足这个条件，那么就通过二叉树的遍历去查找了。先序，中序，后序都ok，这里就不附代码了。

二.二叉树的删除

二叉树的删除其实是最复杂的，列举一个简单的思路：

1.先找到要删除的结点

2.该结点一般分为两种类型

3.一种是无子树，或者只有一个子树，这种情况比较好处理，得到该结点的父结点，让父结点指向空或者改结点的子结点即可

4.第二种情况比较复杂，该结点有左右子树，我们沿该结点的左子树查找到它的左子树中的最大值，将这个结点称为max结点，用max结点的值替换要删除的结点的值，然后删除掉max结点即可。为什么要这么做，因为max结点必然在树的边缘（满足左子树小于根小于右子树的情况下），所以最多只有一颗子树，能有效的避免有两个子树无法处理的问题。

二叉树的删除就暂时总结这么多，代码还没有调好![难过][sad.gif]，就不上代码了~ 关于二叉树的删除以后再继续学习~

[sad.gif]: /images/20220722/85db739ad396430da6c6473a1cda5524.png

发表评论取消回复

表情：

评论列表（有 0 条评论，53人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构（二叉树查找）——二叉排序树的构造和查找、插入、删除

设计一个读入一串整数，然后构造二叉排序树，进行查找、插入、删除。 include <stdio.h> include <stdlib.h> defin

待我称王封你为后i/ 2022年12月24日 11:51/ 0 赞/ 172 阅读

相关每天一点数据结构之二叉树的查找和删除

每天一点数据结构之二叉树的查找一.二叉树的查找我将它分为两类，一类是满足左子树的值小于根小于右子树，那么可以根据这个特性去查找会比较高效。从根节点开始查找，如果当前

旧城等待，/ 2022年08月22日 06:30/ 0 赞/ 54 阅读

相关每天一点数据结构之二叉树的插入与创建

每天一点数据结构之二叉树的插入与创建二叉树的插入： 1.判断树是否为空，如果为空则直接插入当前结点成为根结点 2.若根不为空，则判断是否小于根 3.小于根插入左

阳光穿透心脏的1/2处/ 2022年08月22日 05:49/ 0 赞/ 60 阅读

相关每天一点数据结构之二叉树非递归遍历

用js实现的二叉树非递归遍历即使是做前端，发现自己的数据结构还是很薄弱，所以每天学习一点数据结构吧！今天学习了二叉树的非递归遍历。一：先序遍历主要思路：通

我不是女神ヾ/ 2022年08月22日 03:59/ 0 赞/ 79 阅读

相关数据结构实验之查找一：二叉排序树

数据结构实验之查找一：二叉排序树 Time Limit: 400ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述对应

港控/mmm°/ 2022年08月18日 02:11/ 0 赞/ 155 阅读

相关数据结构实验之查找一：二叉排序树

数据结构实验之查找一：二叉排序树 Time Limit: 400MS Memory Limit: 65536KB [Submit][] [Statist

梦里梦外;/ 2022年07月14日 14:45/ 0 赞/ 211 阅读

相关数据结构实验之查找一：二叉排序树

Problem Description 对应给定的一个序列可以唯一确定一棵二叉排序树。然而，一棵给定的二叉排序树却可以由多种不同的序列得到。例如分别按照序列\{3,1,4

ゝ一纸荒年。/ 2022年07月14日 13:16/ 0 赞/ 162 阅读

相关数据结构实验之查找一：二叉排序树

数据结构实验之查找一：二叉排序树 Time Limit: 400MS Memory Limit: 65536KB [Submit][] [Statistic][]

ゝ一纸荒年。/ 2022年07月14日 08:19/ 0 赞/ 179 阅读

相关数据结构实验之查找一：二叉排序树

think: 1 判断两个二叉搜索树是否相同的函数中注意判断二叉搜索树rt1和二叉搜索树rt2是否为空 [sdut原题链接][sdut] 数据结构实验之查找一：二叉排序

╰半夏微凉°/ 2022年07月12日 02:58/ 0 赞/ 171 阅读

相关数据结构实验之查找一：二叉排序树

数据结构实验之查找一：二叉排序树 Time Limit: 400MS Memory Limit: 65536KB Submit Statistic Problem

谁践踏了优雅/ 2022年06月03日 00:46/ 0 赞/ 177 阅读