计算机软件技术基础第2篇-3.pptx

计算机软件技术基础;第2章 基本数据结构及其运算;2.6 树与二叉树;4;5;6;7;树的表示 树形表示法。这是树的最基本的表示,使用一棵倒置的树表示树结构,非常直观和形象。;文氏图表示法。使用集合以及集合的包含关系描述树结构。下图就是树的文氏图表示法。;凹入表示法。使用线段的伸缩描述树结构。下图是树的凹入表示法;括号表示法。将树的根结点写在括号的左边,除根结点之外的其余结点写在括号中并用逗号间隔来描述树结构。下图是树的括号表示法。;12;13;14;15;路径：对于任意两个结点ki和kj,若树中存在一个结点序列ki,ki1,ki2,…,kin,kj,使得序列中除ki外的任一结点都是其在序列中的前一个结点的后继,则称该结点序列为由ki到kj的一条路径,用路径所通过的结点序列(ki,ki1,ki2,…,kj)表示这条路径。 路径的长度:等于路径所通过的结点数目减1(即路径上分支数目)。 可见,路径就是从ki出发“自上而下”到达kj所通过的树中结点序列。显然,从树的根结点到树中其余结点均存在一条路径。 ;17;18;19;+;21;22;23;;25;;27;树的运算 主要分为三大类： 第一类,寻找满足某种特定关系的结点,如寻找当前结点的双亲结点等； 第二类,插入或删除某个结点,如在树的当前结点上插入一个新结点或删除当前结点的第i个孩子结点等； 第三类,遍历树中每个结点,这里着重介绍。;树的遍历运算 指按某种方式访问树中的每一个结点且每一个结点只被访问一次。 树的遍历运算的算法主要有先根遍历和后根遍历两种。注意,下面的先根遍历和后根遍历算法都是递归的。;30;后根遍历 后根遍历过程为： (1) 按照从左到右的次序后根遍历根结点的每一棵子树； (2) 访问根结点。;32;2011-8-23;34;35;36;37;38;39;40;41;42;43;44;45;46;47;先序遍历非递归算法 void PreOrder2(BTNode *b) { BTNode *St[MaxSize],*p; int top=-1; top++; St[top]=b; //根结点入栈 while (top-1) //栈不为空时循环 {p=St[top]; top--; //退栈并访问该结点 printf(%c ,p-data); if (p-rchild!=NULL) //右孩子结点入栈 { top++; St[top]=p-rchild; } if (p-lchild!=NULL) //左孩子结点入栈 { top++; St[top]=p-lchild; } } } ;2.6.3 二叉树的遍历;2.6.3 二叉树的遍历;后序遍历非递归算法 由后遍历过程可知，采用一个栈保存需要返回的结点指针，先扫描根结点的所有左结点并一一进栈，出栈一个结点*b即当前结点，然后扫描该结点的右孩子结点并入栈，再扫描该右孩子结点的所有左结点并入栈。当一个结点的左右孩子结点均访问后再访问该结点，如此这样，直到栈空为止。; 难点：如何判断一个结点*b的右孩子结点已访问过，为此用p保存刚刚访问过的结点（初值为NULL），若b-rchild==p成立（在后序遍历中，*b的右孩子结点一定刚好在*b之前访问），说明*b的左右子树均已访问，现在应访问*b。 ; void PostOrder2(BTNode *b) { BTNode *St[MaxSize];BTNode *p; int flag,top=-1; //栈指针置初值 do { while (b!=NULL) //将*b的所有左结点进栈 { top++; St[top]=b; b=b-lchild; } p=NULL; //p指向栈顶结点的前一个已访问的结点 flag=1; //设置b的左孩子为已访问过;;55;顺序存储结构 二叉树的顺序存储结构中结点的存放次序是：对该树中每个结点进行编号,其编号从小到大的顺序就是结点存放在连续存储单元的先后次序。若把二叉树存储到一维数组中,则该编号就是下标值加1(注意,C/C++语言中数组的起始下标为0)。树中各结点的编号与等高度的完全二叉树中对应位置上结点的编号相同。 ;A;58;59;2011-8-23;2.6.5 二叉树的基本运算及其实现; 求高度BTNodeDepth(*b)：求二叉树b的高度。若二叉树为空,则其高度为0；否则,其高度等于左子树与右子树中的最大高度加l。 输出二