第四章 树和二叉树



    • 树,二叉树的基本概念
    • 二叉树的存储与遍历
    • 树的存储, 树/森林/二叉树的相互转换
    • 哈夫曼树的结构, 哈夫曼编码


  • 4.1 树的基本概念

    树(tree)的定义:
    树是n(n>=0)个结点的有限集合, 一棵树满足以下两个条件:

    1. 当n=0时, 为空树
    2. 当n>0时, 有且仅有一个称为根的结点, 除根节点外, 其余结点分为m(m>=0)个互不相交的非空集合T...这些集合中每一个都是一棵树, 称为根的子树

    森林(forest)是m(m>=0)棵互不相交的树的集合. 树的每个结点的子树是森林, 删除一个非空树的根,它的子树便构成森林.

    • 度: 树上任一结点所拥有的子树的数目称为该结点的度。
    • 叶子: 度为0的结点称为叶子或终端结点。
    • 树的度: 一棵树中所有结点的度的最大值称为该树的度。
    • 孩子, 双亲(父结点), 兄弟, 子孙, 祖先
    • 层次: 根的层次为1,其余的结点的层次为其双亲的层次加1.
    • 树的高度: 所有结点层次数的最大值称为该树的高度/深度
    • 有序树: 若树中各子树丛左到右是有次序的,不能互换, 称为有序树
    • 无序树: 若树中各结点的子树是无次序的,可以互换,则称为无序树

    树的运算(T树, X结点):

    • 求根 Root(T)
    • 求双亲 Parent(T, X)
    • 求孩子Child(T, X, i)
    • 建树Create(X, Tn, ...)
    • 剪枝Delete(T, X, i)
    • 遍历TraverseTree(T): 访问每个结点, 且每个结点只访问一次


  • 4.2 二叉树

    二叉树(binary tree)是n(n>=0)个元素的有限集合, 该集合或者为空, 或者由一个根及两棵互不相交的左子树和右子树组成, 其中左子树和右子树也均为二叉树。

    二叉树是有次序的, 左右不能互换.

    二叉树有五种基本形态: 空, 只有根, 只有左子树, 只有右子树, 同时有左子/右子树.

    二叉树的基本运算:

    • 初始化Initiate(BT): 建立一个空的二叉树
    • 求双亲Parent(BT, X)
    • 求左子LChild(BT, X), 求右子RChild(BT, X)
    • 建二叉树Create(BT)
    • 遍历: 先序遍历PreOrder(BT), 中序遍历InOrder(BT), 后序遍历PostOrder(BT), 层次遍历LevelOrder(BT)

    性质1: 二叉树第i(i>=1)层上至多有2^(i-1)个结点
    性质2: 深度为k(k>=1)的二叉树至多有 2^k - 1个结点
    性质3: 对任何一棵二叉树, 若度数为0的叶结点个数为n0, 度数为2的结点个数为n2, 则n0 = n2 + 1

    满二叉树: 深度为k(k>=1)且有2^k-1个结点的二叉树称为满二叉树
    完全二叉树: 如果对满二叉树进行编号(从上至下,从左往右), 并且在最下面一层删去部分结点, (删除的结点是连续的并且包含最大编号的结点), 那么这棵树就是完全二叉树

    性质4: 含有n个结点的完全二叉树的深度为floor(log2(n))+1
    性质5: 如果将一个n个结点的完全二叉树按层编号, 则对于任一编号为i(i>=1, <=n)的结点A有:

    1. 若i=1, 则A为根结点; 若i>1, 则Parent(A)为floor(i/2)
    2. 若2i>n, 则结点A既无左孩子也无右孩子; 否则A的左孩子LChild(A)的编号为2i
    3. 若2i+1>n, 则结点A无右孩子, 否则A的右孩子RChild(A)的编号为2i+1


  • 4.3 二叉树的存储结构

    二叉树有两种存储方式: 顺序存储和链式存储。

    顺序存储

    基于完全二叉树的性质5进行顺序存储, 对于非完全二叉树, 需要增加虚拟结点(会有空间浪费的问题)

    链式存储

    二叉树的链式存储最常见的是二叉链表和三叉链表。
    二叉链表的域为: lchild, data, rchild
    三叉链表多了一个parent, 指向双亲结点。


Log in to reply