第五章 树

• ​1.基本概念

  • ​定义

    • ​非空有限的节点集合

    • ​递归定义

      • ​树根、子树

    • 非递归定义

      • ​父节点、子节点、叶节点、路径

    • ​相关术语

      • ​度（或次数）

      • ​叶节点、分支节点

      • ​结点的层数（根节点为0）

      • ​边、路径、路径长度

      • ​子孙节点、祖先结点

      • ​深度（从根出发）、高度（从叶出发）、树的高度

      • ​森林

    • ​有序树和无序树（默认有序）

    • ​有根树和有序树（本章默认有根）

  • ​比较

    • ​线性结构

      • ​一个前驱、一个后继

    • ​树结构

      • ​一个前驱、多个后继

  • ​表示方法

    • ​集合嵌套

    • ​凹入

    • ​广义表

    • ​树形

  • 基本操作

    • ​判空、求根

    • ​求父亲、求儿子、求兄弟

    • ​建树、求树的深度

    • ​树的遍历

• ​2.二叉树

  • 基本概念

    • ​定义

      • ​递归定义

      • ​五种形态

      • ​可为空，子节点有序，是平行于树的概念

    • ​性质

      • ​层数为i的结点至多$2^i$个

      • ​高度为k的二叉树至少k+1个结点，至多 $2^{k+1}-1$ 个结点

      • ​叶节点数等于度为2的节点数+1

    • ​满二叉树、完全二叉树

      • ​层次顺序编号相同

      • ​父节点、左孩子、右孩子的编号特点

      • ​ $n$ 结点完全二叉树的高度是 $⌊ log_2 n⌋$ 

  • ​存储

    • 顺序存储

      • ​定义

        • ​按层次顺序

        • ​存储空间地址连续

        • ​结点编号反映逻辑关系

      • ​完全二叉树：按层次顺序编号

      • 非完全二叉树：添加虚节点

    • ​链接存储

      • ​节点结构

        • ​数据域、左指针、右指针

        • ​数据域、左指针、右指针、父指针

      • ​操作

        • ​查父节点

          • ​Father(t,p.q)

        • ​查找某个符合条件的结点

          • ​Find(t,item.q)

        • ​删除给定子树

          • ​DST(t), Del(p)

  • ​操作

    • ​遍历

      • 分类

        • ​前序（先根）遍历

          • ​Preorder(t)

        • ​中序（中根）遍历

          • ​Inorder(t)

            • ​NIO(t)

        • ​后序（后根）遍历

          • ​Postorder(t)

            • ​NPO(t)

          • ​逆波兰表达式

        • 层次遍历

          • ​LevelOrder(t)

      • ​前序、后序、层次遍历中任意一个和中序遍历均可确定一棵二叉树

    • ​创建（CreateBinTree）

      • ​需要在先根序列中加入空指针标识符作为输入

    • ​复制（CopyTree）

    • ​计算结点个数、高度等