[二叉树](2)二叉树

在讨论一般树的存储结构及其操作之前,我们首先研究一种称为二叉树的抽象数据类型。

二叉树的定义

二叉树(Binary Tree)是另一种树型结构,它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。

抽象数据类型Binary Tree 的定义如下:

ADT BinaryTree{
        数据对象D:D是具有相同特性的数据元素的集合
        数据关系R:
            若D为空集,则R = 空集,则称BinaryTree为空二叉树
            若D不为空,则R = {H},H是如下二元关系
        (1)在D中存在惟一的称为根的数据元素root,它的关系H下无前驱
        (2)任意D = {root} != 空集,则存在D = {root} = {Dl,Dr},且Dl并Dr等于空
        (3)若Dl != 空集,则Dl中存在惟一的元素x1,<root,x1>属于H,且存在Dl上的关系
           H1包含H;若Dr!=NULL,则Dr中存在惟一元素xr,<root,xr>属于H,且存在Dr上的关系
           Hr包含H,H={<root,x1>,<root,xr>,H1,Hr}
        (4)(D1, { H1 })是一棵符合本定义的二叉树, 称为根的左子树, { Dr,{Hr} }是一棵
           符合本定义的二叉树,称为根的右子树


        基本操作P:
           InitBiTree(&T)
               操作结果:构造空二叉树T
           
           DestroyBiTree(&T)
               初始条件:二叉树T存在
               操作结果:销毁二叉树T
           
           CreateBiTree(&T,definition)
               初始条件:definition给出二叉树的定义
               操作结果:按definition构造二叉树T

           ClearBiTree(&T)
               初始条件:二叉树T存在
               操作结果:将二叉树T清为空树

           BiTreeKmpt(T)
               初始条件:二叉树T存在
               操作结果:若T为空二叉树,则返回TRUE,否则返回FALSE

           BiTreeDepth(T)
               初始条件:二叉树T存在
               操作结果:返回T的深度
           
           Root(T)
               初始条件:二叉树T存在
               操作结果:返回T的根

           Value(T,e)
               初始条件:二叉树T存在,e是T中某个结点
               操作结果:返回e的值

           Assign(T,&e,value)
               初始条件:二叉树T存在,e是T中某个结点
               操作结果:结点e赋值为value

           Parent(T,e)
               初始条件:二叉树T存在,e是T中某个结点
               操作结果:若e是T的非根结点,则返回它的双亲,否则函数值为NULL

           LeftChild(T,e)
               初始条件:二叉树T存在,e是T中某个结点
               操作结果:返回e的左孩子,若e无左孩子,则返回NULL

           RightChild(T, e)
              初始条件 : 二叉树T存在, e是T中某个结点
              操作结果 : 返回e的右孩子, 若e无右孩子, 则返回NULL
           
           LeftSibling(T, e)
              初始条件 : 二叉树T存在, e是T中某个结点
              操作结果 : 返回e的左兄弟,若e是T的左孩子或无左兄弟, 则返回NULL

           RightSibling(T,e)
               初始条件:二叉树T存在,e是T中某个结点
               操作结果:返回e的右兄弟,若e是T的右孩子或无右兄弟,则返回NULL

           InsertChild(T,p,LR,c)
               初始条件:二叉树T存在,p指向T中某个结点,LR为0或1,非空二叉树c与T不相交且右子树为空
               操作结果:根据LR为0或1,插入c为T中p所指结点的左或右子树,p所指结点的原有左或右子树则
                        称为c的右子树

           DeleteChild(&T,&p,LR)
               初始条件:二叉树T存在,p指向T中某个结点,LR为0或1
               操作结果:根据LR为0或1,选择删除T中p所指结点的左或右子树

           PreOrderTraverse(T,Visit())
               初始条件:二叉树T存在,Visit是对结点操作的应用函数
               操作结果:先序遍历T,对每个结点调用函数Visit一次且仅一次,一旦Visit()失败,则
               操作失败

           InOrderTraverse(T,Visit())
               初始条件:二叉树T存在,Visit是对结点操作的应用函数
               操作结果:中序遍历T,对每个结点调用函数Visit一次且仅一次,一旦Visit()失败,则
               操作失败

           PostOreadTraverse(T,Visit())
               初始条件:二叉树T存在,Visit是对结点操作的应用函数
               操作结果:后序遍历T,对每个结点调用函数Visit一次且仅一次,一旦Visit()失败,则
               操作失败

           LevelOreadTraverse(T,Visit())
               初始条件:二叉树T存在,Visit是对结点操作的应用函数
               操作结果:层次遍历T,对每个结点调用函数Visit一次且仅一次,一旦Visit()失败,则
               操作失败
    }ADT BinaryTree
}

上述数据结构的递归定义表明二叉树为空,或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成,由于这两棵子树也是二叉树,则由二叉树的定义,它们可以是空树,由此,二叉树可以有5种基本形态,如下图所示:

img

关于有关树的术语也适用于二叉树

二叉树的性质

二叉树具有下列重要特性

性质1 在二叉树的第i层最多有2^i-1个结点(i>=1)

  • 利用归纳法容易证得此性质,i=1时,只有一个根结点,显然,2^i-1=2^0=1是对的
  • 现在假定对所有的j,1<=j<i,命题成立,即第j层上至多有2^j-1个结点,那么,可以证明j=i时命题也成立
  • 由归纳假设:第i-1层上至多有2^i-2个结点,由于二叉树的每个结点的度至多为2,故在第i层上的最大结点数为第i-1层上的最大结点数的2倍,即2*2^i-2=2^i-1

性质2 深度为k的二叉树至多有(2^k)-1个结点(k>=1)

  • 因为除了根结点其余每个结点都为2个

性质3 对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1

设n1为二叉树T中度为1的结点数,因为二叉树中所有结点的度均小于或等于2,所以其结点总数为:

n=n0+n1+n2

再看二叉树中的分支数,除了根结点外,其余结点都有一个分支进去,设B为分支总数,则n=B+1.

由于这些分支是由度为1或2的结点射出的,所以又有B=n1+2n2于是得到:

n=n1+2n2+1

由上俩式子可得:n0=n2+1

完全二叉树和满二叉树是两种特殊形态的二叉树

一棵深度为k且有(2^k)-1个结点的二叉树称为满二叉树,如下图所示,这种数的特点是每一层上的结点数都是最大结点数

img

可以对满二叉树的结点进行连续编号,约定编号从根结点起,自上而下,自左至右,由此可以引出完全二叉树的定义。深度为k的,有n个结点的二叉树,当且仅当其每一个结点与深度为k的满二叉树中编号从1至n 一 一对应时

称之为完全二叉树

img在各个版本的书籍中对完全二叉树的定义均不同,这里统一按严姥书籍如上定义

如上图所示,是一棵深度为4的完全二叉树。显然,这种树的特点是:

  1. 叶子结点只可能在层次最大的两层上出现
  2. 对任一结点,若其右分支下的子孙的最大层次为l,则其左分支下的子孙的最大层次必为l或l+1

如下图就不是完全二叉树(有称之为完满二叉树):

imgA Full Binary Tree (FBT) is a tree in which every node other than the leaves has two children.

换句话说,所有的非叶子结点的度都是2(只要你有孩子,你就必然是有两个孩子)

完全二叉树将会在很多场合下出现,下面介绍完全二叉树的两个重要特性:

性质4 具有n个结点的完全二叉树的深度为不超过log2n的最大整数加1

  • 假设深度为k,则根据性质二和完全二叉树的定义有:

    • 2^(k-1)-1<n<=(2^k)-1
    • 或 2^(k-1)<=n<2^k
  • 于是k-1<=log2n<k,因为k=不大于log2n的最大整数+1

性质5 如果有一棵n个结点的完全二叉树(其深度为不大于log2n的最大整数+1)的结点按层序编号(从1层到第不大于log2n的最大整数+1,每层从左到右),则对任一结点i(1<=i<n),有:

  1. 如果i-1,则结点i就是二叉树的根,无双亲,如果i>1,则其双亲就是不大于i/2的最大整数
  2. 如果2i>n,则结点i无左孩子(结点i为叶子结点)否则其左孩子就是2i
  3. 如果2i+1>n,则结点i无右孩子,否则其右孩子就为2i+1

我们只需要证明性质2和性质3,并可以从2和3导出1,对于i=1,由完全二叉树的定义,其左孩子是结点2,若2>n,则不存在结点2,此时结点i无左孩子,结点i的右孩子也只能是结点3,若结点3不存在,即3>n,此时结点i无右孩子

对于i>1可分两种情况讨论:

  1. 设第j(1<=j<=不大于log2n的最大整数)层的第一个结点的编号为i(由二叉树的定义可知i=2^(i-1)),则其左孩子必为第j+1层的第一个结点,其编号为2^j=2(2^(j-1))=2i

    • 若2i>n,则无左孩子,其右孩子必为第j+1层的第二个结点,其编号为2i+1
    • 若2i+1>n,则无右孩子
  2. 假设第j(1<=j<=不大于log2n的最大整数)层上某个结点的编号为i(2^(j-1)<=i<(2^j)-1),且2i+1<n,则其左孩子为2i,右孩子为2i+1

    • 又编号为i+1的结点是编号为i的结点的右兄弟或者堂兄弟
    • 若它由左孩子,则编号必为2i+2=2(i+1),若它有右孩子,则其编号必为2i+3=2(i+1)+1

可由下图来理解完全二叉树中左右孩子结点之间的关系:

img

img参考大佬博客

二叉树的存储结构

顺序存储结构:

#define MAX_TREE_SIZE 100//二叉树的最大节点数
typedef TElemType SqBiTree[MAX_TREE_SIZE];//0号单元存储根结点
SqBinTree bt;

按照顺序存储结构的定义,在此约定,用一组连续的存储单元依次自上而下,自左至右存储完全二叉树的结点元素,即将完全二叉树上编号为 i 的结点元素存储在如上定义的一维数组中,下标为 i - 1 的分量中。

例如下图所示的两种顺序存储结构树:

img

对于一般二叉树,则应将其每个结点与完全二叉树上的结点相对照,存储在一维数组的相应分量中,图中以“0”表示不存在此结点,由此可见,这种顺序存储结构仅适用于完全二叉树。

因为在最坏的情况下,一个深度为k且只有k个结点的单支树(树中不存在度为2的结点)却需要长度为(2^k)-1的一维数组

链式存储结构:

设计不同的结点结构可构成不同形式的链式存储结构,由二叉树的定义得知,二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成,则表示二叉树中的链表中的结点至少包含3域:

数据域、左指针域、右指针域

如下图所示:

img

img

有时,为了便于找到结点的双亲,则还可以在结点结构中增加一个指向其双亲结点的指针域,利用这两种结点结构所得二叉树的存储结构分别称之为二叉链表和三叉链表,链表的头指针指向二叉树的根结点。

如下图所示:

img

容易证得,在含有n个结点的二叉链表中n+1个空链域,在后面我们将会知道可以利用这些空链域存储其他有用信息,从而得到另一种链式存储结构——线索链表

以下是二叉链表的定义和部分基本操作的函数原型说明:

typedef int Status;
typedef struct BiTNode {
    TElemType data;
    struct BiTNode* lchild, * rchild;//左右孩子指针
}BiTNode,*BiTree;

//-------------基本操作的函数原型说明(部分)-------------
Status CreateBiTree(BiTree* T);
//按先序次序输入二叉树中结点的值(一个字符),#字符代表空树
//构造二叉链表表示的二叉树T

Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//先序遍历二叉树T,对每个结点调用函数Visit,一次且仅一次
//一旦Visit()失败,则操作失败

Status InOrderTraverse(BiTree T, Status(*Visit)(TElemTypde e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//中序遍历二叉树T,对每个结点调用函数Visit,一次且仅一次
//一旦Visit()失败,则操作失败

Status PostOrderTraverse(BiTree T.Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//后序遍历二叉树T,对每个结点调用函数Visit,一次且仅一次
//一旦Visit()失败,则操作失败

Status LevelOrderTraverse(BiTree T, Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//层次遍历二叉树T,对每个结点调用函数Visit,一次且仅一次
//一旦Visit()失败,则操作失败

在不同的存储结构中,实现二叉树的操作方法也不同,如找结点x的双亲PARENT(T,e),在三叉链表中很容易实现,而在二叉链表中则需从根结点出发寻找

由此,具体应用中采用什么存储结构,除根据二叉树的形态之外还需要考虑需进行何种操作,在以下我们将会对这三种存储结构做一个比较

本文链接:

https://nullcode.fun/41.html
1 + 6 =
快来做第一个评论的人吧~