Lipsky

树和二叉树

字数统计: 410阅读时长: 1 min
2019/05/27 Share

树与二叉树#

引子#

查找:根据某个给定关键字 K,从集合 R 中找出关键字与 K 相同的记录#

  • 静态查找:集合中记录是固定的。没有插入和删除操作,只有查找

    • 顺序查找:(通过设置哨兵,进行判断是否找到元素或者是否到达表末尾)

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      int SequentialSearch(list Tbl, ElementType k){
      int i;
      Tb1->Element[0] = k; //建立哨兵,最后函数返回的时候如果值为0,则没找到
      for(i = Tab->Length; Tb1->Element[i]!=k; i--);
      return i;
      }

      typedef struct LNode *List;
      struct LNode{
      ElementType Element[MAXSIZE];
      int Length;
      };

      顺序查找的时间复杂度为 O(n)

    • 二分查找(Binary Search)

      假设 n 个数据元素的关键字满足有序(比如:小到大)

      并且是连续存放(数组),那么可以进行二分查找。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      int BinarySearch(List Tal, ElementType K){
      int left, right, mid, NoFound = -1;

      left = 1; /*初始左边界*/
      right = Tbl->Length;
      while(left <= right){
      mid = (left+right)/2;
      if(K < Tbl->Element[mid]) right = mid-1;
      else if(K > Tbl->Element[mid]) left = mid+1;
      else return mid;
      }
      return NotFound; /*查找不成功,返回-1*/
      }

      11个元素的二分查找判定树

      Screen Shot 2019-05-27 at 22.16.28

      平均成功查找次数:

      ASL = (4*4 + 4*3 + 2*2 + 1)/11 = 3

  • 动态查找:集合中记录是动态变化的,除查找,还可能发生插入和删除

树形结构#

  • 二叉树
    • 概念:
      • 定义
      • 存储结构
    • 操作:
      • 三种遍历
      • 线索二叉树
    • 应用:
      • 排序二叉树—平衡二叉树
      • 哈夫曼树
  • 树和森林:
    • 概念:
      • 定义
      • 存储结构
    • 操作:
      • 与二叉树的转换
      • 遍历
    • 应用:并查集
CATALOG
  1. 1. 树与二叉树#
    1. 1.1. 引子#
      1. 1.1.1. 查找:根据某个给定关键字 K,从集合 R 中找出关键字与 K 相同的记录#
    2. 1.2. 树形结构#