Fork me on GitHub

树（二）--二叉树

发表于 | 分类于
字数统计: 2,218 | 阅读时长 ≈ 9

二叉树的定义：二叉树是n(n >= 0)个结点的有限集合，该集合或者为空集(空二叉树)，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

基本概念

特点：

  • 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。
  • 左右子树是有顺序的，次序不能任意颠倒。
  • 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

三个结点的树有两种形态，三个结点的二叉树有五种形态

五种基本形态：

  • 空二叉树
  • 只有一个根结点
  • 根结点只有左子树
  • 根结点只有右子树
  • 根结点既有左子树又有右子树

特殊二叉树

斜树

所有结点都只有左子树的树叫做左斜树，所有结点都只有右子树的树叫做右斜树，两者统称斜树。

每一层只有一个结点，结点的个数与二叉树深度相同。

满二叉树

所有分支结点都存在左右子树，且所有叶子结点都在同一层上的二叉树。

特点：

  • 叶子只能出现在最下层
  • 非叶子结点的度一定为2
  • 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多

完全二叉树

对一棵具有n个结点的二叉树按层序编号，如果编号为i(1 <= i <= n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。

mark

满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

特点：

  • 叶子结点只能出现在最下两层
  • 最下层的叶子一定集中在左部连续位置
  • 倒数第二层若有叶子结点，则一定都在右部连续位置
  • 如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况
  • 同样结点数的二叉树，完全二叉树深度最小

二叉树的性质

  • 在二叉树的第i层上至多有2^(i-1)个结点(i >= 1)

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

  • 对任意一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1

    原因：分支总数 = 结点总数 - 1

    ​ n1 + 2*n2 = n0 + n1 + n2 -1

    ​ 故n0 = n2 + 1

  • 具有n个结点的完全二叉树的深度为[log₂n]+1([x]表示不大于x的最大整数)

  • 如果对一棵有n个结点的完全二叉树(其深度为[log₂n]+1)的结点按层序编号，对任一结点i (i <= i <= n)有：

    • 如果i = 1，则结点i是二叉树的根，无双亲；如果i > 1，则其双亲是结点[i/2]
    • 如果2i > n，则i无左孩子(结点i为叶子结点)；否则其左孩子是结点2i
    • 如果2i+1 > n，则i无右孩子；否则其右孩子是结点2i+1

若一个偶数结点下一位奇数结点存在，则该奇数结点为该偶数结点的右兄弟

二叉树的存储结构

顺序存储结构

对于一般二叉树，尽管层次编号不能反映逻辑关系，但可以将其按完全二叉树编号，把不存在的结点设置为”^”，依次存入数组中。

极端情况下，右斜树将造成存储空间极大浪费。(k个结点要分配2^k - 1个存储单元空间)

顺序存储结构一般只用于完全二叉树

二叉链表

二叉树每个结点设计为一个数据域和两个指针域。

结构代码：

1
2
3
4
5
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;

也可以增加一个指向双亲的指针构成三叉链表。

求二叉树高度

1
2
3
4
5
6
7
8
9
10
11
12
13
int PostOrderGetHeight(BiTree T)
{
      int HL,HR,MaxH;
      if(T)
      {
          HL = PostOrderGetHeight(BT->Left);//求左子树的深度
          HR = PostOrderGetHeight(BT->Right);//求右子树的深度
          MaxH =（HL > HR）? HL : HR;//取左右子树较大的深度
          
          return (MaxH+1);//返回树的深度
      }
      else return 0;//空树深度为0
}

​ ~~via文盲

遍历二叉树

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。(从根结点出发并不意味着先访问根结点)

前序遍历(先访问根结点)

若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。ABDGHCEIF

mark

结构代码：

1
2
3
4
5
6
7
8
void PreOrderTraverse (BiTree T)
{
    if (T == NULL)
        return;
    printf("%c",T->data);//可以改为其他对结点的操作
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}

中序遍历(中间访问根结点)

若树为空，则空操作返回，否则从根结点开始，中序遍历根结点的左子树，然后访问根结点，最后中序遍历右子树。GDHBAEICF

mark

结构代码：

1
2
3
4
5
6
7
8
void InOrderTraverse (BiTree T)
{
    if (T == NULL)
        return;
    InOrderTraverse(T->lchild);
    printf("%c",T->data);//可以改为其他对结点的操作
    InOrderTraverse(T->rchild);
}

后序遍历(最后访问根结点)

若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点。GHDBIEFCA

mark

结构代码：

1
2
3
4
5
6
7
8
void PostOrderTraverse (BiTree T)
{
    if (T == NULL)
        return;
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    printf("%c",T->data);//可以改为其他对结点的操作
}

非递归表示法(使用堆栈) – 树的深度优先遍历(中序)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void InOrderTraverse (BiTree T)
{
    Stack S = CreatStack(MaxSize);//创建并初始化堆栈
    while （T || !IsEmpty(S))
    {
        while (T)
        {
            Push(S,T);//压栈
            T = T->Left;//从树左边开始
        }
        if  (!IsEmpty(S))
        {
            T = Pop(S);//结点弹出堆栈
            printf("%c",T->Data);//输出结点
            T = T->Right;//转向右子树
        }
    }
}

层序遍历(使用队列) – 树的广度优先遍历

若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。ABCDEFGHI

mark

使用队列实现~~via文盲：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void LevelOrderTraverse(BiTree T)
{
      Queue Q;//创建队列
      if(!T)
          return;//是空树则直接返回
      Add(Q,T);
      while(!IsEmpty(Q))
      {//循环，直至队列为空
            T = Delate(Q);
            printf("%d\n",T->Data);//访问取出队列的结点  
            if(T->Left)
                Add(Q,T->Left);
            if(T->Right)
                Add(Q,T->Right);
      }
}

二元运算表达树及其遍历

三种遍历得到不同的访问结果：

  • 先序遍历得到前缀表达式。

  • 中序遍历得到中缀表达式：但是中缀表达式可能由于优先级不同，出现问题。

    —- 如何解决？输出左子树之前加左括号，输出右子树之后加右括号。

  • 后序遍历得到后缀表达式。

​ ~~via文盲

计算机只会处理线性序列，这些遍历方法其实都是在把树中的结点变成某种有意义的线性序列，给程序的实现带来好处。

已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

已知前序遍历序列和后序遍历序列，不能确定一棵二叉树。

二叉树的建立

扩展二叉树：将二叉树每个结点的空指针引出一个虚结点，其值为一个特定值(如#)，这种处理后的二叉树为原二叉树的扩展二叉树。

扩展二叉树可以做到一个遍历序列确定一棵二叉树。(确定某一个结点有几个孩子，是否为叶子结点等)

mark

假设用前序遍历生成一个结点均为字符的二叉树：

用键盘输入：AB#D##C##

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//按前序输入二叉树中结点的值(一个字符)
//#表示空树，构造二叉链表表示二叉树T
void CreateBiTree (BiTree *T)
{
    TElemType ch;
    scanf("%c",&ch);
    if (ch == '#')
        *T = NULL;//空结点
    else
    {
        *T = (BiTree)malloc(sizeof(BiTNode));
        if (!*T)
            exit(OVERFLOW);//内存已炸
        else
        {
            *T->data = ch;//生成根结点
            CreateBiTree (&(*T)->rchild);//构造左子树
            CreateBiTree (&(*T)->lchild);//构造右子树
        }
    }
}
-------------本文结束感谢您的阅读-------------
undefined