第五章 数和二叉树

• ​5.1  数和二叉树的定义

  • ​5.1.1 树的定义

    • ​树是n（n>=0）个结点的有限集；

  • ​5.1.2  树的基本术语

    • ​1.结点：树中的一个基独立单元包括一个数据元素及若干指向其他子树的分支

    • ​2.结点的度：结点拥有子树数

    • ​3.树的度：树内各结点度的最大值

    • ​4.叶子：度为零的结点

    • ​5.非终端结点：度不为0的结点

    • ​6.双亲和孩子：节点的子树为孩子，该节点为双亲

    • ​7.兄弟：同一双亲的结点

    • ​8.祖先：从根到该节点的所有节点

    • ​9.子孙：以某结点为根的任意节点

    • ​10.层次

    • ​11堂兄弟

    • ​12树的深度

    • ​13.有序树和无序树

    • ​14.森林

  • ​5.1.3二叉树的定义

    • ​二叉树是n（n>=0）个结点锁构成的集合，它或为非空树，对于非空树T：1.有且仅有一个称为根的结点 2.除根节点以外的其余结点分为两个不想交的子集T1和T2

    • ​二叉树愈树一样具有递归性质，二叉树愈树的区别主要有一下两点

      • ​1.二叉树的每个节点最多有；两个节点

      • ​2.二叉树的子树有左右之分

• ​5.4  二叉树的性质和存储结构

  • ​5.4.41二叉树的性质

    • ​性质1：在二叉树的第i层上之多有2（i-1）个结点

    • ​性质2：深度为k的二叉树至多有2^k-1个结点

    • ​性质3 对任何一个二叉树T，如果其终端节点为n0，度为2的结点数为n2，则n0=n2+1.

  • ​5.4.2二叉树的存储结构

    • ​1.顺序存储结构

    • ​2.链式存储结构

• ​5.5遍历二叉树和线索二叉树

  • ​5.5.1遍历二叉树

    • ​1.遍历二叉树的算法描述

    • ​2.根据遍历二叉树确定二叉树

  • ​线索二叉树

• ​5.2  案例引入

  • ​案例5.1  数据压缩问题

  • ​案例5.2  利用二叉树求解表达式的值

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