数据结构（三）—— 树与二叉树

• 第3章 树与二叉树
• • 树
  • • 基本概念
    • 存储结构
  • 二叉树
  • • 基本概念
    • 顺序存储
    • 链式存储
    • 遍历算法
    • • 先序遍历（根左右）
      • 中序遍历（左根右）
      • 后序遍历（左右根）
      • • 应用——求树的深度
      • 层次遍历
    • 赫夫曼编码

• 森林：是m (m>0) 颗互不相交的树的集合
  
  

#define MaxSize 100
struct TreeNode{
    ElemType value;		//结点中的数据元素
    bool isEmpty;		//结点是否为空
};

//定义一个长度为MaxSize的数组t，按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点
TreeNode t[MaxSize];

typedef struct BiTNode {
    ElemType data;		//数据域
    struct BiTNode *lchild,*rchild;		//左、右孩子指针
    //struct BiTNode *parent;	//父结点指针（三叉链表——查找父结点方便） 
}BiTNode,*BiTree;

• 若二叉树为空，什么也不做
• 若二叉树非空：
  • 访问根结点
  • 先序遍历左子树
  • 先序遍历右子树

void PreOrder(BiTree T){
    if(T != NULL){
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

• 若二叉树为空，什么也不做
• 若二叉树非空：
  • 先序遍历左子树
  • 访问根结点
  • 先序遍历右子树

void PreOrder(BiTree T){
    if(T != NULL){
        PreOrder(T->lchild);
        visit(T);
        PreOrder(T->rchild);
    }
}

• 若二叉树为空，什么也不做
• 若二叉树非空：
  • 先序遍历左子树
  • 先序遍历右子树
  • 访问根结点

void PreOrder(BiTree T){
    if(T != NULL){
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    	visit(T);
    }
}

int treeDepth(BiTree T){
    if(T == NULL)
        return 0;
    else{
        int l = treeDepth(T->lchild);
        int r = treeDepth(T->rchild);
        //树的深度 = Max(左子树深度，右子树深度) + 1
        return l > r ? l+1 :r+1;
    }
}

• 初始化一个辅助队列
• 根结点入队
• 若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）
• 重复上一步直至队列为空

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

typedef struct LinkNode{
    BiTNode *data;		//链数据的类型是一个树结点的指针而不是结点本身
    struct LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *front,*rear;
}LinkQueue;


void LevelOrder(BiTree T){
    LinkQueue Q;
    InitQueue(Q);		//初始化
    BiTNode *p;
    EnQueue(Q,T);		//根结点入队
    while(!isEmpty(Q)){		
        DeQueue(Q,p);
        visit(p);		//访问出队结点
        if(p->lchild != NULL)
            EnQueue(Q,p->lchild);		//左孩子入队
        if(p->rchild != NULL)
            EnQueue(Q,p->rchild);		//右孩子入队
    }
}

• 在带有n个带权结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为赫夫曼树（最优二叉树）
  • 结点的权：有某种现实含义的数值（如结点的重要性等）
  • 结点的带权路径长度：从树根到每一结点的路径长度（经过的边数）之与该结点上权值的乘积
  • 树的带权路径长度：树中所有叶子结点的带权路径长度之和
    
• 赫夫曼编码可用于数据压缩