二叉树

二叉树（Binary Tree）

概念：

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

特点：

  • 每个结点最多有两棵子树
  • 左子树和右子树是有顺序的
  • 即使树中某结点只有一颗子树，也要区分它是左子树还是右子树

特殊的二叉树：

  • 满二叉树：在一颗二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。
  • 完全二叉树：对于一棵具有n个节点的二叉树按照层次编号，同时，左右子树按照先左后右编号，如果编号为i的节点与同样深度的满二叉树中编号为i的节点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。

性质：

  • 在二叉树的第i层中至多有2^(i-1)个结点
  • 深度为k的二叉树至多有(2^k)-1个结点
  • 对一棵二叉树，如果叶子节点的个数为n0，度为2的节点个数为n2，则n0=n2+1
  • 具有n个结点的完全二叉树的深度为[log2n]+1
  • 对于一棵有n个结点的完全二叉树的结点按层序号，对任意结点i有
    • 如果i = 1，则结点i是二叉树的根，无双亲；如果i>1，则双亲是结点(i/2)
    • 如果2i>n,则结点i无左右孩子；否则其左右孩子是结点2i
    • 如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1

链式存储结构

typedef int TElemType;

typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;

二叉树的遍历

  • 前序遍历：若二叉树为空，则返回；否则先访问根节点，然后前序遍历左子树，再遍历右子树。

    void PreOrderTraverse(BiTree T)
{
    if(T == NULL)
        return;
    printf("%d",T->data);
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
}

  • 中序遍历：若二叉树为空，则返回；否则从根结点开始，中序遍历跟结点的左子树，然后访问根节点，最后中序遍历右子树

    void InOrderTraverse(BiTree T)
{
    if(T == NULL)
        return
    PreOrderTraverse(T->lchild);
    printf("%d",T->data);
    PreOrderTraverse(T->rchild);
}

  • 后续遍历：若二叉树为空，则返回；否则从左子树到右子树后结点的方式遍历访问左右子树，最后访问根节点

    void PostOrderTraverse(BiTree T)
{
    if(T == NULL)
        return
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
    printf("%d",T->data);
}

经典应用：

赫夫曼树、编码

29 Jan 2020