根在顶部(见图12-20)。
我们可以把树中的顶点分成三类:根、叶子和内部节点。
表12-1显示了每种节点允许的外出弧和进入弧的数目。
从一给定节点可以直接到达(通过一个弧)的节点称为子节点;从其出发子节点可以直接到达的节点称为双亲。具有相同双亲的节点称为兄弟节点。节点的子孙是指从该节点出发可以到达的所有节点,而从其出发所有的子孙都可以到达的节点称为祖先。树中每个节点都有可能有子树。
1. 二叉树
树中的一种特殊形式的树。二叉树是一棵树,且其中没有一个节点所含有的子树的个数超过两个。换句话说,任一个节点只能有0、1或是2棵子树。这些子树被描述为左子树和右子树。图12-22给出了一棵有两棵子树的二叉树的结构。注意每一棵子树本身也是一棵二叉树。
1. 二叉树的遍历
二叉树遍历要求按照预定的顺序处理每一个节点且仅处理一次。两种常用的遍历次序是深度优先和广度优先。
(1)深度优先遍历
给定一棵由根、左子树、右子树构成的二叉树,我们可以定义6种不同的深度优先次序。计算机科学家已经在文献定义了其中三种的标准名称。另外三种没有名称但很容易导出。图12-24中给出了标准遍历。
●前序遍历。在前序遍历中,根被首先访问,接着是左子树,最后是右子树。前缀pre表示根在子树前面被处理。
●中序遍历。在中序遍历中,先处理左子树,然后是根,最后是右子树。前缀in表示根在子树之间被处理。
●后序遍历。在后序遍历中,根在左右子树都处理完后才处理。前缀post表示根在子树之后被处理。
例12.10图12-25显示了我们使用前序遍历访问树中的每个节点。图中还显示了行走次序。在前序遍历中,当我们从左边经过这个节点时,访问该节点。节点被访问的顺序是:A、B、C、D、E、F。
问题:针对上图写出中序遍历和后序遍历的节点访问顺序。
树包括一组有限的元素,称为节点(或顶点),同时包括一组有限的有向线段,用来连接节点,称为弧。如果树是非空的,其中有一个节点没有进入的弧,该节点称为根。树中的其他节点都可以沿着从根开始的唯一路径到达,该路径是指一系列相邻连接的节点序列。树的结构通常被画成上下颠倒,根在顶部(见图12-20)。
点点赞赏,手留余香
给TA打赏
评论0