ACM--树解读.ppt

树和二叉树 一、树的定义和基本术语 树：树是n（n大于等于0）个结点的有限集合。当n=0时，称为空树；当n0时，该集合满足如下条件： （1）其中必有一个称为根的特定结点，它没有直接前驱，但有零个或多个直接后续。 （2）其余n-1个结点可以划分成m（m大于等于0）个互不相交的有限集T1，T2，T3，…，Tm，其中Ti又是一棵树，称为根的子树。每棵子树的根结点有且仅有一个直接前驱，但有零个或多个直接后继。 结点：包含一个数据元素及若干指向其它结点的分支信息。 结点的度：一个结点的子树个数称为此结点的度。 叶结点：度为0的结点，即无后续的结点，也称为终端结点。 分支结点：度不为0的结点，也称为非终端结点。 孩子结点：一个结点的直接后继称为该结点的孩子结点。 双亲结点：一个结点的直接前驱称为该结点的双亲结点。 兄弟结点：同一双亲结点的孩子结点之间互称兄弟结点。 祖先结点：一个结点的祖先结点是指从根结点到该结点的路径 上的所有结点。 子孙结点：一个结点的直接后继和间接后继称为该结点的子孙 结点。 树的度：树中所有结点的度的最大值。 结点的层次：从根结点开始定义，根结点的层次为1，根的直接后续的层次为2，以此类推。 树的深度（高度）：树中所有结点的层次最大值。 二叉树：它是另一种树形结构，满足以下两个条件： （1）每个结点的度都不大于2； （2）每个结点的孩子结点次序不能任意颠倒。 由此定义可以看出，一个二叉树中的每个结点只能含有0、1或2个孩子，而且每个孩子有左右之分。我们把位于左边的孩子叫做左子树，位于右边的孩子叫做右子树。下图给出了二叉树的五种基本形态。 二、二叉树的编号 例题： 小球下落 有一棵二叉树，最大深度为D，且所有叶子的深度都相同。所有结点从上到下从左到右编号为1，2, 3，…，2的D次幂减1。在结点1处放一个小球，它会往下落。每个内结点上都有一个开关，初始化全部关闭，当每次有小球落到一个开关上时，状态都会改变。当小球到达一个内结点时，如果该结点上的开关关闭，则往左走，否则往右走，直到走到叶子结点。 一些小球从结点1处依次开始下落，最后一个小球将会落到哪里呢？输入叶子深度D和小球个数I，输出第I个小球最后所在的叶子编号。假设I不超过整棵树的叶子个数。D小于等于20.输出最多包含1000组数据。 样例输入： 4 2 3 4 1 2 128 12345 样例输出： 12 7 512 3 255 36358 分析：对于一个结点k，其左子结点、右子结点的编号分别是2k和2k+1。 #includestdio.h #includestring.h const int maxd=20; int s[1maxd]; void main() { int D,I; while(scanf(%d%d,D,I)==2) { memset(s,0,sizeof(s)); int k,n=(1D)-1; for(int i=0;iI;i++) { k=1; for(;;) { s[k]=!s[k]; k=s[k]?k*2:k*2+1; if(kn) break; } } printf(%d\n,k/2); } } 三、二叉树的递归遍历 对于二叉树T，可以递归定义它的三种遍历方式： 先序遍历、中序遍历和后续遍历。 1、先序遍历 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。 2、中序遍历 （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 3、后序遍历 （1）后序遍历左子树； （2）后序遍历右子树访问根结点； （3）访问根结点。 例题：天平 输入一个树状天平，根据力矩相等原则判断是否平衡。所谓力矩相等，就是WL*DL=WR*DR，其中WL和WR分别为左右两边砝码的重量，D为距离。 采用递归（先序）方式输入：每个天平的格式为WL，DL，WR，DR，当WL或WR为0时，表示该“砝码”实际是一个子天平，接下来会描述这个子天平。当WL=WR=0时，会先描述左子天平，然后是右子天平. 样例输入： 1 0 2 0 4 0 3 0 1 1 1 1 4 4 2 6 3 2 其正确输出为YES。 例题：下落的树叶 给一棵二叉树，每个结点都有一个水平位置；左子结点在它左边1个单位，右子结点在右边1个单位。从左向右输出每个水