C语言数据结构系列之树的概念结构和常见表示方法

0x00 树的概念

树是一种非线性的数据结构，它是由 n（n >= 0）个有限节点组成的一个具有层次关系的集合。

那么为什么叫 "树" 呢？

我们之所以把它成为 "树"，是因为它很像我们现实生活中的树。只是它是倒过来的，根朝上叶子朝下。

0x01 树的结构

① 有一个特殊的节点，成为根节点，根节点不存在前驱节点。

② 除根节点外，其余节点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm，期中没一个集合 Ti(1 <= i <= m) 又是一颗结构于树类似的字数。每颗子树的节点有且只有一个前驱，可以有0个或多个后继。

③ 因此，树是递归定义的。因为任何树都会被分成根和子树。

注意：树型结构中，子树之间不能有交集，否则就不是树形结构。

0x02 树的相关概念

节点的度：一个节点含有的子树的个数称为该节点的度。 比如上图中，A的度为6。

叶子结点：又称终端节点，度为0的节点称为叶子结点。 比如上图中，BCHIPQ等节点就是叶子结点，因为它们的度为0。

分支节点：又称非终端节点，度不为0的节点称为分支节点。 比如上图中，DEFG等节点就是分支节点，因为他们的度不为0。

父节点：又称双亲结点，若一个节点有子节点，则这个节点称作其子节点的父节点。 比如上图中，A是B的父节点。

子节点：又称孩子节点，若一个节点有根节点，则称为该节点的子节点。 如上图，B是A的子节点。

兄弟节点：具有相同父节点的节点互相称为兄弟节点。 同一个父亲生的才算。如上图，B和C是兄弟节点，它们的父节点都是A。

赞 (0)

相关推荐

  • C语言实现找出二叉树中某个值的所有路径的方法

    本文实例讲述了C语言实现找出二叉树中某个值的所有路径的方法,是非常常用的一个实用算法技巧.分享给大家供大家参考. 具体实现方法如下: #include <iostream> #include <vector> #include <iterator> #include <algorithm> using namespace std; vector<int> result; struct Node { Node(int i = 0, Node *pl

  • C语言判定一棵二叉树是否为二叉搜索树的方法分析

    本文实例讲述了C语言判定一棵二叉树是否为二叉搜索树的方法.分享给大家供大家参考,具体如下: 问题 给定一棵二叉树,判定该二叉树是否是二叉搜索树(Binary Search Tree)? 解法1:暴力搜索 首先说明一下二叉树和二叉搜索树的区别.二叉树指这样的树结构,它的每个结点的孩子数目最多为2个:二叉搜索树是一种二叉树,但是它有附加的一些约束条件,这些约束条件必须对每个结点都成立: 结点node的左子树所有结点的值都小于node的值. 结点node的右子树所有结点的值都大于node的值. 结点n

  • C语言数据结构之平衡二叉树（AVL树）实现方法示例

    本文实例讲述了C语言数据结构之平衡二叉树(AVL树)实现方法.分享给大家供大家参考,具体如下: AVL树是每个结点的左子树和右子树的高度最多差1的二叉查找树. 要维持这个树,必须在插入和删除的时候都检测是否出现破坏树结构的情况.然后立刻进行调整. 看了好久,网上各种各种的AVL树,千奇百怪. 关键是要理解插入的时候旋转的概念. // // AvlTree.h // HelloWorld // Created by feiyin001 on 17/1/9. // Copyright (c) 201

  • 使用C语言实现最小生成树求解的简单方法

    使用C语言实现最小生成树求解的简单方法

    最小生成树Prim算法朴素版 有几点需要说明一下. 1.2个for循环都是从2开始的,因为一般我们默认开始就把第一个节点加入生成树,因此之后不需要再次寻找它. 2.lowcost[i]记录的是以节点i为终点的最小边权值.初始化时因为默认把第一个节点加入生成树,因此lowcost[i] = graph[1][i],即最小边权值就是各节点到1号节点的边权值. 3.mst[i]记录的是lowcost[i]对应的起点,这样有起点,有终点,即可唯一确定一条边了.初始化时mst[i] = 1,即每条边都是从

  • c语言_构建一个静态二叉树实现方法

    c语言_构建一个静态二叉树实现方法

    第一.树的构建 定义树结构 struct BTNode { char data; struct BTNode* pLChild; struct BTNode* pRChild; }; 静态方式创建一个简单的二叉树 struct BTNode* create_list() { struct BTNode* pA = (struct BTNode*)malloc(sizeof(BTNode)); struct BTNode* pB = (struct BTNode*)malloc(sizeof(BT

  • 使用C语言求二叉树结点的最低公共祖先的方法

    使用C语言求二叉树结点的最低公共祖先的方法

    算法分析 我们直接来分析O(n)的算法. 比如求节点F和节点H的最低公共祖先,先求出从根节点A到F的路径,再求出A到H的路径,那么最后一个相同的节点就是最低公共祖先.A->B->D->F和A->B->E->H,最后相同的节点事B,所以最低公共祖先是B节点.求根节点到指定节点的算法先前已经更新过了,复杂度是O(n),所以总的时间复杂度是O(n). 条件细化: (1)树如果是二叉树,而且是二叉排序树.              这中条件下可以使用二叉排序树的搜索功能找到最低

  • C语言实现计算树的深度的方法

    本文实例讲述了C语言实现计算树的深度的方法.是算法设计中常用的技巧.分享给大家供大家参考.具体方法如下: /* * Copyright (c) 2011 alexingcool. All Rights Reserved. */ #include <iostream> using namespace std; struct Node { Node(int i = 0, Node *l = NULL, Node *r = NULL) : data(i), left(l), right(r) {}

  • C语言数据结构系列之树的概念结构和常见表示方法

    C语言数据结构系列之树的概念结构和常见表示方法

    0x00 树的概念 树是一种非线性的数据结构,它是由 n(n >= 0)个有限节点组成的一个具有层次关系的集合. 那么为什么叫 "树" 呢? 我们之所以把它成为 "树",是因为它很像我们现实生活中的树.只是它是倒过来的,根朝上叶子朝下. 0x01 树的结构 ① 有一个特殊的节点,成为根节点,根节点不存在前驱节点. ② 除根节点外,其余节点被分成 M(M>0) 个互不相交的集合 T1.T2.…….Tm,期中没一个集合 Ti(1 <= i <=

  • C语言数据结构系列篇二叉树的概念及满二叉树与完全二叉树

    C语言数据结构系列篇二叉树的概念及满二叉树与完全二叉树

    链接:C语言数据结构系列之树的概念结构和常见表示方法 0x00 概念 定义:二叉树既然叫二叉树,顾名思义即度最大为2的树称为二叉树. 它的度可以为 1 也可以为 0,但是度最大为 2 . 一颗二叉树是节点的一个有限集合,该集合: ① 由一个根节点加上两颗被称为左子树和右子树的二叉树组成 ② 或者为空 观察上图我们可以得出如下结论: ① 二叉树不存在度大于 2 的节点,换言之二叉树最多也只能有两个孩子. ② 二叉树的子树有左右之分,分别为左孩子和右孩子.次序不可颠倒,因此二叉树是有序树. 注意:对

  • C语言数据结构系列篇二叉树的遍历

    C语言数据结构系列篇二叉树的遍历

    目录 前言: Ⅰ. 定义二叉树 0x00二叉树的概念(回顾) 0x00定义二叉树 0x01 手动创建二叉树 Ⅱ. 二叉树的遍历 0x00关于遍历 0x01二叉树前序遍历 0x02二叉树中序遍历 0x03二叉树后序遍历 0x04层序遍历 前言: 学习二叉树的基本操作前,需要先创建一颗二叉树,然后才能学习其相关的基本操作,考虑到我们刚刚接触二叉树,为了能够先易后难地进行讲解,我们将暂时手动创建一颗简单的二叉树,用来方便大家学习.等二叉树结构了解的差不多后,后期我们会带大家研究二叉树地真正的创建方式.

  • C语言数据结构之中缀树转后缀树的实例

    C语言数据结构之中缀树转后缀树的实例 对于一个中缀表达式 a+b*c*(d-e/f) 转换成后缀是这样的形式 abc*def/-+ 后缀表达式是相当有用处的,转换成后缀表达式后求值会简单很多.那么该如何转换呢? 网上关于这方面的资料一搜一大把,每本数据结构的书中都会提及这个算法,在这个算法中,用到 栈 这个数据结构. 1,关键是比较运算符的优先级,谁的优先级高,谁就出现在前面上面的表达式中,有括号的时候括号优先级最高,*/次之,+-最后. 在上面的表达式中+的优先级不如*的高,因此,在后缀表达式

  • C语言数据结构系列队列篇

    C语言数据结构系列队列篇

    目录 一.队列(Queue) 0x00队列的概念 0x01队列的结构 二.队列的定义 0x00链式队列 0x02 接口函数 三.队列的实现 0x00队列初始化(QueueInit) 0x01销毁队列(QueueDestroy) 0x02判断队列是否为空(HeapIsEmpty) 0x03入队(QueuePush) 0x04出队(QueuePop) 0x05 返回队头数据(QueueFront) 0x06 返回队尾数据(QueueBack) 0x07 求队列大小(QueueSize) 0x08完整

  • go语言数据结构之前缀树Trie

    go语言数据结构之前缀树Trie

    目录 介绍 流程 代码 初始化 插入 查找 统计以XXX开头的单词个数 删除数据 介绍 Trie树:又称为单词查找树,是一种树形结构,可以应用于统计字符串,会在搜索引擎系统中用于对文本的词频统计,下图是一个Trie树的结构,同时它也是在插入数时的一个顺序图. 流程 首先应该先创建一个结构体,里面保存的是每一个节点的信息 初始化根节点,根节点应该初始化啥?啥也不用初始化,给个空就好看上图 插入:串转字符数组:遍历数组,如果下一个节点为空,创建,则继续遍历 查找:串转字符数组,遍历如何所有字符都在树

  • C语言递归系列的深入总结

    C语言递归系列的深入总结

    递归 什么是递归 递归简而言之就是函数自己调用自己 如图所示 但是递归并不是简简单单的自己调用自己的过程 它分为 传递 和 回归,传递就是橙色箭头 回归则是黑色箭头 这就是递归 以 计算阶乘为例,假设我们输入6 计算6的阶乘为例 #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> int factorial(int x) //递归体函数 { if (x == 1) { return 1; } return x * (factorial(x - 1

  • C语言数据结构二叉树简单应用

     C语言数据结构二叉树简单应用 在计算机科学中,二叉树是每个节点最多有两个子树的树结构.通常子树被称作"左子树"(left subtree)和"右子树"(right subtree),接下来我就在这里给大家介绍一下二叉树在算法中的简单使用: 我们要完成总共有 (1)二叉树的创建 (2)二叉树的先中后序递归遍历 (3)统计叶子结点的总数 (4)求树的高度 (5)反转二叉树 (6)输出每个叶子结点到根节点的路径 (7)输出根结点到每个叶子结点的路径. 定义二叉树结点类型

  • C语言数据结构之线索二叉树及其遍历

    C语言数据结构之线索二叉树及其遍历

    C语言数据结构之线索二叉树及其遍历 遍历二叉树就是以一定的规则将二叉树中的节点排列成一个线性序列,从而得到二叉树节点的各种遍历序列,其实质是:对一个非线性的结构进行线性化.使得在这个访问序列中每一个节点都有一个直接前驱和直接后继.传统的链式结构只能体现一种父子关系,￥不能直接得到节点在遍历中的前驱和后继￥,而我们知道二叉链表表示的二叉树中有大量的空指针,当使用这些空的指针存放指向节点的前驱和后继的指针时,则可以更加方便的运用二叉树的某些操作.引入线索二叉树的目的是: 为了加快查找节点的前驱和后继

随机推荐