第六章树和二叉树

第六章数和二叉树

二叉树的定义与特点

二叉树的定义

二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成（即左、右子树次序不能颠倒）。

二叉树的五种形态

空树
只有根节点
右子树为空
左子树为空
左右子树都不为空

二叉树的性质

性质1: 非空二叉树中，第i层（i≥1）上最多为2i-1个结点。
性质2: 深度为k（k>=1）的二叉树中，结点总数最多为2k-1。
性质3: 对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0= n2+1。

满二叉树: 深度为k且含有2k-1个结点的二叉树。
完全二叉树: 在深度为k的满二叉树中，按层次顺序从上到下、每层从左至右，从编号1开始连续取n（0≤n≤2k-1）个结点所构成的二叉树。

性质4: 具有n个结点的完全二叉树的深度为log2n+1。
性质5: 若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：

若i=1，则该结点是二叉树的根，无双亲；否则，编号为i/2的结点为其双亲结点。
若2i>n，则该结点无左孩子；否则，编号为2i的结点为其左孩子结点。
若2i+1>n，则该结点无右孩子结点；否则，编号为2i+1的结点为其右孩子结点。

二叉树的存储

顺序存储

1 2	#define MAXSIZE 1000 typedef TElemType SqBiTree[MAXSIZE + 1];

链式存储

二叉链表

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

三叉链表

typedef struct TriTNode{
    TElemType data;
    struct TriTNode *lchild, *rchild;
    struct TriTNode *parent;
}TiTNode, *TriTree;

二叉树的递归遍历算法

遍历二叉树的概念:
遍历二叉树就是如何按某条搜索路径巡访二叉树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。

遍历实现

:::danger 使用二叉链表

:::

先序遍历

Status PreOrderTraverse(BiTree T){
    if(T){
        Traverse(T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}

中序遍历

Status IneOrderTraverse(BiTree T){
    if(T){
        IneOrderTraverse(T->lchild);
        Traverse(T->data);
        IneOrderTraverse(T->rchild);
    }
}

后序遍历

Status PostOrderTraverse(BiTree T){
    if(T){
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        Traverse(T->data);
    }
}

层次遍历

首先将根入队列，以后若队列不空则出队头元素p，如果p不空，则访问之。然后将其左右孩子入队列，如此循环直到队列为空。

Status LevelTraverse(BiTree T){
    InitQueue(Q); // 初始化队列
    EnQueue(Q, T); // 根入队列
    while(!EmptyQueue(Q)){ // 队列不空则继续遍历
        DeQueue(Q, p); //队头元素出队
        if(p != NULL){
            Traverse(T->data);
            EnQueue(p->lchild);
            EnQueue(p->rchild);
        }
    }
}

Huffman Tree

Huffman Tree 定义

由n个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树，称为哈夫曼树，又称最优二叉树。

如何计算二叉树的带权路径长度？
树中所有叶子结点的带权路径长度之和。记作，WPL=∑wili。
如何计算叶子结点的带权路径长度？
叶子结点的权值乘以该结点的路径长度。
如何计算叶子结点的路径长度？
从根结点到该叶子结点的路径上的分支数目。

Huffman Code

前缀编码

任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。
哈夫曼树中，约定左分支标0，右分支标1，则从根结点到叶子结点的路径上分支字符组成的01字符串构成叶子结点的哈夫曼编码。

第六章 数和二叉树