树一：定义及存储

article/2025/8/19 6:31:00

树的定义：

  • 树是一种非线性的数据结构。
  • 树是由 n (n >= 0) 个结点组成的有序集合。
    • 如果 n 为0，称为空树；
    • 如果 n > 0, 则：
      • 有一个结点称为根结点（root），它有直接后继，但没有直接前驱；
      • 除根以外的其他结点划分为 m (m > 0)个互不相交的有限集合 T0, T1, ..., Tm-1，每个集合又是一棵树，并且称为根的子树（subtree）　　　　

基本概念：

　　1. 树的结点包含一个数据和若干个指向子树的分支

　　2. 结点拥有的子树称为结点的度

　　　　（1）度为0的结点称为叶结点

　　　　（2）度不为0的结点称为分支结点

　　3. 树的度定义为所有结点中的度的最大值

　　4. 结点的直接后继称为该结点的孩子，相应的，该结点称为孩子的双亲。

　　5. 结点的孩子的孩子......称为该结点的子孙，相应的该结点称为子孙的祖先。

　　6. 同一个双亲的孩子之间互称兄弟。

　　7. 结点的层次：

　　　　　　（1）根为第一层

　　　　　　（2）根的孩子为第二层

　　　　　　（3）......

　　8. 树中结点的最大层次称为树的深度或高度。

　　9. 如果树中的结点的各子树从左向右是有次序的，子树间不能互换位置，则该树为有序树，否则称为无序树。

　　10. 森林是由 n (n >= 0) 棵互不相交的树的集合。

 

树的存储结构：

/* main.c */
#include <stdio.h>
#include "GTree.h"
/* run this program using the console pauser or add your own getch, system("pause") or input loop */void printf_data(GTreeData* data)
{printf("%c", (int)data);
}int main(int argc, char *argv[])
{GTree* tree = GTree_Create();int i = 0;GTree_Insert(tree, (GTreeData*)'A', -1);GTree_Insert(tree, (GTreeData*)'B', 0);GTree_Insert(tree, (GTreeData*)'C', 0);GTree_Insert(tree, (GTreeData*)'D', 0);GTree_Insert(tree, (GTreeData*)'E', 1);GTree_Insert(tree, (GTreeData*)'F', 1);GTree_Insert(tree, (GTreeData*)'H', 3);GTree_Insert(tree, (GTreeData*)'I', 3);GTree_Insert(tree, (GTreeData*)'J', 3);printf("Tree Height: %d\n", GTree_Height(tree));printf("Tree Degree: %d\n", GTree_Degree(tree));printf("Full Tree:\n");GTree_Display(tree, printf_data, 2, ' ');printf("Get Tree Data:\n");for(i=0; i<GTree_Count(tree); i++){printf_data(GTree_Get(tree, i));printf("\n");}printf("Get Root Data:\n");printf_data(GTree_Root(tree));printf("\n");GTree_Delete(tree, 3);printf("After Deleting D:\n");GTree_Display(tree, printf_data, 2, '-');GTree_Clear(tree);printf("After Clearing Tree:\n");GTree_Display(tree, printf_data, 2, '.');GTree_Destroy(tree);return 0;
}
/* LinkList.h */
#ifndef _LINKLIST_H_
#define _LINKLIST_H_typedef void LinkList;
typedef struct _tag_LinkListNode LinkListNode;
struct _tag_LinkListNode
{LinkListNode* next;
};LinkList* LinkList_Create();void LinkList_Destroy(LinkList* list);void LinkList_Clear(LinkList* list);int LinkList_Length(LinkList* list);int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);LinkListNode* LinkList_Get(LinkList* list, int pos);LinkListNode* LinkList_Delete(LinkList* list, int pos);#endif
/* LinkList.c */
#include <stdio.h>
#include <malloc.h>
#include "LinkList.h"typedef struct _tag_LinkList
{LinkListNode header;int length;
} TLinkList;LinkList* LinkList_Create() // O(1)
{TLinkList* ret = (TLinkList*)malloc(sizeof(TLinkList));if( ret != NULL ){ret->length = 0;ret->header.next = NULL;}return ret;
}void LinkList_Destroy(LinkList* list) // O(1)
{free(list);
}void LinkList_Clear(LinkList* list) // O(1)
{TLinkList* sList = (TLinkList*)list;if( sList != NULL ){sList->length = 0;sList->header.next = NULL;}
}int LinkList_Length(LinkList* list) // O(1)
{TLinkList* sList = (TLinkList*)list;int ret = -1;if( sList != NULL ){ret = sList->length;}return ret;
}int LinkList_Insert(LinkList* list, LinkListNode* node, int pos) // O(n)
{ TLinkList* sList = (TLinkList*)list;int ret = (sList != NULL) && (pos >= 0) && (node != NULL);int i = 0;if( ret ){LinkListNode* current = (LinkListNode*)sList;for(i=0; (i<pos) && (current->next != NULL); i++){current = current->next;}node->next = current->next;current->next = node;sList->length++;}return ret;
}LinkListNode* LinkList_Get(LinkList* list, int pos) // O(n)
{TLinkList* sList = (TLinkList*)list;LinkListNode* ret = NULL;int i = 0;if( (sList != NULL) && (0 <= pos) && (pos < sList->length) ){LinkListNode* current = (LinkListNode*)sList;for(i=0; i<pos; i++){current = current->next;}ret = current->next;}return ret;
}LinkListNode* LinkList_Delete(LinkList* list, int pos) // O(n)
{TLinkList* sList = (TLinkList*)list;LinkListNode* ret = NULL;int i = 0;if( (sList != NULL) && (0 <= pos) && (pos < sList->length) ){LinkListNode* current = (LinkListNode*)sList;for(i=0; i<pos; i++){current = current->next;}ret = current->next;current->next = ret->next;sList->length--;}return ret;
}
/* GTree.h */
#ifndef _GTREE_H_
#define _GTree_H_typedef void GTree;
typedef void GTreeData;
typedef void (GTree_Printf)(GTreeData*);GTree* GTree_Create();void GTree_Destroy(GTree* tree);void GTree_Clear(GTree* tree);int GTree_Insert(GTree* tree, GTreeData* data, int pPos);GTreeData* GTree_Delete(GTree* tree, int pos);GTreeData* GTree_Get(GTree* tree, int pos);GTreeData* GTree_Root(GTree* tree);int GTree_Height(GTree* tree);int GTree_Count(GTree* tree);int GTree_Degree(GTree* tree);void GTree_Display(GTree* tree, GTree_Printf* pFunc, int gap, char div);#endif
/* GTree.c */
#include <stdio.h>
#include <malloc.h>
#include "GTree.h"
#include "LinkList.h"typedef struct _tag_GTreeNode GTreeNode;
struct _tag_GTreeNode
{GTreeData* data;GTreeNode* parent;LinkList* child;
};typedef struct _tag_TLNode TLNode;
struct _tag_TLNode
{LinkListNode header;GTreeNode* node;
};static void recursive_display(GTreeNode* node, GTree_Printf* pFunc, int format, int gap, char div)
{int i = 0;if( (node != NULL) && (pFunc != NULL) ){for(i=0; i<format; i++){printf("%c", div);}pFunc(node->data);printf("\n");for(i=0; i<LinkList_Length(node->child); i++){TLNode* trNode = (TLNode*)LinkList_Get(node->child, i);recursive_display(trNode->node, pFunc, format + gap, gap, div);}}
}static void recursive_delete(LinkList* list, GTreeNode* node)
{if( (list != NULL) && (node != NULL) ){GTreeNode* parent = node->parent;int index = -1;int i = 0;for(i=0; i<LinkList_Length(list); i++){TLNode* trNode = (TLNode*)LinkList_Get(list, i);if( trNode->node == node ){LinkList_Delete(list, i);free(trNode);index = i;break;}}if( index >= 0 ){  if( parent != NULL ){for(i=0; i<LinkList_Length(parent->child); i++){TLNode* trNode = (TLNode*)LinkList_Get(parent->child, i);if( trNode->node == node ){LinkList_Delete(parent->child, i);free(trNode);break;}}               }while( LinkList_Length(node->child) > 0 ){TLNode* trNode = (TLNode*)LinkList_Get(node->child, 0);recursive_delete(list, trNode->node);}LinkList_Destroy(node->child);free(node);}}
}static int recursive_height(GTreeNode* node)
{int ret = 0;if( node != NULL ){int subHeight = 0;int i = 0;for(i=0; i<LinkList_Length(node->child); i++){TLNode* trNode = (TLNode*)LinkList_Get(node->child, i);subHeight = recursive_height(trNode->node);if( ret < subHeight ){ret = subHeight;}}ret = ret + 1;}return ret;
}static int recursive_degree(GTreeNode* node)
{
int ret = -1;if( node != NULL ){int subDegree = 0;int i = 0;ret = LinkList_Length(node->child);for(i=0; i<LinkList_Length(node->child); i++){TLNode* trNode = (TLNode*)LinkList_Get(node->child, i);subDegree = recursive_degree(trNode->node);if( ret < subDegree ){ret = subDegree;}}}return ret;
}GTree* GTree_Create()
{return LinkList_Create();
}void GTree_Destroy(GTree* tree)
{GTree_Clear(tree);LinkList_Destroy(tree);
}void GTree_Clear(GTree* tree)
{GTree_Delete(tree, 0);
}int GTree_Insert(GTree* tree, GTreeData* data, int pPos)
{LinkList* list = (LinkList*)tree;int ret = (list != NULL) && (data != NULL) && (pPos < LinkList_Length(list));if( ret ){TLNode* trNode = (TLNode*)malloc(sizeof(TLNode));TLNode* cldNode = (TLNode*)malloc(sizeof(TLNode));TLNode* pNode = (TLNode*)LinkList_Get(list, pPos);GTreeNode* cNode = (GTreeNode*)malloc(sizeof(GTreeNode));ret = (trNode != NULL) && (cldNode != NULL) && (cNode != NULL);if( ret ){cNode->data = data;cNode->parent = NULL;cNode->child = LinkList_Create();trNode->node = cNode;cldNode->node = cNode;LinkList_Insert(list, (LinkListNode*)trNode, LinkList_Length(list));if( pNode != NULL ){cNode->parent = pNode->node;LinkList_Insert(pNode->node->child, (LinkListNode*)cldNode, LinkList_Length(pNode->node->child));}}else{free(trNode);free(cldNode);free(cNode);}}return ret;
}GTreeData* GTree_Delete(GTree* tree, int pos)
{TLNode* trNode = (TLNode*)LinkList_Get(tree, pos);GTreeData* ret = NULL;if( trNode != NULL ){ret = trNode->node->data;recursive_delete(tree, trNode->node);}return ret;
}GTreeData* GTree_Get(GTree* tree, int pos)
{TLNode* trNode = (TLNode*)LinkList_Get(tree, pos);GTreeData* ret = NULL;if( trNode != NULL ){ret = trNode->node->data;}return ret;
}GTreeData* GTree_Root(GTree* tree)
{return GTree_Get(tree, 0);
}int GTree_Height(GTree* tree)
{TLNode* trNode = (TLNode*)LinkList_Get(tree, 0);int ret = 0;if( trNode != NULL ){ret = recursive_height(trNode->node);}return ret;
}int GTree_Count(GTree* tree)
{return LinkList_Length(tree);
}int GTree_Degree(GTree* tree)
{TLNode* trNode = (TLNode*)LinkList_Get(tree, 0);int ret = -1;if( trNode != NULL ){ret = recursive_degree(trNode->node);}return ret;
}void GTree_Display(GTree* tree, GTree_Printf* pFunc, int gap, char div)
{TLNode* trNode = (TLNode*)LinkList_Get(tree, 0);if( (trNode != NULL) && (pFunc != NULL) ){  recursive_display(trNode->node, pFunc, 0, gap, div);}
}

 

转载于:https://www.cnblogs.com/ronnydm/p/5928892.html


http://chatgpt.dhexx.cn/article/lRKVDNQe.shtml

相关文章

mysql 创建索引规则

mysql 创建索引规则

1、表的主键、外键必须有索引&#xff1b; 2、数据量超过300的表应该有索引&#xff1b; 3、经常与其他表进行连接的表&#xff0c;在连接字段上应该建立索引&#xff1b; 4、经常出现在Where子句中的字段&#xff0c;特别是大表的字段&#xff0c;应该建立索引&#xff1b; 5、…
阅读更多...
mysql分区表之三：MySQL分区建索引,唯一索引

mysql分区表之三：MySQL分区建索引,唯一索引

介绍 mysql分区后每个分区成了独立的文件&#xff0c;虽然从逻辑上还是一张表其实已经分成了多张独立的表&#xff0c;从“information_schema.INNODB_SYS_TABLES”系统表可以看到每个分区都存在独立的TABLE_ID,由于Innodb数据和索引都是保存在".ibd"文件当中&#…
阅读更多...
分享mysql创建索引的3种方法

分享mysql创建索引的3种方法

大家应该都知道索引的建立对于MySQL数据库的高效运行是很重要的,索引可以大大提升MySQL的检索速度,下面这篇文章主要给大家介绍了关于mysql创建索引的3种方法,需要的朋友可以参考下 1、使用CREATE INDEX创建&#xff0c;语法如下&#xff1a; 1 CREATE INDEX indexName ON tab…
阅读更多...
js 监听浏览器刷新还是关闭事件

js 监听浏览器刷新还是关闭事件

// $(window).bind(beforeunload,function(){return 您输入的内容尚未保存&#xff0c;确定离开此页面吗&#xff1f;;}); // window.onbeforeunload function() { return "确定离开此页面吗&#xff1f;"; }; // function myFunction() {return "自定…
阅读更多...
浏览器刷新和页面手动为什么不一样？

浏览器刷新和页面手动为什么不一样？

Fiddler(2):AutoResponse修改返回结果_mb5fed6ec4336ce的技术博客_51CTO博客Fiddler(2):AutoResponse修改返回结果&#xff0c;前言怎么修改接口的返回数据呢步骤1.抓包&#xff0c;找到要拦截的请求&#xff0c;然后在AutoResponder中AddRule&#xff1a;2.在RuleEditor中的第…
阅读更多...
vue监听浏览器刷新和关闭事件，并在页面关闭/刷新前发送请求

vue监听浏览器刷新和关闭事件，并在页面关闭/刷新前发送请求

vue监听浏览器刷新和关闭事件&#xff0c;并在页面关闭/刷新前发送请求 1.需求背景&#xff1a;2.需求分析&#xff1a;3.实现方式&#xff1a;4.实现方式解析&#xff1a;1&#xff09;浏览器页面事件基础2&#xff09;在mounted监听beforeunload和unload事件 5.存在的问题/风…
阅读更多...
浏览器刷新和关闭时显示提示信息

浏览器刷新和关闭时显示提示信息

vue 刷新和关闭浏览器时显示提示信息 使用onbeforeunload事件 mounted() {window.onbeforeunload e > {e e || window.eventif (e) {e.returnValue 关闭提示}return 关闭提示}} }, beforeDestroy() {window.onbeforeunload null },如果是所有页面都需要页面销毁显示提…
阅读更多...
【Vue实用功能】Vue监听浏览器刷新和关闭事件

【Vue实用功能】Vue监听浏览器刷新和关闭事件

Vue监听浏览器刷新和关闭事件 在前端开发中&#xff0c;我们通常会遇到这样的需求&#xff0c;用户离开、刷新页面前&#xff0c;修改数据未进行保存操作&#xff0c;需要提示框提醒用户 效果实现 methods: {/** 在刷新和关闭之前询问 **/beforeRefreshClose() {let self t…
阅读更多...
vue监听浏览器刷新和关闭；

vue监听浏览器刷新和关闭；

注意&#xff1a;区分不了浏览器是触发了刷新还是关闭&#xff0c;而且提示的弹框是无法自定义的&#xff1b;如果有大佬有方法能区分&#xff0c;还请评论学习一下&#xff01;感谢&#xff01; 代码可直接复制&#xff1a; <template><div><div /></di…
阅读更多...
JS阻止浏览器刷新的方法

JS阻止浏览器刷新的方法

直接先给朋友们上阻止浏览器刷新的代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><meta http-equiv&quo…
阅读更多...
VSCODE同步浏览器刷新

VSCODE同步浏览器刷新

VSCODE同步浏览器刷新 安装插件 live server
阅读更多...
java中foreach的用法

java中foreach的用法

文章目录 前言语法用法用法1&#xff1a;输出一维数组用法2&#xff1a;输出二维数组foreach的局限性什么是索引 总结 前言 java中foreach,可以认为是增强版的for语句循环&#xff0c;它可以减少代码量&#xff0c;但是不是所有的foreach都可以代替for循环。 语法 foreach的…
阅读更多...
JAVA实现九九乘法表

JAVA实现九九乘法表

用java语言实现九九乘法表&#xff0c;这里使用的是for循环 public class NineNineDemo{public static void main(String[] args){int i1;//对行变量赋值int j1;//对列变量赋值for(i1;i<9;i){for(j1;j<i;j){//行变量外循环&#xff1b;列变量内循环System.out.print(i&q…
阅读更多...
Java的ASCII编码表

Java的ASCII编码表

数字和字符的对照关系表&#xff08;编码表&#xff09;&#xff1a; ASCII码表&#xff1a;American Standard Code for Information Interchange, 美国信息交换标准代码。 Unicode码表&#xff1a;万国码。也是数字和符号的对照关系&#xff0c;开头0-127部分和ASCII完全一样…
阅读更多...
JAVA——链表

JAVA——链表

一、链表概念及结构 链表&#xff1a;链表是一种物理存储结构上非连续存储结构&#xff0c;数据元素的逻辑顺序是通过链表中的引用链接次序实现的。如下图&#xff1a;&#xff08;通俗的说&#xff1a;就是由一个个节点组成&#xff0c;这些节点逻辑上连续&#xff0c;物理上…
阅读更多...
java对象复制_Java对象的复制三种方式

java对象复制_Java对象的复制三种方式

Java对象的复制三种方式 概述 在实际编程过程中，我们常常要遇到这种情况：有一个对象A，在某一时刻A中已经包含了一些有效值，此时可能 会需要一个和A完全相同新对象B，并且此后对B任何改动都不会影响到A中的值，也就是说，A与B是两个独立的对象，但B的初始值是由A对象确定的。…
阅读更多...
Java 如何复制 List ?

Java 如何复制 List ?

List 复制在项目开发时&#xff0c;使用到的频率还是比较高的。List 复制有浅拷贝和深拷贝两种方式。在陈述复制方法前&#xff0c;先总结下什么是浅拷贝和深拷贝(以下内容均站在 Java 语言基础上进行讨论)。 一、什么是浅拷贝&#xff08;Shallow Copy&#xff09;和深拷贝&a…
阅读更多...
Java对象复制

Java对象复制

文章目录 前言何不可变类对象复制方式1.直接赋值2.浅拷贝3.深拷贝 对象复制方案1.get/set2.Spring BeanUtils3.Apache BeanUtils4.BeanCopier5.Orika6.Dozer7.MapStruct8.Bean Mapping9.Bean Mapping ASM10.ModelMapper11.JMapper12.Json2Json 复制方案选择 前言 在我们实际项…
阅读更多...
Java 复制Excel工作表

Java 复制Excel工作表

本文归纳了关于Java如何复制Excel工作表的方法&#xff0c;按不同复制需求&#xff0c;可分为&#xff1a; 1. 复制工作表 1.1 在同一个工作簿内复制工作表 1.2 在不同工作簿间复制工作表 2. 复制指定单元格数据 对于复制方法copy()&#xff0c;这里简单整理了一个表格&am…
阅读更多...
个人如何接入微信支付和支付宝等支付接口，免签约

个人如何接入微信支付和支付宝等支付接口，免签约

企业的资质足够高了才能够得到微信或者支付宝官方的支付接口&#xff08;而且这个官方接口收费的最低费率在0.38%以上&#xff09;那么个人如何做&#xff1f; 个人开发者或者小微企业团队如何使用在线收款支付功能呢&#xff1f; 第四方支付&#xff0c;市面上各种收款工具要…
阅读更多...
推荐文章

Copyright @ 2022~2023