- 知识点摘要：

• 一般树的实现：父节点指向第一个左子节点，其余节点由第一个左子结点作为表头以链表的形式描述兄弟节点
• 树的遍历&应用：
  • 先序遍历：
    • 对节点的处理工作在其诸多子节点被处理之前进行
    • 打印目录中所有的文件名

  • 中序遍历

  • 后序遍历
    • 对节点的处理工作在其诸多子节点被处理之后进行
    • 计算每一个目录与文件夹所占磁盘区块个数的总和
• 二叉树
  • 表达式树：
    • 应用：
      • 对表达式树 先/中/后 序遍历以生成 前/中/后 缀表达式
      • 通过后缀表达式生成表达式树：
        • 借助栈。遇到操作数时新增操作数结点并进行存储，遇到操作符时新增操作符结点并Pop栈中的两个结点分别设为其 右 | 左 结点
  • 二叉查找树：
    • MakeEmpty()
    • Find()
    • FindMin()
    • FindMax()
    • Insert()
    • *Delete()
      • 若删除的节点：
        • 为叶子节点，则立即删除
        • 具有一个子节点，则通过其父节点绕过当前节点指向子节点
        • 具有两个子节点，则用其右子树中最小的节点（必然没有左子节点，故可再写一个删除具有一个子节点的情况的节点方法）数据代替当前节点数据并删除

      • 懒惰删除