【数据结构与算法】树（一）

我就是我 2022-05-21 06:11 178阅读 0赞

### 树的定义 ###

树是n个结点的有限集，当n=0的时候称为空树。

*  有且仅有一个特定的称为根的结点。
 *  树的度就是树内各个结点的度的最大值。
 *  度为0的结点称为叶结点。
 *  度不为0的结点称为分支结点。

### 树的存储结构 ###

三种不同的表示结构：双亲表示法，孩子表示法，孩子兄弟表示法。

*  双亲表示法  
    每个结点除了知道自己是谁以外，还知道其双亲在哪里。  
    ![双亲表示法][70]

#define MAX_TREE_SIZE 100
    
    typedef int ElemType;
    
    typedef struct PTNode
    {
        ElemType data; //结点数据
        int parent;    //双亲位置
    }PTNode;
    
    typedef struct
    {
        PTNode nodes[MAX_TREE_SIZE ];
        int r;   //根的位置
        int n;   //结点数目
    }

*  双亲孩子表示法

#define MAX_TREE_SIZE 100
    typedef int ElemType;
    
    typedef struct CTNode
    {
        int child;                           //孩子结点的下标
        struct CTNode *next;       //指向下一个孩子结点的指针
    }*ChildPtr;
    
    //表头结构
    typedef struct
    {
        ElemType data; //结点数据
        int parent;    //双亲位置
        ChildPtr firstchild; //指向第一个孩子结点
    }CTBox;
    
    //树结构
    typedef struct
    {
        CTBox nodes[MAX_TREE_SIZE];
        int r,n;
    }

![双亲孩子表示法][70 1]

![双亲孩子表示法][70 2]

[70]: /images/20220521/9cfe325befc840da9d65b64297851b7e.png
[70 1]: /images/20220521/e2a5025783354b4192074c40d321686f.png
[70 2]: /images/20220521/ed7e6b56f95d4106b8f3283742abce63.png

发表评论取消回复

表情：

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

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

相关阅读

相关【数据结构与算法】B树与B+树

B 树，又称为多路平衡查找树，BB 树中所有结点的孩子个数的最大值称为 BB 树的阶，通常用 mm 表示，上图即为 55 阶 BB 树。一棵 mm 阶 BB 树或为空树，...

分手后的思念是犯贱/ 2024年04月26日 02:32/ 0 赞/ 15 阅读

相关算法数据结构(一)-B树

介绍 B树的目的为了硬盘快速读取数据（降低IO操作次树）而设计的一种平衡的多路查找树。目前大多数据库及文件索引，都是使用B树或变形来存储实现。目录 1. 为什

落日映苍穹つ/ 2023年10月17日 15:54/ 0 赞/ 54 阅读

相关数据结构与算法 -- 树与树算法

目录树树的概念树的存储与表示常见的一些树的应用场景二叉树二叉树的概念二叉树的性

逃离我推掉我的手/ 2022年12月20日 12:39/ 0 赞/ 111 阅读

相关【算法与数据结构】——线段树

线段树原理将\[1,n\]分解成若干特定的自取件(数量不超过4\n),然后,将每个区间\[L,R\]都分解为少量特定的子区间,通过对这些少量子区间的修改或者统计,来实现

悠悠/ 2022年11月15日 14:28/ 0 赞/ 150 阅读

相关数据结构与算法--之树

二叉树的定义：每个结点最多有两个子树且左右子树的顺序不能调换。满二叉树：如果二叉树中任意一个结点。或者是叶结点，或者有两个非空子树，且叶结点都集中在树的最下面

快来打我*/ 2022年08月30日 00:49/ 0 赞/ 153 阅读

相关【数据结构】数据结构与算法（一）——线性结构

一、前言线性结构是一种基本的数据结构，主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述。即“一个接一个排列”。特点是数据元素之间呈现一种线性关系。

逃离我推掉我的手/ 2022年07月15日 01:58/ 0 赞/ 225 阅读

相关【数据结构与算法】树（一）

树的定义树是n个结点的有限集，当n=0的时候称为空树。有且仅有一个特定的称为根的结点。树的度就是树内各个结点的度的最大值。度为0的结点称为叶结

我就是我/ 2022年05月21日 06:11/ 0 赞/ 179 阅读

相关数据结构与算法---4（树）

树树是n（n>=0）个结点的有限集；n=0的时候称为空树；在任意的一颗非空树中：有且仅有一个特定的称为根的结点当n>1的时候，其余结点可分为m(m>0

╰+哭是因爲堅強的太久メ/ 2022年03月06日 07:56/ 0 赞/ 206 阅读

相关树（数据结构与算法）

[递归](递归) [1. 树的高度](1-树的高度) [2. 平衡树](2-平衡树)

素颜马尾好姑娘i/ 2021年12月07日 13:37/ 0 赞/ 240 阅读

相关 7.树与树算法（python数据结构与算法）

树的概念树（英语：tree）是一种抽象数据类型（ADT），用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成的一个具有层次关系的集合。把它叫做“树”

红太狼/ 2021年05月12日 11:50/ 0 赞/ 456 阅读