树(tree) [一]

树(tree) [一]

基本概念:

​ 日常生活中,很多数据的组织形式本质上是一棵树。比如一个公司中的职员层级关系、一个学校中的院系层级关系、淘汰赛中的各次比赛队伍、一个家族中的族谱成员关系等都是树状逻辑结构。由于树状结构表现出来都是具有层次的,因此也被称为层次结构。

树是一种非线性结构(一对多),其严格的数学定义是:如果一组数据中除了第一个节点(第一个节点称为根节点,没有直接前驱节点)之外,其余任意节点有且仅有一个直接前驱,有零个或多个直接后继==,这样的一组数据形成一棵树。树中的数据元素之间的逻辑关系是一对多的。

​ 树就是n个结点的有限集,当n=0的时候,此时树就被称为空树任意的非空树中有且只有一个特定的结点,该结点被称为根或称为根结点,也就是n = 1。

​ 当n>1的时候,其余的结点可以分为m个(m>1)互不相交的有限集 T1、T2、T3.........Tm ,每个集合也被称为一棵树,就是根的子树

​ 对于树状结构,除了*根结点*之外,其余的结点都可以分为多个不相交的*子树*,具体如下所示:

​ 可以看到,结点A就是根结点,根结点A下面有两个子树,分别是子树B和子树H,另外结点B和H都是根结点A的子结点。

​ 如果一个结点有子树,则该结点就被称为子树的“*双亲*”,该结点的子树就被称为结点的“*孩子*”,另外,具有相同结点的子树就被称为“*兄弟*”。如下图所示:

​ 可以看到,结点D的祖先为A、B、C,结点G的祖先为H、A,另外对于子树B而言,结点C、D、E、F都是结点B的子孙。

  • 树是分层结构,一般把树的根结点称为第一层,其余的子结点的层次就是在上一层的基础上+1,另外一般把树的最大层数称为*树的深度*树的深度也被称为树的高度

二叉树:

概念:

​ 二叉树是另一种树状结构,*二叉树的特点就是每个结点至多有两颗子树*(每个结点的度不会超过2),并且二叉树的子树是*有左右之分*,如果有两颗子树,就分别叫做左子树和右子树,而且二叉树的子树是有次序的,不能随意更改的,所以*二叉树也属于有序树*,也就意味着哪怕二叉树只有一个子树,也要区分到底是左子树还是右子树

​ 二叉树也是n个(n>=0)结点的有限集,一般二叉树有5种形式,分别是空树、根结点(ROOT)、有根结点和左子树以及右子树、左子树(Left Child Tree)右子树(Right Child Tree)

二叉树分类:

  • 斜树:

    ​ 一般只有左子树的二叉树被称为*左斜树*,一般只有右子树的二叉树被称为*右斜树*,可以看到斜树退化为线性结构,所以斜树是没有体现二叉树的性能

  • 满二叉树

  • 完全二叉树:

​ 对于一颗树而言,完全二叉树指的是只有树的最下面2层的结点的度可以小于2,并且结点的编号也是按照从上到下,从左到右的顺序进行排列,最下面一层的叶子结点都集中在左树。

注意: 满二叉树一定是完全二叉树,但是完全二叉树不一定是满二叉树

  • 二叉查找树:

​ 二叉查找树英文缩写为*BST树*(Binary Search Tree),一般也被称为二叉搜索树或者二叉排序树,二叉查找树的结点是有*键值key的*,如果二叉查找树不是空树则需要遵循以下的特点:

  1. 如果二叉查找树有左子树,则左子树的结点的键值key要小于左子树的根结点的键值key
  2. 如果二叉查找树有右子树,则右子树的结点的键值key要大于右子树的根结点的键值key
  3. 对于二叉查找树而言,左子树和右子树也分别是二叉查找树。

可以看到,左子树的结点的键值都是小于右子树,二叉查找树的结点的键值key是不重复

  • 平衡二叉树:

​ 平衡二叉树也是有序树,指的是树中任一结点的左子树和右子树的深度之差不超过1,如下图所示:

二叉树的性质:

  • *非空二叉树中的叶子结点数量等于双分支结点数量+1*双分支结点指的是就是度为2的结点,假设二叉树的叶子结点数量为n0,二叉树中单分支结点的数量为n1,二叉树中双分支结点的数量为n2,则二叉树中结点的总数 = n0 + n1 + n2。

​ 可以看到,上图二叉查找树中叶子结点的数量为3,度为1的结点的数量为1,度为2的结点数量为2,所以该二叉查找树的结点总数为6,和图中结点数量一致。

  • 二叉树的第i层上*最多*有2的(i - 1)次方(i≥1)个结点,因为二叉树结点最多的情况就是满二叉树。

​ 可以看到,满二叉树此时一共有4层,也就是二叉树的高度为4,假设要计算二叉树第4层的结点数量,则带入公式之后得到的结果为8,和图中结点数量一致。

  • 高度为h的二叉树*最多*有2的h次方 - 1(h≥1)个结点。满二叉树就是结点最多的二叉树,所以换句话说,满二叉树前h层结点的数量为2的h次方 - 1(h≥1)

二叉树的存储结构

  • 顺序结构

​ 二叉树的顺序结构就是采用一组地址连续的内存单元(数组)按照从上到下,从左到右的顺序依次存储二叉树中的结点,也就是把二叉树中编号为i的结点存储在数组下标为i-1的元素空间中。

​ 如果按照二叉树的性质而言,满二叉树以及完全二叉树使用顺序存储比较合适,好处是可以最大程序的节约内存空间,并且可以利用数组下标查找数据

​ 对于一般的二叉树而言,也可以使用顺序结构进行存储,为了可以使用数组来表示结点的逻辑关系,需要数组的一些元素空间来存储空结点,会导致浪费空间。0表示不存在的空结点如下图所示:

  • 链式结构

    ​ 链式结构就可以有效的解决数组中存储空结点的问题,链式结构不受内存的限制,由于一个结点最多可能存在两个子结点,所以应该采用双向不循环链表的方案来实现。

二叉树的遍历说明

​ 通过遍历二叉树可以得到二叉树的所有信息,对二叉树做出全面的了解,对于二叉树遍历结点而言,绝大多数是采用二叉查找树(BST树)来实现,接下来就以二叉查找树为例进行讲解:

/********************************************************************************************************
*
*
* 设计BST二叉查找树的接口,为了方便对二叉树进行节点的增删,所以采用双向不循环链表实现,每个节点内部都需要
* 有2个指针,分别指向该节点的左子树(lchild)和右子树(rchild)
*
* 
*
* Copyright (c)  2023-2024   cececlmx@126.com   All right Reserved
* ******************************************************************************************************/
//指的是BST树中的结点有效键值的数据类型,用户可以根据需要进行修改
typedef int  DataType_t;


//构造BST树的结点,BST树中所有结点的数据类型应该是相同的
typedef struct BSTreeNode
{
	DataType_t  		 data; 	//节点的键值
	struct BSTreeNode	*lchild; 	//左子树的指针域
	struct BSTreeNode	*rchild; 	//右子树的指针域

}BSTnode_t;

  1. 创建BST树的根节点,并完成根节点的初始化

    //创建一个带根节点的BST树,对BST树的根节点进行初始化
    BSTnode_t * BSTree_Create(DataType_t KeyVal)
    {
    	//1.创建一个根结点并对根结点申请内存
    	BSTnode_t *Root = (BSTnode_t *)calloc(1,sizeof(BSTnode_t));
    	if (NULL == Root)
    	{
    		perror("Calloc memory for Root is Failed");
    		exit(-1);
    	}
    
    	//2.对根结点进行初始化,根节点的2个指针域分别指向NULL
    	Root->data = KeyVal;
    	Root->lchild = NULL;
    	Root->rchild = NULL;
    
    	//3.把根结点的地址返回即可
    	return Root;
    }
    
  2. 创建BST树中新的节点,并完成其的初始化(数据域 + 指针域)

    //创建新的结点,并对新结点进行初始化(数据域 + 指针域)
    BSTnode_t * BSTree_NewNode(DataType_t KeyVal)
    {
    	//1.创建一个新结点并对新结点申请内存
    	BSTnode_t *New = (BSTnode_t *)calloc(1,sizeof(BSTnode_t));
    	if (NULL == New)
    	{
    		perror("Calloc memory for NewNode is Failed");
    		return NULL;
    	}
    
    	//2.对新结点的数据域和指针域(2个)进行初始化
    	New->data = KeyVal;
    	New->lchild = NULL;
    	New->rchild = NULL;
    
    	return New;
    }
    
    
  3. 向BST树中加入节点 并且要遵循BST树的特点。即:根节点的左子树的键值都是比根节点小的,根节点的右子树的键值都是比根节点大的

    //向BST树中加入节点   规则:根节点的左子树的键值都是比根节点小的,根节点的右子树的键值都是比根节点大的
    bool BSTree_InsertNode(BSTnode_t *Root,DataType_t KeyVal)
    {
    
    	//为了避免根节点地址丢失,所以需要对地址进行备份
    	BSTnode_t *Proot = Root;
    
    
    	//1.创建新节点并对新结点进行初始化
    	BSTnode_t * New = BSTree_NewNode(KeyVal);
    	if (NULL == New)
    	{
    		printf("Create NewNode Error\n");
    		return false;
    	}
    
    	//2.此时分析当前的BST树是否为空树,有2种情况(空树 or 非空树)
    	if (NULL == Root)
    	{
    		//此时BST树为空树,则直接把新节点作为BST树的根节点
    		Root = New;
    	}
    	else
    	{
    		while(Proot)
    		{
    			
    			//新节点的键值和根节点的键值进行比较,如果相等则终止函数
    			//因为BST树不能存有相同的树
    			if (Proot->data == New->data)
    			{
    				printf("Can Not Insert,.....\n");
    				return false;
    			}
    			//新节点的键值和根节点的键值进行比较,如果不相等继续分析
    			else
    			{
    				//新节点的键值小于根节点的键值,则把根节点的左子树作为新的根
    				if( New->data < Proot->data )
    				{
    					//如果左边子树为空,则直接插入新的节点
    					if (Proot->lchild == NULL)
    					{
    						Proot->lchild = New;
    						break;
    					}
    
    					Proot = Proot->lchild;
    
    				}
    				else
    				{
    					//如果右边子树为空,则直接插入新的节点
    					if (Proot->rchild == NULL)
    					{
    						Proot->rchild = New;
    						break;
    					}
    
    					Proot = Proot->rchild;
    				}
    			}
    		}
    
    	}
    
    	return true;
    }
    

    验证结果:

    思考:如果按照思路把n个结点插入到二叉查找树中,请问应该如何验证程序的正确性???

    1. 需要包含drawtree.h头文件,并需要把源文件和该头文件处于同一个路径中,使用双引号包含,即:"drawtree.h"

    2. 修改drawtree.h头文件中关于二叉树的数据类型以及二叉树结点的类型,操作如下图所示!

    3. 在用户设计的源文件中调用drawtree.h头文件中的函数即可,然后把根结点传入该函数!! 即:在主函数中调用该函数。

    4. 编译源程序,当编译运行之后,会自动在当前目录内生成一个网页,打开网页即可验证!!

  • drawtree.h头文件如下:
///////////////////////////////////////////////////////////
//
//  Copyright(C), 2013-2021, GEC Tech. Co., Ltd.
//
//  文件: lab/tree/headers/drawtree.h
//  日期: 2017-9
//  描述: 使用C语言写一页webpage展示二叉树
//
//  作者: 粤嵌科技  
//
///////////////////////////////////////////////////////////

#ifndef _DRAWTREE_H_
#define _DRAWTREE_H_

/* ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ 公共头文件 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
#include <time.h>
#include <fcntl.h>
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <stdbool.h>
#include <strings.h>

#include <sys/stat.h>
#include <sys/types.h>

/* ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ 公共头文件 ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ */

#define MAX(a, b) ({ \
		typeof(a) _a = a; \
		typeof(b) _b = b; \
		(void)(&_a == &_b);\
		_a > _b? _a : _b; \
		})



/* ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ 用户二叉树节点 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
//指的是BST树中的结点有效键值的数据类型,用户可以根据需要进行修改
typedef int  DataType_t;


//构造BST树的结点,BST树中所有结点的数据类型应该是相同的
typedef struct BSTreeNode
{
	DataType_t  		 data; 		//节点的键值
	struct BSTreeNode	*lchild; 	//左子树的指针域
	struct BSTreeNode	*rchild; 	//右子树的指针域

}BSTnode_t;
/* ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ 用户二叉树节点 ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ */


/* ↓↓↓↓↓ 用户指定二叉树节点 ↓↓↓↓↓ */
#ifndef TREENODE
#define TREENODE BSTnode_t
#endif
/* ↑↑↑↑↑ 用户指定二叉树节点 ↑↑↑↑↑ */








/* ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ 默认二叉树节点 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
typedef struct _tree_node
{
	int data;
	struct _tree_node *lchild;
	struct _tree_node *rchild;

#ifdef AVL
	int height;
#endif

#ifdef RB
	struct _tree_node *parent;
	int color;
#endif
}_treenode, *_linktree;

// #ifndef TREENODE
// #define TREENODE Tnode_t
// #endif

/* ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ 默认二叉树节点 ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ */


/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */

#ifndef QUEUE_TREENODE_DATATYPE
#define QUEUE_TREENODE_DATATYPE TREENODE *
#endif

typedef QUEUE_TREENODE_DATATYPE qn_datatype;

struct _queue_node
{
	qn_datatype data;
	struct _queue_node *next;

};

typedef struct
{
	struct _queue_node *front;
	struct _queue_node *rear;
#ifdef QUEUE_SIZE
	int size;
#endif
}_queuenode, *_linkqueue;


static _linkqueue init_queue(void)
{
    _linkqueue q = (_linkqueue)malloc(sizeof(_queuenode));
	q->front = q->rear =
		(struct _queue_node *)malloc(sizeof(struct _queue_node));
	q->rear->next = NULL;

	return q;
}

static bool is_empty_q(_linkqueue q)
{
	return (q->front == q->rear);
}

/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
static bool out_queue(_linkqueue q, qn_datatype *pdata)
{
	if(is_empty_q(q))
		return false;

	struct _queue_node *p = q->front;

	q->front = q->front->next;
	free(p);
	*pdata = q->front->data;

	return true;
}

static bool en_queue(_linkqueue q, qn_datatype data)
{
	struct _queue_node *pnew;
	pnew = (struct _queue_node *)malloc(sizeof(struct _queue_node));
	if(pnew == NULL)
		return false;

	pnew->data = data;
	pnew->next = NULL;

	q->rear->next = pnew;
	q->rear = pnew;

	return true;
}

#ifdef QUEUE_SIZE
int queue_size(_linkqueue *q)
{
	return q->size;
}
#endif
/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */


static void pre_travel(TREENODE *root, void (*handler)(TREENODE *))
{
	if(root == NULL)
		return;
	
	handler(root);
	pre_travel(root->lchild, handler);
	pre_travel(root->rchild, handler);
}

static void mid_travel(TREENODE *root, void (*handler)(TREENODE *))
{
	if(root == NULL)
		return;
	
	mid_travel(root->lchild, handler);
	handler(root);
	mid_travel(root->rchild, handler);
}

static void post_travel(TREENODE *root, void (*handler)(TREENODE *))
{
	if(root == NULL)
		return;

	post_travel(root->lchild, handler);
	post_travel(root->rchild, handler);
	handler(root);
}

/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
static void level_travel(TREENODE *root, void (*handler)(TREENODE *))
{
	if(root == NULL)
		return;

    _linkqueue q;
	q = init_queue();

	en_queue(q, root);

    TREENODE *tmp;
	while(1)
	{
		if(!out_queue(q, &tmp))
			break;

		handler(tmp);

		if(tmp->lchild != NULL)
			en_queue(q, tmp->lchild);
		if(tmp->rchild != NULL)
			en_queue(q, tmp->rchild);
	}
}
/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
static char page_begin[] = "<html><head><title>tree map"
                           "</title></head><body>"
			   "<table border=0 cellspacing"
                           "=0 cellpadding=0>";
static char line_begin[] = "<tr>";
static char line_end  [] = "</tr>";
static char space     [] = "<td>&nbsp;</td>";
static char underline [] = "<td style=\"border-bottom:"
	 		   "1px solid #58CB64\">&nbsp;"
                           "</td>";

#ifdef RB
static char data_begin_red[] = "<td bgcolor=\"#FF0000\";style="
			       "\"border:1px sol"
                               "id #58CB64;background-colo"
                               "r:#DDF1D8;PADDING:2px;\" t"
                               "itle=\"level: 1\">";
static char data_begin_blk[] = "<td bgcolor=\"#000000\";style="
			       "\"border:1px sol"
                               "id #58CB64;background-colo"
                               "r:#DDF1D8;PADDING:2px;\" t"
                               "itle=\"level: 1\"><font color"
				"=\"#FFFFFF\">";
static char data_end_red[] = "</td>";
static char data_end_blk[] = "</font></td>";
#else
static char data_begin[] = "<td style=\"border:1px sol"
                           "id #58CB64;background-colo"
                           "r:#DDF1D8;PADDING:2px;\" t"
                           "itle=\"level: 1\">";
static char data_end  [] = "</td>";
#endif

static char page_end  [] = "</table></body></html>";

#define MAX_TREENODES_NUMBER 100
#define FILENAME 32

static int central_order[MAX_TREENODES_NUMBER];

static void putunderline(int fd, int num)
{
	int i;
	for(i=0; i<num; i++)
	{
		write(fd, underline, strlen(underline));
	}
}


static void putspace(int fd, int num)
{
	int i;
	for(i=0; i<num; i++)
	{
		write(fd, space, strlen(space));
	}
}
/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
#ifdef RB
static void putdata(int fd, TREENODE * p)
{
	char s[50];
	bzero(s, 50);

	snprintf(s, 50, "%d", p->data);

	switch(p->color)
	{
	case RED:
		write(fd, data_begin_red, strlen(data_begin_red));
		write(fd, s, strlen(s));
		write(fd, data_end_red, strlen(data_end_red));
		break;
	case BLACK:
		write(fd, data_begin_blk, strlen(data_begin_blk));
		write(fd, s, strlen(s));
		write(fd, data_end_blk, strlen(data_end_blk));
	}
}
#else
static void putdata(int fd, int data)
{
	char s[50];
	bzero(s, 50);

	snprintf(s, 50, "%d", data);
	write(fd, data_begin, strlen(data_begin));
	write(fd, s, strlen(s));
	write(fd, data_end, strlen(data_end));
}
#endif

static int Index = 0;
static void create_index(TREENODE * root)
{
	if(Index >= MAX_TREENODES_NUMBER-1)
		return;

	central_order[Index++] = root->data;
}


static int get_index(int data)
{
	int i;
	for(i=0; i<100; i++)
	{
		if(central_order[i] == data)
			return i;
	}
	return -1;
}

/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
static void data_leftside(int fd, TREENODE * root, int spaces)
{
	if(root == NULL)
		return;

	int s_line=0;

	if(root->lchild != NULL)
	{
		s_line = get_index(root->data)-
			 get_index(root->lchild->data)-1;
	}
	putspace(fd, spaces-s_line);
	putunderline(fd, s_line);
}


static int data_rightside(int fd, TREENODE * root)
{
	if(root == NULL)
		return 0;

	int s_line=0;

	if(root->rchild != NULL)
	{
		s_line = get_index(root->rchild->data)-
			 get_index(root->data)-1;
	}

	putunderline(fd, s_line);
	return s_line;
}


static void start_page(int fd)
{
	write(fd, page_begin, strlen(page_begin));
}

/* ↓↓↓↓↓↓↓↓↓↓↓↓↓ 画网页相关算法代码 ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ */
static void end_page(int fd)
{
	write(fd, page_end, strlen(page_end));
}


static void draw(TREENODE * root)
{
	if(root == NULL)
		return;

	time_t t;
	time(&t);
	static char filename[FILENAME];
	bzero(filename, FILENAME);
	snprintf(filename, FILENAME, "%u.html", (unsigned)t);
	int fd = open(filename, O_CREAT | O_TRUNC | O_RDWR, 0644);
	if(fd == -1)
	{
		perror("open() failed");
		exit(1);
	}

	Index = 0;
	mid_travel(root, create_index);

    _linkqueue q = init_queue();

	TREENODE * tmp = root;
	int ndata = 1;

	start_page(fd);
	while(1)
	{
		write(fd, line_begin, strlen(line_begin));

		int i, n = 0;
		int nextline = 0;
		for(i=0; i<ndata; i++)
		{
			int index = get_index(tmp->data);

			data_leftside(fd, tmp, index-n);

			#ifdef RB
			putdata(fd, tmp);
			#else
			putdata(fd, tmp->data);
			#endif
			int rightline = data_rightside(fd, tmp);

			if(tmp->lchild != NULL)
			{
				nextline++;
				en_queue(q, tmp->lchild);
			}
			if(tmp->rchild != NULL)
			{
				nextline++;
				en_queue(q, tmp->rchild);
			}
			if(!out_queue(q, &tmp))
				return;

			n = index + rightline;
			n++;
		}
		write(fd, line_end, strlen(line_end));
		ndata = nextline;
	}
	end_page(fd);
	close(fd);
}
#endif

二叉树的三种遍历方法:前序遍历、中序遍历、后序遍历

​ 对于二叉树的遍历,指的是从根结点出发,依次访问二叉树中所有的结点,每个结点只会被访问一次,一共提供了三种方案实现二叉树结点的遍历:前序遍历、中序遍历、后序遍历。

  • 前序遍历(根结点--->左子树--->右子树) A B D G H C E I F

  • 中序遍历(左子树--->根结点--->右子树) G D H B A E I C F

  • 后序遍历(左子树--->右子树--->根结点) G H D B I E F C A

删除二叉查找树中的节点(参考)

​ 从二叉查找树删除某个结点比插入结点要麻烦一点,但是删除结点之后也必须遵循“小--中--大”的原则。删除结点的时候就可能会出现以下几种情况:

(1) 要删除的结点的键值比根结点小,则在根结点的左子树进行递归的删除

(2) 要删除的结点的键值比根结点大,则在根结点的右子树进行递归的删除

(3) 如果要删除的结点恰好是根结点,也会遇到以下三种情况:

  1. 如果根结点有左子树,需要从左子树中找到键值最大的结点去替换根结点,然后在左子树中把原来的键值最大的结点递归的删掉

  2. 如果根结点有右子树,需要从右子树中找到键值最小的结点去替换根结点,然后在右子树中把原来的键值最小的结点递归的删掉

  3. 如果根结点没有左子树和右子树,则直接把根结点删掉

    例如:

​ 可以看到,如果要删除的结点是15,该结点有左子树,所以需要从左子树中找到键值最大的结点,也就是13,然后把13替换到15的位置,最后把多余13删掉即可。

​ 可以看到,如果要删除的结点是25,该结点有右子树,所以需要从右子树中找到键值最小的结点,也就是26,然后把26替换到25的位置,最后把多余26删掉即可。

热门相关:功夫圣医   全民女神:重生腹黑千金   重生田园贵媛:名门暖婚   北宋大丈夫   史上最强赘婿