《数据结构与算法分析》C语言描述

目录

树

树

• 对于大量输入数据，链表的线性访问时间太慢，不宜使用，树可以以平均$O(\log N)$运行时间查找

本章内容

• 了解树是如何实现几个流行的操作系统中的文件系统的
• 看到树如何能够用来计算算术表达式的值
• 指出如何利用树支持$O(\log N)$平均时间进行的各种搜索操作，以及如何细化以得到最坏情况时间界$O(\log N)$，以及当数据存储在磁盘上时如何实现这些操作

树（预备知识）

树的定义

递归方法定义

• 一颗树是一些节点的集合
• 这个集合可以是空集
• 若非空，则一棵树由称作根（root）的节点$r$以及0个或多个非空的(子)树$T_1，T_2，\cdots，T_k$组成
• 这些子树中每一棵的根都被来自根$r$的一条有向的边（edge）所连接
• 一棵树是$N$个节点和$N-1$条边的集合

概念

• 根（root）：见树的定义
• 边（edge）：见树的定义
• 儿子（child）：每一棵子树的根叫做根$r$的儿子
• 父亲（parent）：$r$是每一棵子树的父亲
• 树叶（leaf）：没有儿子的节点
• 兄弟（sibling）：具有相同父亲节点的节点
• 祖父（grandparent）：父亲的父亲
• 孙子（grandchild）：儿子的儿子
• 路径（path）：节点$n_1，n_2，\cdots，n_k$的一个序列，使得对于$1\leq i<k$，节点$n_i$是$n_{i+1}$的父亲（另：从根到每个节点恰好存在一条路径）
• 路径长（length）：路径上边的条数
• 深度（depth）：根到$n_i$的唯一路径的。其中根的深度为0
• 高（height）：$n_i$到一片树叶的最长路径的长。其中所有树叶的高都是0，一棵树的高等于它根的高（定义空树高为-1，仅有根的树高为0）
• 祖先（ancestor）： 如果存在$n_1$到$n_2$的一条路径，那么$n_1$是$n_2$的一个祖先
• 后裔（descendant）：如果存在$n_1$到$n_2$的一条路径，那么$n_2$是$n_1$的一个后裔
• 真祖先（proper ancestor）： 如果$n_1\neq n_2$，那么$n_1$是$n_2$的一个真祖先
• 真后裔（proper descendant）：如果$n_1\neq n_2$，那么$n_2$是$n_1$的一个真后裔
• 第一儿子（FirstChild）
• 下一兄弟（NextSibling）

树的实现

• 实现方法一

  • 思路：每一个节点除数据外还有一些指针，使得节点的每个儿子都有一个指针指向它（即父节点有指向子节点的指针）
  • 缺点：不知道每个节点的儿子数，儿子数可以变化很大并且事先不知道（如果要用数组实现则浪费空间，如果用动态数组则浪费性能）

• 实现方法二

  • 思路：每个节点的所有儿子都放在树节点的链表中

  • 程序：

    typedef struct TreeNode *PtrToNode;
    struct TreeNode
    {
        ElementType Element;
        PtrToNode	FirstChild;		// 第一儿子
        PtrToNode	NextSibling;	// 下一兄弟
    }
    

树的遍历及应用

目录结构应用

• 应用
  • UNIX、VAX/VMS、DOS等许多常用操作系统到目录结构
  • 例如/usr/mark/book/ch.r，每个/都表示一条边
  • 这个分级文件系统非常流行
• 优点
  • 能够使用户逻辑地组织数据（很符合使用习惯吗，像是找文件夹并依次识别名字并打开的过程）
  • 在不同目录下的两个文件还可以使用同样的名字
• 程序——打印实现
  • 略
• 程序策略补充
  • 先序遍历（preorder traversal）：对节点的处理工作是在它诸儿子节点被处理之前进行的
    • 例如：目录（先序）列表
  • 后序遍历（postorder traversal）：对节点的处理工作是在它诸儿子节点被处理之后进行的
    • 例如：计算一个目录大小

二叉树（binary tree）

二叉树模型

• 概念
  • 二叉树是一颗树，其中每个节点的儿子都不能多于两个
• 性质
  • 对于平均二叉树，其深度要比N小得多，这个平均深度是$O(\sqrt N)$
  • 对于二叉查找树（binary search tree），其深度的平均值是$O(\log N)$，但不幸的是，这个深度在最坏情况可以大到$N-1$的

实现

• 思路

  • 因为一颗二叉树最多有两个儿子，所以可以用指针直接指向它们

• 程序

  •   typedef struct TreeNode *PtrToNode;
      typedef struct PtrToNode Tree
      struct TreeNode
      {
          ElementType Element;
          Tree		Left;			// 左节点
          Tree		Right;			// 右节点
      }
    

• 应用

  • 搜索，也有许多与搜索无关的应用，如编译器的设计

表达式树（expression tree）

• 表达式树
  • 表达式树的树叶是操作数（operand），比如常量和变量
  • 其他节点为操作符（operator）
  • 表达式树正好是二叉树
  • 节点含有的儿子有可能多于两个的、一个节点也可能只有一个儿子（如一目减算符）
• 遍历策略
  • 中缀表达式（infix expression）使用中序遍历（inroder traversal）
  • 后缀表达式（postfix expression）使用后序遍历（postorder traversal）
  • 前缀表达式（prefix expression）使用先序遍历（preorder traversal）
• 构造表达式树
  • 栈实现，原理基本同前面的栈一章中的 “计算后缀表达式”

二叉查找树（查找树 ADT）

MakeEmpty

Find

FindMin 和 FindMax

Insert

Delete

平均情形分析

AVL树（带有平衡条件的二叉查找树）

单旋转

双旋转

伸展树（舍弃平衡条件而自调整的二叉查找树）

一个简单的写法

展开

树的遍历

B树（非二叉的查找树）