@[TOC]

树的基本概念


          图1

树的结点

  结点：应用树结构存储的每一个数据元素都被称为“结点”。例如，上图1中，数据元素 1 就是一个结点；
  父结点（双亲结点）、子结点和兄弟结点：对于上图1中的结点 1,2,3,4 来说，1 是 2,3,4 结点的父结点（也称为“双亲结点”），而 2,3,4 都是 1 结点的子结点（也称“孩子结点”）。对于 2,3,4 来说，它们都有雷同的父结点，所以它们互为兄弟结点。
  树根结点（简称“根结点”）：每一个非空树都有且只有一个被称为根的结点。上图1中，结点1就是整棵树的根结点。
  叶子结点：如果结点没有任何子结点，那么此结点称为叶子结点（叶结点）。例如上图1中，结点 11,12,6,7,13,9,10都是这棵树的叶子结点。

子树和空树

  子树：上图1中，整棵树的根结点为结点 1，而如果单看结点2,5,6,11,12 组成的局部来说，也是棵树，而且节点 2 为这棵树的根结点。所以称 2,5,6,11,12这几个结点组成的树为整棵树的子树；同样，结点 5,11,12 形成的也是一棵子树，根结点为5。
  留神：单个结点也是一棵树，只不过根结点就是它自身。上图1中，结点 11,12,6 等都是树，且都是整棵树的子树。
  晓得了子树的概念后，树也能够这样定义：树是由根结点和若干棵子树形成的。
  空树：如果汇合自身为空，那么形成的树就被称为空树。空树中没有结点。
  补充：在树结构中，对于具备同一个根结点的各个子树，相互之间不能有交加。例如，上图1中，除了根结点1，其余元素又各自形成了三个子树，根结点别离为 2,3,4，这三个子树相互之间没有雷同的结点。如果有，就毁坏了树的构造，不能算做是一棵树。

结点的度和档次

  对于一个结点，领有的子树数（结点有多少分支）称为结点的度（Degree）。例如，上图1中，根结点1下分出了 3 个子树，所以，结点 1 的度为 3。
  一棵树的度是树内各结点的度的最大值。上图1示意的树中，各个结点的度的最大值为 3，所以，整棵树的度的值是 3。
  结点的档次：从一棵树的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，顺次类推。对于上图1来说，1 结点在第一层，2,3,4 为第二层，5,6,7,8,9,10在第三层，11,12,13在第四层。
  一棵树的深度（高度） 是树中结点所在的最大的档次。上图1树的深度为 4。
  如果两个结点的父结点虽不雷同，然而它们的父结点处在同一档次上，那么这两个结点互为堂兄弟。例如，上图1中，结点5,6,7,8,9,10 的父结点都在第二层，所以之间为堂兄弟的关系。

有序树和无序树

  如果树中结点的子树从左到右看，谁在右边，谁在左边，是有规定的，这棵树称为有序树；反之称为无序树。
  在有序树中，一个结点最右边的子树称为"第一个孩子"，最左边的称为"最初一个孩子"。
拿上图1来说，如果是其自身是一棵有序树，则以结点 2 为根结点的子树为整棵树的第一个孩子，以结点 4 为根结点的子树为整棵树的最初一个孩子。

森林

  由 m（m >= 0）个互不相交的树组成的汇合被称为森林。上图1中，别离以2,3,4为根结点的三棵子树就能够称为森林。
  后面讲到，树能够了解为是由根结点和若干子树形成的，而这若干子树自身是一个森林，所以，树还能够了解为是由根结点和森林组成的。用一个式子示意为：Tree =（root,F）
  其中，root 示意树的根结点，F 示意由 m（m >= 0）棵树组成的森林。

二叉树的性质

  通过前人的总结，二叉树具备以下几个性质：

  • 二叉树中，第 i 层最多有 2i-1 个结点。
  • 如果二叉树的深度为 K，那么此二叉树最多有 2K-1 个结点。
  • 二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1。
  • 二叉树还能够持续分类，衍生出满二叉树和齐全二叉树。

满二叉树

  如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。

        图2

  如图2 所示就是一棵满二叉树。

  • 满二叉树除了满足一般二叉树的性质，还具备以下性质：
  • 满二叉树中第 i 层的节点数为 2n-1 个。
  • 深度为 k 的满二叉树必有 2k-1 个节点 ，叶子数为 2k-1。
  • 满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度雷同的子树，且叶子节点都在最底层。
  • 具备 n 个节点的满二叉树的深度为 log2(n+1)。

齐全二叉树

  如果二叉树中除去最初一层节点为满二叉树，且最初一层的结点顺次从左到右散布，则此二叉树被称为齐全二叉树。

              图3
  如上图3a 所示是一棵齐全二叉树，如上图3b中因为最初一层的节点没有依照从左向右散布，因而只能算作是一般的二叉树。
  齐全二叉树除了具备一般二叉树的性质，它本身也具备一些独特的性质，比如说，n 个结点的齐全二叉树的深度为 ⌊log2n⌋+1。
  [log2n]示意取小于 log2n 的最大整数。例如，[log24] = 2，而 [log25⌋]后果也是 2。
  对于任意一个齐全二叉树来说，如果将含有的结点依照档次从左到右顺次标号（图3），对于任意一个结点 i ，齐全二叉树还有以下几个论断成立：

  • 当 i>1 时，父亲结点为结点 [i/2] 。（i=1 时，示意的是根结点，无父亲结点）
  • 如果 2 i>n（总结点的个数） ，则结点 i 必定没有左孩子（为叶子结点）；否则其左孩子是结点 2i 。
  • 如果 2 i+1>n ，则结点 i 必定没有右孩子；否则右孩子是结点 2i+1 。

二叉树的顺序存储

  二叉树的顺序存储，指的是应用程序表（数组）存储二叉树。须要留神的是，顺序存储只实用于齐全二叉树。换句话说，只有齐全二叉树才能够应用程序表存储。因而，如果咱们想顺序存储一般二叉树，须要提前将一般二叉树转化为齐全二叉树。
  有读者会说，满二叉树也能够应用顺序存储。要晓得，满二叉树也是齐全二叉树，因为它满足齐全二叉树的所有特色。

  一般二叉树转齐全二叉树的办法很简略，只需给二叉树额定增加一些节点，将其"拼凑"成齐全二叉树即可。如图4所示：

            图4
  下图中，左侧是一般二叉树，右侧是转化后的齐全（满）二叉树。
  解决了二叉树的转化问题，接下来学习如何顺序存储齐全（满）二叉树。
  齐全二叉树的顺序存储，仅需从根节点开始，依照档次顺次将树中节点存储到数组即可。

      图5
  例如，存储图5如下 所示的齐全二叉树，其存储状态如图 6 所示：

      图6
  同样，存储由一般二叉树转化来的齐全二叉树也是如此。例如，图 4 中一般二叉树的数组存储状态如图7 所示：

      图7
  由此，咱们就实现了齐全二叉树的顺序存储。
  不仅如此，从程序表中还原齐全二叉树也很简略。咱们晓得，齐全二叉树具备这样的性质，将树中节点依照档次并从左到右顺次标号（1,2,3,...），若节点 i 有左右孩子，则其左孩子节点为 2i，右孩子节点为 2i+1。此性质可用于还原数组中存储的齐全二叉树，也就是实现由图6到图5、由图 7到图4的转变。

二叉树的链式存储

  二叉树并不适宜用数组存储，因为并不是每个二叉树都是齐全二叉树，一般二叉树应用程序表存储或多或多会存在空间节约的景象。
  接下来咱们介绍二叉树的链式存储构造。

      图8
  如图 8 所示，此为一棵一般的二叉树，若将其采纳链式存储，则只需从树的根节点开始，将各个节点及其左右孩子应用链表存储即可。因而，图8对应的链式存储构造如图9所示：

            图9
  由图9可知，采纳链式存储二叉树时，其节点构造由 3 局部形成（如图10 所示）：

  • 指向左孩子节点的指针（Lchild）；
  • 节点存储的数据（data）；
  • 指向右孩子节点的指针（Rchild）；


     图10
链式存储代码实现：

/* * @Description: 二叉树的链式存储 * @Version: V1.0 * @Autor: Carlos * @Date: 2020-05-29 16:37:38 * @LastEditors: Carlos * @LastEditTime: 2020-05-29 16:45:13 */ #include <stdio.h>#include <stdlib.h>typedef struct BitNode{    int data;    struct BitNode *lchild,*rchild;}BitNode,*BitTree;void CreateBiTree(BitTree *T){    *T=(BitNode*)malloc(sizeof(BitNode));    //根节点    (*T)->data=1;    (*T)->lchild=(BitNode*)malloc(sizeof(BitNode));    //1节点的左孩子2    (*T)->lchild->data=2;    (*T)->rchild=(BitNode*)malloc(sizeof(BitNode));    //1节点的右孩子3    (*T)->rchild->data=3;    (*T)->rchild->lchild=NULL;    (*T)->rchild->rchild=NULL;    (*T)->lchild->lchild=(BitNode*)malloc(sizeof(BitNode));    //2节点的左孩子    (*T)->lchild->lchild->data=4;    (*T)->lchild->rchild=NULL;    (*T)->lchild->lchild->lchild=NULL;    (*T)->lchild->lchild->rchild=NULL;}int main() {    BitTree Tree;    CreateBiTree(&Tree);    printf("%d",Tree->lchild->lchild->data);    return 0;}

  文中代码均已测试，有任何意见或者倡议均可分割我。欢送学习交换！
  如果感觉写的不错，请点个赞再走，谢谢！
如遇到排版错乱的问题，能够通过以下链接拜访我的CSDN。

**CSDN:[CSDN搜寻“嵌入式与Linux那些事”]