[理学]数据结构Chapter 10.ppt

树结构 树结构（续一） 树是一种层次化的结构，各个元素存储在树枝上，树枝从根开始向下延伸。如上一页图所示的就是一个公司的组织结构。 树结点按照所在的高度被划分为不同的层，根结点在最高层。任何结点都可以有多个后继，这些后继比该结点低一个层次。所以，树是一种非线性的数据结构。 在广义树中，每个结点可以有多于两个的后继结点，但它们的应用很有限，只有诸如文件结构这样的有限的应用。 树结构（续二） 树结构（续三） 其他大部分应用都涉及到一类特殊的树，称为二叉树。 二叉树中的每一个结点最多可以有两个后继结点。 如上一页图所示，编译器将这个表达式拆开并创建一棵二叉表达式树。在这棵树中，每个变量（a、b、c、d、e）占据了一个叶结点的位置，运算符（+、-、*）则是在非叶结点的位置。 二叉树结构很适合用来表示表达式，因为在表达式中只有一元和二元运算符。 树结构（续四） 树结构（续五） 在一棵树中，有一个唯一的起始结点，称为根结点。其余的结点都从根结点延伸出来。每一个结点包含一个值和零个或多个指向后继结点的指针。 从父结点指向子结点的连接称为边。 从子结点的角度来看，每一个非根结点都有唯一的一个父结点。 我们根据一个结点的子结点数目来给结点分类。没有子结点的称为叶结点，而内结点（非叶结点）至少有一个子结点。 每一个结点都是一棵子树的根结点，子树由该结点和它的子结点组成。 子树的定义使得我们可以给根结点另外一个定义，即以它为根结点的子树就是整棵树本身。 树结点层次和路径长度 树结点层次和路径长度（续一） 由于每一个非根结点只有一个父结点，这样保证了从任何结点到它或其子结点只有唯一的一条路径。 从根结点到任何结点的路径长度为每一个结点定义了一种度量，称为层次。根结点的层次是0。根结点的子结点的层次是1，子结点的子结点的层次是2，依此类推。 树的深度（depth）定义为树中所有结点层次的最大值。 树的深度也是所有从根结点到其它结点的路径中长度的最大值。 树结点层次和路径长度－深度讨论 树结点层次和路径长度－深度讨论 在二叉树中，父结点只有不超过两个的子结点。 二叉树中的每个结点都可以通过两个指针来访问到它的子结点。 我们用左指针和右指针来区分它们，左指针指向了左子树，右指针指向了右子树。 可以注意到每一颗子树都是一棵二叉树，这样我们又可以得到二叉树的递归定义。定义中将二叉树看成是由根结点和子树组成的集合。由定义可知，没有结点的树也是二叉树。 完全二叉树是理想的存储结构，它能将大量的结点聚集在根结点的周围。 深度为n的完全二叉树的第0层到第n-1层的结点是满的，而在第n层，叶子结点则占据了最左边的位置。 上一页图为完全二叉树（深度3）。 树结点层次和路径长度－深度讨论 树结点层次和路径长度－深度讨论 树结点层次和路径长度－深度讨论 二叉树定义 二叉树T是一个具有下列性质之一的有限结点集合： (a)如果结点集合为空集（空树是树），则T是一棵树。 (b)结点集合由根结点R和两个不相交的二叉树——左子树TL和右子树TR组成。T中的结点由R和TL、TR中的结点组成。 参见教材：P438、示例10-1。 二叉树示例选 二叉树结点 二叉树遍历算法 利用顺序容器，可以按照它们在序列中的位置来遍历元素，不如链表和向量。数是非线性的结构，顺序遍历是不行的，因为没有明确的“下一个” 概念。 二叉树是递归结构，每个结点都有值以及两个结点。递归的能力在对每个结点的3个操作步骤中体现。步骤包括访问结点本身并执行某些任务（N），对左结点进行递归操作（L），对右结点进行进行递归操作（R）。进行左右递归时，是遍历相应的子树。一旦到了一棵子树的根结点，算法就重复这3个操作。这样的过程一直持续到到达了一颗空树（pointer == null）。 二叉树遍历算法（中序遍历） 树的递归遍历算法假设对于每个结点都采用同样的顺序来实施3个操作。 中序遍历：按照L、N、R的顺序进行遍历。 其中，N——结点值，L——左结点，R——右结点。 中序遍历（LNR）的具体步骤： （1）遍历左子树（向左） （2）访问结点 （3）遍历右子树（向右） 当对一个结点的操作完成后，回到父结点，继续未完成的任务。 二叉树遍历算法（后序遍历） 后序遍历：按照L、 R 、 N 的顺序进行遍历。 其中，L——左结点，R——右结点， N——结点值。 后序遍历（LRN）的具体步骤： （1）遍历左子树（向左） （2）遍历右子树（向右） （3）访问结点 当对一个结点的操作完成后，回到父结点，继续未完成的任务。 二叉树遍历算法（示例） 参见教材：P44