首页 > 其他分享 >树(tree) [一]

树(tree) [一]

时间：2024-04-29 21:44:43浏览次数：24  
标签：结点 root tree 键值 二叉树 data 节点

树(tree) [一]

基本概念：

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

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

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

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

image

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

image

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

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

image

​ 可以看到，结点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）。

image

二叉树分类：

  • 斜树：

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

image

  • 满二叉树：

image

image

  • 完全二叉树：

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

image

注意： 满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树

  • 二叉查找树：

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

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

image

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

image

image

image

image

image

image

image

image

image

  • 平衡二叉树：

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

image

二叉树的性质：

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

image

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

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

image

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

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

二叉树的存储结构

  • 顺序结构

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

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

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

image

  • 链式结构

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

image

二叉树的遍历说明

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

/********************************************************************************************************
*
*
* 设计BST二叉查找树的接口，为了方便对二叉树进行节点的增删，所以采用双向不循环链表实现，每个节点内部都需要
* 有2个指针，分别指向该节点的左子树(lchild)和右子树(rchild)
*
* 
*
* Copyright (c)  2023-2024   [email protected]   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头文件中关于二叉树的数据类型以及二叉树结点的类型，操作如下图所示!image

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

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

      image

  • 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

image

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

image

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

image

删除二叉查找树中的节点（参考）

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

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

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

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

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

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

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

    例如：

image

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

image

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

标签：结点,root,tree,键值,二叉树,data,节点
From： https://www.cnblogs.com/fly-home/p/18166700

相关文章

  • JDK源码分析-TreeSet
    概述TreeSet是Java集合框架中用于存储唯一元素的树形数据结构，它实现了NavigableSet接口，这意味着TreeSet中的元素不仅是有序的，还支持一系列的导航方法。TreeSet的内部实现主要依赖于TreeMap，通过TreeMap的键来维护元素的排序。 类图从以上类图可以看到，TreeSet实现了三个接口，......
  • D. Distance in Tree
    https://codeforces.com/problemset/problem/161/D题意：给一棵树，求树上距离为k的节点对的数量。思路：树上dp，随便找个节点开始遍历。然后枚举当前点的距离为i的节点数与当前点的孩子节点距离为k-i-1的节点数相乘。总结：想到了树上dp，也想到了这个思路，但是没想到相乘跟开始遍历的......
  • Tree-shaking ESModule
     一、需求背景与收益Tree-shaking剪裁无用js与css，目前在dc组实现，首页效果如下：1、原文件5.19M，优化后2.61M2、gzip文件988.25KB， 优化后665.63KB3、Js文件减少三分之一，项目越久收益越高4、运行速度和用户体验都会提升5、Lighthouse性能评分提升大概4-8分6、属于攻坚技术......
  • ant-design Tree树形控件，通过expandedKeys控制收缩或折叠失效
    一、概述AntDesign的树形组件Tree，通过属性expandedKeys手动控制组件的展开和收缩时，点击节点后更新expandedKeys属性值可以正常展开，再点击左侧三角形小图标时（onExpand）却不能收缩了。  二、问题分析a.根据以往经验，出现keys的问题，一般是由key的数据重复或类型（尤其Number......
  • LSM Tree 简笔
    LSMTree总览写流程：就地写，写入memTable当activememTable满后，转变为readOnlymemTable，在合适时机flush入磁盘。当前level数据满后，进行归并操作，把数据排序，去重后转入下一level。背景介绍两种场景，读多写少，写多读少。原地写写操作：找到老数据所在位置，更新，IO操作，慢。......
  • vue3使用echarts的tree，自己写事件进行分页
    vue3使用echarts的tree，自己写事件进行分页  先到npmjs官网查看当前使用最多的版本https://www.npmjs.com/package/echarts 看了下5.5.0用的最多[email protected] 以下的demo(“@/flare”是后面的flare.json数据)<template><divid="chart-container"></div......
  • CF1709E XOR Tree
    linkSolution:PART1:转化首先套路地预处理出每个节点到根节点（\(1\)号节点）路径上的点权异或和\(w[u]\)。可以发现题意容易转化为：给定一棵\(n\)个节点的树，问你最少可以把它分成多少个联通块，使得每个连通块中的节点两两路径上的异或和不为0。易知对于一个节点，若它要被割......
  • CF771C Bear and Tree Jumps
    题目大意：给定一棵有\(n\)个节点的树，要你统计\(\sum_{1\lex\ley\len}{dist(x,y)/k}\)(\(dist(x,y)\)表示\(x\)到\(y\)的距离)\(n\le2\times10^5,k\le5\)解法：一道换根\(dp\)套路题。首先看到树上统计问题，考虑树形\(dp\)，那么我们设\(g(u)\)为以\(......
  • CF911F Tree Destruction
    题目链接：https://www.luogu.com.cn/problem/CF911Fsolution：先求得树的直径，再求得在树的直径上的节点和不在树的直径上的节点。我们考虑优先删除不在直径上的节点，这样不会破坏树的直径，在删完了这些点之后再慢慢删直径上的点。#include<bits/stdc++.h>usingnamespacestd;#def......
  • AGC014D Black and White Trees
    传送门[AGC014D]BlackandWhiteTree给出一颗\(N\)个节点组成的树，每个节点都可以被染成白色或者黑色；有高桥（先手）和青木（后手）两个人————高桥可以把任意一个点染成白色，青木则可以把任意一个点染成黑色，每个点只可染色一次。重复上述操作直到所有点都被染色后，只执行一次执行......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99