树是n(n>=0)个结点的有限集,n=0时称为空树,在任意一颗非空树中:

  • 有且只有一个特定的称为(Root)的结点
  • 当n > 1时,其余结点可分为m(m>0)个互不相交有限集T1,T2…Tm,其中每一个集合本身又是一棵树,并且称为根的子树(SubTree)
  1. 结点拥有的子树称为结点的(Degree),度为0的结点称为叶结点(Leaf)或终端结点,度不为0的结点称为分支结点非终端结点,除根节点之外,分支结点也称为内部结点树的度是树内各结点的度的最大值
  2. 结点的子树的根称为该结点的孩子(Child),该结点称为孩子的双亲(Parent),同一个双亲的孩子之间互称兄弟(Sibling),结点的祖先是从根到该结点所经分支上的所有结点,以某结点为根的子树中的任一结点都称为该结点的子孙
  3. 结点的层次:根为第一层,根的孩子为第二层,双亲在同一层的结点互为堂兄弟,树中结点的最大层次称为树的深度(Depth)或高度
  4. 如果将树中结点的各子树看成从左至右是有顺序的,不能互换的 ,则该树称为有序树,否则称为无序树
  5. 森林是m(m>=0)棵互不相交的树的集合

树的存储结构

简单的顺序存储结构是不能满足树的实现要求的,但结合链式存储结构可以满足

双亲表示法

除了根结点,每个结点一定且仅有一个双亲

  1. 双亲表示法结点定义:在每个结点中附设一个指示器指示其双亲结点在数组中的位置,即一个数据域、一个指针域(存放双亲下标)
  2. 可以灵活扩展此结构,把指针域扩展为长子域、右兄弟域等
  3. 一个存储结构设计的是否合理,取决于基于该存储结构的运算是否合适、方便、时间复杂度好坏等

孩子表示法

每个结点有多个指针域,其中每个指针指向一棵子树的根结点,这称为多重链表表示法,有两种方案:

  • 指针域的个数就等于树的度;对于树中各结点的度相差很大时会浪费空间
  • 是专门取一个位置(度域)来存储结点指针域的个数;各结点的链表结构不同,损耗运算时间

结合该两种方案做到既可以减少空指针的浪费又能使结点结构相同,即孩子表示法,具体为:

  • 把每个结点的孩子结点排列起来,以单链表做存储结构,则n个结点有n个孩子链表,叶子节点为空表
  • n个头指针又组成一个线性表,采用顺序存储结构,存放进一个一维数组中

如此一来,要查找某个结点的某个孩子或兄弟,只需要查找这个结点的孩子单链表即可

如果还想知道某个结点的双亲是谁,可以结合双亲表示法,形成双亲孩子表示法

孩子兄弟表示法

  1. 任何一棵树,它的结点的第一个孩子如果存在,就是唯一的,它的右兄弟如果存在也是唯一的。因此设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟
  2. 孩子兄弟表示法结构定义:数据域、两个指针域(指向该结点的第一个孩子结点、指向右兄弟结点)

二叉树

由n个结点组成的有限集合,该集合或为空集(空二叉树),或由一个根结点和两棵互不相交、分别称为根结点的左子树右子树的二叉树组成

特点:

  • 每个结点最多有两棵子树(0~2棵)
  • 左子树和右子树的次序不能变
  • 只有一棵子树时也要区分左右子树

二叉树的五种基本形态:空二叉树、只有根结点、只有左子树、只有右子树、有左右子树

特殊二叉树:

  • 斜树:每一层都只有一个结点,结点的个数与二叉树的深度相同;分左斜树右斜树
  • 满二叉树:所有叶子都在最底层;分支结点的度一定是2;与同深度的二叉树比,满二叉树的结点和叶子数最多
  • 完全二叉树:按层序编号,如果编号没出现空档(存在的结点位置和同条件的满二叉树的位置相同)则是;叶结点只能在最后两层,与同深度的二叉树比,完全二叉树的深度最小

二叉树的性质

  1. 性质1:在二叉树的第i层上至多有2^(i-1)个结点(i>=1)
  2. 性质2:深度为k的二叉树至多有(2^k)-1个结点 (k>=1)
  3. 性质3:叶结点数=度为2的结点数+1(通过推导总结点数和分支线总数得出)
  4. 性质4:具有n个结点的完全二叉树的深度为[log2n]+1(性质2的倒推)
  5. 性质5:对一棵有n个结点的完全二叉树的结点按层编号,对任一结点i有
    • 若i=1,则i是根结点,无双亲;若i>1,则双亲是结点i/2
    • 若2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i
    • 若2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1

二叉树的存储结构

顺序存储结构:用一维数组存储二叉树中结点,对一般的二叉树不能反应逻辑关系;一般用于完全二叉树 二叉链表:由结点数据(数据域)、左右孩子指针(两个指针域)定义的链表;若再加一个指向双亲的指针域就称为三叉链表

遍历二叉树

指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次

前序遍历算法:

先前序遍历左子树,再前序遍历右子树

/* 用C实现二叉树的前序遍历递归算法*/

void PreOrder(BiTree T)
{
    if (T == NULL)
        return;
    printf("%c", T->data);   /*对结点的操作*/
    PreOrder(T->lchild)
    PreOrder(T->rchild)
}

中序遍历算法:

先中序遍历根结点的左子树,然后访问根结点,最后中序遍历右子树 与前序遍历相比相当于把调用左孩子的递归函数提前了 遍历到左孩子为NULL的结点时才返回对结点操作,然后再对该结点的右子树做同样遍历

/* 用C实现二叉树的中遍历递归算法*/

void InOrder(BiTree T)
{
    if (T == NULL)
        return;
    InOrder(T->lchild)    /*提前*/
    printf("%c", T->data);   /*对结点的操作*/
    InOrder(T->rchild)
}

后序遍历算法:

从左到右的顺序先遍历叶子再遍历结点的方式遍历访问左右子树

/* 用C实现二叉树的后遍历递归算法*/

void PostOrder(BiTree T)
{
    if (T == NULL)
        return;
    PostOrder(T->lchild)   /*先左*/
    PostOrder(T->rchild)  /*再右*/
    printf("%c", T->data);   /*对结点的操作*/
}