树(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的*，如果二叉查找树不是空树则需要遵循以下的特点：
- 如果二叉查找树有左子树，则左子树的结点的键值key要小于左子树的根结点的键值key
- 如果二叉查找树有右子树，则右子树的结点的键值key要大于右子树的根结点的键值key
- 对于二叉查找树而言，左子树和右子树也分别是二叉查找树。
可以看到，左子树的结点的键值都是小于右子树，二叉查找树的结点的键值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;
-
创建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; } -
创建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; } -
向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个结点插入到二叉查找树中，请问应该如何验证程序的正确性???
-
需要包含drawtree.h头文件，并需要把源文件和该头文件处于同一个路径中，使用双引号包含，即："drawtree.h"
-
修改drawtree.h头文件中关于二叉树的数据类型以及二叉树结点的类型，操作如下图所示!
-
在用户设计的源文件中调用drawtree.h头文件中的函数即可，然后把根结点传入该函数！！ 即：在主函数中调用该函数。
-
编译源程序，当编译运行之后，会自动在当前目录内生成一个网页，打开网页即可验证！！
-
- 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> </td>";
static char underline [] = "<td style=\"border-bottom:"
"1px solid #58CB64\"> "
"</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) 如果要删除的结点恰好是根结点，也会遇到以下三种情况：
-
如果根结点有左子树，需要从左子树中找到键值最大的结点去替换根结点，然后在左子树中把原来的键值最大的结点递归的删掉
-
如果根结点有右子树，需要从右子树中找到键值最小的结点去替换根结点，然后在右子树中把原来的键值最小的结点递归的删掉
-
如果根结点没有左子树和右子树，则直接把根结点删掉
例如：
可以看到，如果要删除的结点是15，该结点有左子树，所以需要从左子树中找到键值最大的结点，也就是13，然后把13替换到15的位置，最后把多余13删掉即可。
可以看到，如果要删除的结点是25，该结点有右子树，所以需要从右子树中找到键值最小的结点，也就是26，然后把26替换到25的位置，最后把多余26删掉即可。