树

一、知识要点

1、树的定义、表示和术语

• 定义
  • 树（Tree）是n个节点构成的有限集合。当n = 0时，称为空树；对于任一颗非空树（n > 0），它具备以下性质：
  • 树中有一个称为树根（Root）的特殊节点，用r表示。
  • 树根下的任何子集也是一个树，都称为根节点r的子树（SubTree）。r是这些子树根节点的父节点（Parent）。
• 表示
  • 树中的每条边将某个节点与其父节点连接起来，除根结点外，每个节点有且只有一个父节点，因此一颗有N个节点的树有N-1条边。
  • 树的结点用圆圈表示，圈内用一个数字或字母等符号代表该节点的数据信息。
  • 树中的每个节点都是其子树的根节点。
• 术语
  • 结点的度(Degree)：一个结点的度是其子树的个数。
  • 树的度：树的所有结点中最大的度。
  • 叶结点(Leaf)：是度为0的结点，叶结点也可称为端节点。
  • 父结点(Parent)：是其子树的根节点。
  • 子结点(Child)：对一个结点来讲，其子树的根节点是它的子结点。
  • 兄弟结点(Sibling)：具有同一个父结点的各结点彼此都是兄弟结点。
  • 祖先结点(Ancestor)：沿树根到某一结点路径上的所有节点都是这个结点的祖先结点。
  • 子孙结点(Descendant)：某一结点的子树的所有结点都是这个结点的子孙结点。
  • 结点的层次(Level)：规定根节点在一层，其他任一结点的层次是其父节点的层数加一。
  • 树的深度(Depth)：树中所有结点中最大层次是这棵树的深度。
  • 分支：树中两个相邻结点的连边称为一个分支。
  • 路径的路径长度：从结点n₁到n_k的路径被定义为一个结点序列n₁，n₂，……，n_k。一条路径的长度为这条路径所包含的边（分支）的个数。

2、二叉树

• 二叉树的定义及其逻辑表示

  • 定义：一个二叉树是一个有穷的结点集合。这个集合可以为空，若不为空，则他是由根节点和称为其左子树和右子树的两个不相交的二叉树组成。
  • 逻辑表示：一棵二叉树有五种基本形态
    • 空二叉树
    • 只有根节点的二叉树
    • 只有根节点和左子树T_L的二叉树。
    • 只有根节点的右子树T_R的二叉树。
    • 具有根节点、左节点T_L和右节点T_R的二叉树。

• 二叉树的性质

  • 二叉树的深度小于等于结点数N，其平均深度为O（$\sqrt N$）

    • 斜二叉树（Skewed Binary Tree）：斜二叉树结构最差，深度到达最大N。它所有结点都在同一条线上。
    • 完美二叉树：所有分支结点都有左子树和右子树，并且所有叶结点都在同一层上。
    • 完全二叉树：叶结点只能出现在最下层和次下层，且最下层的叶结点都集中在树的左部。

  • 二叉树的重要性质：

    • 一个二叉树第 i 层的最大结点数为2^i-1，i >= 1。
    • 深度为k的二叉树有最大结点总数2^k - 1，K >= 1。
    • 对任何为空的二叉树T，若n₀表示叶结点的个数、n₂是度为2的非叶结点的个数，那么二者关系为n₀ = n₂ + 1。

• 二叉树的存储结构

  • 顺序存储结构

    • 这种结构是用一组连续的储存单元（比如数组）存储二叉树结点的数据，通常情况下顺序储存结构用于完全二叉树的储存。
    • 具体实现是从树的根结点开始，从上层至下层，每层从左到右，依次给结点编号存到一个数组的对应单元中。
      • 当i / 2 >= 1时，[i / 2]单元是其父结点；当i / 2 == 0时，该节点是树的根节点
      • 当2i <= N时，2i单元是其左孩子，否则无左孩子
      • 当2i + 1 <= N时，2i + 1是其右孩子，否则无右孩子
      • 这种数组的起始单元是1。

  • 二叉树的链表储存

    //二叉树树结构
    struct TNode
    {
        ElementType Data;	//Data域表示这个树结点的数值
        struct TNode *Left;	//Left域表示指向本结点的左子树根节点的指针
        struct TNode *Right;//Right域表示指向本结点的右子树根节点的指针
    };
    typedef struct TNode *BinTree;
    

• 二叉树的操作

  • 二叉树的抽象数据类型定义

    • 类型名称：二叉树（BinTree）
    • 数据对象集：一个有穷的结点集合。这个集合可以为空。
    • 操作集：
      • bool IsEmpty(BinTree BT)：若BT为空则返回true，否则返回false。
      • void Traversal(BinTree BT)：二叉树的遍历，即按某一顺序访问二叉树BT中每一个结点。
      • BinTree CreateBinTree()：创建一个二叉树。

  • 二叉树的遍历

    • 中序遍历：它对任一结点的访问是在遍历完其左子树后进行的，访问此节点后，再对右子树遍历

      void InorderTraversal(BinTree BT)
      {
          if(BT)
          {
              InorderTraversal(BT->Left);
              printf("%d", BT->Data);
              InorderTraversal(BT->Right);
          }
      }
      

    • 先序遍历：访问根节点->先序遍历左子树->先序遍历右子树

      void PreorderTraversal(BinTree BT)
      {
          if(BT)
          {
              printf("%d", BT->Data);
              PreorderTraversal(BT->Left);
              PreorderTraversal(BT->Right);
          }
      }
      

    • 后序遍历：…………

    • 非递归中序遍历：

      //创建一个堆栈，遍历二叉树时，遇到一个结点就把他压栈，然后遍历左子树
      //左子树遍历结束后，出栈这个结点并访问它，然后访问该节点的右子树
      void InorderTraversal(BinTree BT)
      {
          BinTree T;
          Stack S = CreateStack();	//创建空堆栈
          T = BT;	//从根节点出发
          while(T || !isEmpty(S))
          {
              while(T)	//一直向左并将沿途结点压入栈中
              {
                  Push(S, T);
                  T = T->left;
              }
              T = Pop(S);	//结点弹出堆栈
              printf("%d", T->Data);
              T = T->Right;	//转向右子树
      	}
      }
      

    • 层序遍历：

      //创建一个队列，首先将根节点存入队列
      //从队列中取出一个元素，访问该节点，将该节点的左右子树入队，然后重复此操作
      
      void LevelorderTraversal(BinTree BT)
      {
          Queue Q;
          BinTree T;
          if(!BT)
              return;	//若是空树则直接返回
          Q = CreatQueue();	//创建空队列
          Add(Q, BT);	//根节点入队
          while(!IsEmpty)
          {
              T = DeleteQ(Q);
              printf("%d", T->Data);
              if(T->Left)
                  Add(Q);
              if(T->Right)
                  Add(Q);
          }
      }
      

3、二叉搜索树

• 二叉搜索树的定义

  • 非空左子树的所有键值小于其根结点的键值
  • 非空右子树的所有键值大于其根节点的键值
  • 左右子树都是二叉搜索树。

• 二叉搜索树的动态查找

  • 二叉搜索树的查找操作Find

    • 查找从树的根节点开始，如果数为空，返回NULL，表示未找到关键字为X的结点。
    • 搜索树非空，则根节点关键字和X进行比较，依据比较结果，需要进行不同的操作
      • 若根节点关键字小于X，则接下来的搜索在右子树中进行。
      • 若根节点关键字大于X，则接下来的搜索在左子树中进行。
      • 若相等，则返回此节点指针。

    //递归查找法
    Position Find(BinTree BST, ElementType X)
    {
        if(!IsEmpty(BST))
            return NULL;	//查找失败
        if(X > BST->Data)
            return Find(BST->Right, X);
        else if(X < BST->Data)
            return Find(BST->Left, X);
        else
            return BST;
    }
    
    //非递归查找法
    Position Find(BinTree BST, ElementType X)
    {
        while(BST)
        {
        	if(X > BST->Data)
            	BST = BST->Right;
        	else if(X < BST->Data)
            	BST = BST->left;
        	else
                break;
        }
        return BST;	//返回结点或NULL
    }
    

  • 查找最大元素和最小元素

    //最大元素一定在最右分支的端节点上
    //最小元素一定在最左分支的端节点上
    
    //查找最大元素
    Position FindMax(BinTree BST)
    {
        if(!BST)	//空的搜索树返回NULL
            return NULL;
        else if(!BST->Right)	//找到最右端，返回结点
            return BST;
        else
            return FinMax(BST->Right);
    }
    
    //查找最小元素
    Position FindMin(BinTree BST)
    {
        if(!BST)
            return NULL;
        else if(!BST->Left)
            return BST;
        else
            return FindMin(BST->Left);
    }
    

• 二叉搜索树的插入

  • //将X插入二叉搜索树关键是找到要插入的位置
    BinTree Insert(BinTree BST, ElementType X)
    {
        if(!BST)	//若原树为空，则生成并返回一个结点的二叉搜索树
        {
            BST = (BinTree)malloc(sizeof(struct TNode));
            BST->Data = X;
            BST->Left = BST->Right = NULL;
        }
        else	//找要插入元素的位置
        {
            if(X > BST->Data)
                BST->Right = Insert(BST->Right);
            else if(X < BST->Data)
                BST->Left = Insert(BST->Left);
            //如果X已经存在，那么什么都不做
        }
        return BST;
    }
    

• 二叉搜索树的删除

  • 当删除的是叶结点时：可以直接删除，然后修改其父结点的指针。

  • 当删除的结点只有一个孩子节点：删除结点前，需要把删除节点的父结点指向删除节点的孩子结点，然后删除结点。

  • 当删除的结点有左右两棵子树：有两种不同的选择：一种是选取其右子树最小的结点填充它，一种是选取其左子树最大的结点填充它，无论哪种选择，被选择的结点都必定最多只有一个孩子节点

    BinTree Delete(BinTree BST, ElementType X)
    {
        Position Tmp;
        if(!BST)
            printf("要删除的结点未找到\n");
        else
        {
            if(X < BST->Data)
                BST->Left = Delete(BST->Left, X);	//从左子树递归删除
            else if(X > BST->Data)
                BST->Right = Delete(BST->Right, X);	//从右子树递归删除
            else
            {
                //当BST就是要删除的结点
                if(BST->Left && BST->Right)	//如果被删除的结点有左右两颗结点
                {
                    //从右子树找到最小的结点填充
                    Tmp = FindMin(BST->Right);
                    BST->Data = Tmp->Data;
                    //从右子树删除最小元素
                    BST->Right = Delete(BST->Right, BST->Data);
                }
                else
                {
                    //如果被删除的结点有一个或无子结点
                    if(!BST->Left)	//只有右结点或无结点
                        BST = BST->Right;
                    else	//只有左孩子
                        BST = BST->Left;
                    free(Tmp);
                }
            }
        }
        return BST;
    }
    

4、平衡二叉树(AVL树)

• 平衡二叉树的定义

  • 任一结点的左右子树均为AVL树。
  • 根节点的左右子树高度差的绝对值不超过1。
  • 对于二叉树的任一结点T，其平衡因子定义为BF(T) = h_L - h_R，其中h_L和h_R分别是T的左子树和右子树的高度，一般来说平衡因子绝对值大于1就得做平衡调整。
  • 最小不平衡子树：距离插入节点最近的，并且BF的绝对值大于1的结点为根节点的子树是最小不平衡子树。「旋转」纠正只需要纠正「最小不平衡子树」即可。

• 平衡二叉树的旋转调整

  • 2 种「旋转」方式：

    • 左旋

      • 旧根节点为新根节点的左子树。

      • 新根节点的左子树（如果存在）为旧根节点的右子树。

    • 右旋

      • 旧根节点为新根节点的右子树。

      • 新根节点的右子树（如果存在）为旧根节点的左子树。

  • 4 种「旋转」纠正类型：

    • LL 型：插入左孩子的左子树，右旋

    • RR 型：插入右孩子的右子树，左旋

    • LR 型：插入左孩子的右子树，先左旋，再右旋

    • RL 型：插入右孩子的左子树，先右旋，再左旋

  • struct AVLNode
    {
        ElementType Data;
        struct AVLNode *Left;
        struct AVLNode *Right;
        int Height;	//树高
    };
    typedef struct AVLNode *Position;
    typedef Position AVLTree;	//AVL树类型
    
    AVLTree Right_Rotation(AVLTree A)	//右旋函数
    {
        //A必须有一个左子树结点B
        //更新A，B的高度
        AVLTree B = A->Left;
        A->Left = B->Right;
        B->Right = A;
        
        A->Height = GetHeight(A);
        B->Height = GetHeight(B);
        return B;
    }
    
    //左旋函数
    AVLTree left_Rotation(AVLTree A)	
    {
        //A必须有一个右子树结点B
        //更新A，B的高度
        AVLTree B = A->Right;
        A->Right = B->Left;
        B->Left = A;
        
        A->Height = GetHeight(A);
        B->Height = GetHeight(B);
        return B;
    }
    
    //右左旋函数
    AVLTree Right_Left_Rotion(AVLTree A)
    {
        //先将B与C做右旋
        A->Right = Right_Rotion(A->Right);
        //再把A与C做左旋
        A = Left_Rotion(A);
        return A;
    }
    
    //左右旋函数
    AVLTree Left_Right_Rotion(AVLTree A)
    {
        //先将B与C做左旋
        A->Left = Left_Rotion(A->Left);
        //再把A与C做右旋
        A = Right_Rotion(A);
        return A;
    }
    
    AVLTree Insert(AVLTree T, ElementType X)	//将X插入AVL树中，并返回调整后的AVL树
    {
        if(!T)	//若树为空树，则创建一个一个包含该节点的AVL树
        {
            T = (AVLTree)malloc(sizeof(struct AVLNode*));
            T->Data = X;
            T->Right = T->Left = NULL;
            T->Height = 1;
        }
        else if(X < T->Data)	//插入AVL树的左子树
        {
            T->Left = Insert(T->Left, X);
            //如果需要右旋
            if(GetHeight(T->Right) - GetHeight(T->Left) == -2)
                //右旋
                if(X < T->Left->Data)
                    T = Right_Rotion(T);
            	//右左旋
            	else
                    T = Right_Left_Rotion(T);
        }
        else if(X > T->Data)	//插入·AVL树的右子树
        {
            T->Right = Insert(T->Right, X);
            //如果需要左旋
            if(GetHeight(T->Right) - GetHeight(T->Left) == 2)
                //左旋
                if(X > T->Right->Data)
                    T = Left_Rotion(T);
            	//左右旋
            	else
                    T = Left_Right_Rotion(T);
        }
        //更新树高
        T->Height = GetHeight(T);
        return T;
    }
    

5、树的应用

• 堆及其操作

  • 堆的定义和表示

    • 堆最常用的结构是用完全二叉树表示。完全二叉树结点排布及其规律，因此不用指针，而是用数组来实现堆的存储。
    • 堆中的元素是按照完全二叉树的层序存储的，所用的数组起始单元为1，而不是0开始的。
    • 对于下标为i的结点，其父结点的下标为i/2。反过来，结点为i的左右子结点分别为2i和2i+1。
    • 堆分为最大堆和最小堆
      • 最大堆：任一结点的值大于或等于其子结点的值。
      • 最小堆：任一结点的值小于或等于其子结点的值。

  • 最大堆的操作

    //堆的结构
    struct HNode
    {
        ElementType *Data;	//存储元素的数组
        int Size;			//堆当前元素个数
        int Capacity;		//堆的最大容量
    };
    typedef struct HNode *Heap;	//堆结构的定义
    typedef Heap Max_Heap;	//最大堆
    typedef Heap Min_Heap;	//最小堆
    
    #define MAX_DATA 1000	//此值应该根据具体情况定义为大于堆中所有可能元素的值
    
    //创建容量为Max_Size的空的最大堆
    Max_Heap Create_Heap(int Max_Size)
    {
        Max_Heap H = (Max_Heap)malloc(sizeof(struct HNode));
        H->Data = (ElementType *)malloc((Max_Size + 1) * sizeof(ElementType));
        H->Size = 0;
        H->Capacity = Max_Size;
        H->Data[0] = MAX_DATA;	//定义“哨兵”为大于堆中所有可能元素的值
        
        return H;
    }
    
    //判断最大堆是否已满
    bool Is_Full(Max_Heap H)
    {
        return (H->Size == H->Capacity);
    }
    
    //最大堆的插入
    bool Insert(Max_Heap H, ElementType X)
    {
        int i;
        
        if(Is_Full(H))
        {
            printf("最大堆已满\n");
            return false;
        }
        i = H->Size + 1;	//i指向插入后堆中最后一个元素的位置
        for( ; H->Data[i / 2] < X; i /= 2)
            H->Data[i] = H->Data[i / 2];	//上滤X
        H->Data[i] = X;		//将X插入
        
        return true;
    }
    
    //判断最大堆是否为空
    bool Is_Empty(Max_Heap H)
    {
        return (H->Size == 0);
    }
    
    #define ERROR -1	//错误标识应定义为堆中不可能出现的元素
    
    //取出键值最大的元素，并删除一个结点
    ElementType Delete_Max(Max_Heap H)
    {
        int Parent, Child;
        ElementType Max_Item, X;
        
        if(Is_Empty(H))
        {
            printf("最大堆已空\n");
            return ERROR;
        }
        
        Max_Item = H->Data[1];	//取出根节点存放的最大值
        //用最大堆最后一个元素放在根节点，然后下滤结点
        X = H->Data[H->Size];
        H->Size--;	//规模要减少
        for(Parent = 1; Parent * 2 <= H->Size; Parent = Child)
        {
            Child = Parent * 2;
            if((Child != H->Size) && (H->Data[Child] < H->Data[Child + 1]))	
                Child++;	//Child指向左右子树的较大者
            if(X >= H->Data[Child])
               break;	//找到了合适位置
            else	//下滤
                H->Data[Parent] = H->Data[Child];
        }
        H->Data[Parent] = X;
        
        return Max_Item;
    }
    
    //最大堆的建立
    //第一步：将N个元素按顺序存入二叉树中，这一步只要求满足完全二叉树的特性，不管它是否有序
    //第二步：调整各节点元素，以满足最大堆特性
    //这种方法比一个一个插入元素高效
    void Perc_Down(Max_Heap H, int p)
    {
        //下滤：将H中以H->Data[p]为根的子堆调整为最大堆
        int Parent, Child;
        ElementType X;
        
        X = H->Data[p];	//取出根节点存放的值
        for(Parent = p; Parent * 2 <= H->Size; Parent = Child)
        {
            Child = Parent * 2;
            if((Child != H->Size) && (H->Data[Child] < H->Data[Child + 1]))
                Child++;
            if(X > H->Data[Parent])
                break;
            else
                H->Data[Parent] = H->Data[Child];
        }
        H->Data[Parent] = X;
    }
    
    void Build_Heap(Max_Heap H)
    {
        //调整堆中的元素，使其满足最大堆特性
        //这里假设所有元素已存入堆中
        
        int i;
        
        for(i = H->Size / 2; i > 0; i--)
        {
            //从最后一个结点的父结点开始，到根节点1
            Perc_Down(H, i);
        }
    }
    

• 哈夫曼树

  • 哈夫曼树的基本结构

    • 路径长度：从根节点开始沿着某个分支到达该节点的一个结点序列，路径所含的分支数叫做路径的长度。
    • 树的路径长度：树根到各节点的路径长度之和。
    • 结点的带权路径长度：从根结点到该结点之间的路径长度l_k与该结点的权W_k的乘积。其中结点的权是节点中的数据。
    • 树的带权路径长度：树中所有叶子节点的带权路径长度之和。它可以被表示为：$\displaystyle \sum^{n}_{k = 1}{W_k L_k}$。

  • 哈夫曼树的构造

    • 由给定的n个权值{W₁, W₂, W₃, …，W_n}构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F = {T₁, T₂, …, T_n}；

    • 在F中选取根节点权值最小和次小的两颗二叉树作为左右子树构造一棵新的二叉树，其根节点的值为左右二叉树权值之和。

    • 在集合F中删去上一步的两个左右二叉树，并将新的二叉树放入集合F中。

    • 重复上面两步操作，直到最后只剩一颗树时，哈夫曼树就建立好了。

      struct HTNode
      {
          int Weight;		//结点权值
          struct HTNode *Left;	//指向左子树
          struct HTNode *Right;	//指向右子树
      };
      typedef struct HTNode *Huffman_Tree;	//哈夫曼树类型
      
      Huffman_Tree Huffman(MinHeap H)
      {
          //这里最小堆的元素类型为Huffman_Tree
          //假设H->size个权值已经存进H->Data[]->Weight中
          int i, N;
          Huffman_Tree T;
          
          Build_Heap(H);	//将H->Data[]按权值Weight调整为最小堆
          N = H->Size;
          for(i = 1; i < N; i++)
          {
              //做H->Size-1次合并
              T = (Huffman_Tree)malloc(sizeof(struct HTNode));	//建立一个新节点
              T->Left = Delete_Min(H);	//从最小堆中拿出最小权值作为T的左子树
              T->Right = Delete_Min(H);	//从最小堆中拿出最小权值作为T的右子树
              T->Weight = T->Left->Weight + T->Right->Weight;	//权值相加
              Insert(H, T);	//将新T插入最小堆
          }
          return Delete_Min(H);	//返回哈夫曼树根节点指针
      }
      

二、感想

感觉学了后面忘了前面