数据结构第四讲二叉树

数据结构2014.2课程大纲第1讲数据结构—应用、概念和课程基础第2讲线性表—链表第3讲队列、堆栈第4讲非线性数据结构--二叉树第5讲堆与线索化二叉树第6讲哈夫曼树与k-d树第7讲检索操作第8讲分块检索与哈希表第9讲排序第10讲算法分析与图的基本概念第11讲图结构第12讲图应用第13讲高级数据结构内容--索引技术第四讲数据结构—二叉树非线性数据结构--二叉树数据结构的效率二叉树的基本概念与性质完全二叉树定义在二叉树上的操作遍历节点计数层次遍历二叉树二叉排序树定义二叉排序树的节点插入二叉排序树的节点删除九宫格基本概念数据结构--队列应用大作业（二）：八数码—开放式作业大作业（二）：八数码—开放式作业背景八数码难题由8个编码为1—8、放在3×3井字画面上可走动的将牌组成。画面上总有一个格是空的，因而可移动空格周围带有数码的将牌走到空格里，或者说空格在移动。要求从初始状态，按照规则，每次移动一步，最终达到目标状态（图1）问题的解是一个合适的走步序列。如“牌6向下移动（用箭头↓、↑、←、→代表移动方向），牌8↑”等等。三要素：问题状态，走步和目标状态牌的每种结构就是问题的状态所有可能的结构集合就构成了问题的状态空间（问题空间）八将牌和一个空格一共有9！中不同的结构（可以分离成对等的两个子空间，每个是181440种状态）问题描述：3×3矩阵图1大作业（二）：八数码—开放式作业移动一次把一个状态转化的另一状态，当有空格四种走步时（↓、↑、←、→），可以一组规则来模仿这些走步每个规则都有某一状态描述必须满足的先决条件。目的是使这些规则能应用于那个状态的描述，比如，“空格上移”有关这条规则的先决条件是从“空格不应处于顶处的行”的要求推导出来的。目标状态是从初始状态开始，经过一系列走步序列后，要达到的某一特殊状态（比如图1）。或者：“达到任一将牌结构，其第一行上将牌的总和是6”。控制策略：不可撤回控制策略、探索回溯控制策略和图形搜索策略。由局部知识构造一个全局系列（知识），是爬山法爬山过程中，寻找函数的极大值，我们在最陡梯度（局部知识）的方向前进。具体来说，用所有“不在位”的将牌与其在目标状态位置的偏差距离之和的最小值的负数，作为状态函数的描述，我们称之为启发性搜索。“距离”是指某个牌与其在目标状态的位置相比较后的偏差距离值。图1中初始状态的函数值是-4，而对目标状态来说，函数值是0.从初始状态出发，上移空格（↑）可获得函数值的最大增加：大作业（二）：八数码—开放式作业图2简单的启发式函数，搜索图1的过程—不可撤回控制策略大作业（二）：八数码—开放式作业队列与堆栈回溯：选一条规则，如果无解，忘掉所有的参与搜索的各步，并选择另一条规则取代。开放式作业（b项必选，其余你可以选择不做）可能会有多个局部的极大值破坏爬山法，比如，图2将使搜索陷入“平顶”或“山脊线”。至少设计一种启发式搜索函数查阅资料—人工智能导论，设计一种更合适的算法。图2大作业（二）：八数码—开放式作业功能1.通过搜索，程序能够由九宫的初始状态逐步移动到达目标状态；2.每一步只能把空格上、下、左或右的一个数字移到空格的位置；3.使用至少三种搜索算法（宽度优先、深度优先、启发式搜索—开放式作业）；4.对比所用算法的优劣。

要求图形界面的人机交互设计，可指定或随机生成九宫的初始状态、目标状态；能指定搜索算法；运行搜索算法前判断是否有解；动画演示搜索过程（深搜）；动画演示最终的移动过程，可单步或多步，可调整运行速度。难点在于时间消耗与算法关系随着初始状态到最终状态的距离加长，时间消耗是指数形式的。比如，一个需要走19步的初始状态到目标状态之间的距离，A算法瞬间可到（启发式搜索），宽度优先搜索需要约30秒，深度优先就是需要数倍的时间了。这是因为相对于迷宫来说，九宫格搜索的状态空间很大。一个100x100的迷宫只有10000格（搜索步），但是3x3的九宫格从初始状态起，能达到的状态有(9！)/2=181440种。至于4x4的九宫格搜索状态就是无法忍受了。换大型机吧。大作业（二）：八数码—开放式作业以下介绍判断重排九宫问题是否有解的方法：1.将当前状态的九宫和目标状态的九宫分别按照自然顺序（先按从左到右的顺序写下第一行，然后按从左到右的顺序写下第二行，最后按从左到右的顺序写下第三行）写成数列形式（空格不写），例如图1写作12384765；2.分别计算当前状态、目标状态写成的排列的逆序数，如果都是偶数或都是奇数，那么重排九宫问题有解，否则无解。

下面介绍计算排列的逆序数的方法（假设排列中有n个数）：1.先看数1，检查有多少个数排在数1前面并且比数1大，记作

；2.再看数2，检查有多少个数排在数2前面并且比数2大，记作

；……n+1.逆序数即为挑战难度把格数增加到4x42.将重排数字改为拼图游戏，如图2所示；3.启发式搜索的算法：A*、A算法等图2.拼图大作业（二）：八数码—开放式作业作业评分完成三部分内容：大作业报告、可运行程序及讲解ppt。报告包含基本原理、程序设计详细、设计心得、源程序清单四个部分。基本原理中除阐述必要的原理性内容外，重点说明在编程中涉及的自己的特色；程序设计部分按照需求分析、概要设计、详细设计等软件开发标准过程展开，重点说明在软件开发的各阶段遇到的主要问题以及解决思路；心得部分说明通过实际问题编程，对于时间消耗的理解，对启发式搜索函数设计方法的思考；讲解要求：参考课堂讲授，简要的阐述所采用的数据结构的基本原理（节点结构、文件存储形式），分析算法的时间效率与空间效率；阐述启发式搜索函数设计方案；运行程序。评分标准（100%）数据结构（50%）：界面风格（40%）基本功能（20%）显示效果（20%）报告写作、讲解ppt制作（10%）第四讲数据结构—二叉树非线性数据结构--二叉树数据结构的效率二叉树的基本概念与性质完全二叉树定义在二叉树上的操作遍历节点计数层次遍历二叉树二叉排序树定义二叉排序树的节点插入二叉排序树的节点删除九宫格基本概念数据结构--队列应用线性结构—链表的效率找粉色球需要爬高6层高度13找灰色球需要爬高7层找绿色球需要爬高8层找黄色球需要爬高9层123456789找红色球需要爬高10层10找橙色球需要爬高11层1112找月亮爬高12层13摘花冠需要爬高13层每次搜寻都从根开始，寻找任何一球的概率相等，平均每次检索的比较次数是多少？平均搜寻次数=(6+7+8+…+13)/8=63/8链头节点非线性结构—二叉树的效率1234567891011121314找粉色球需要搜寻4层找灰色球需要搜寻4层摘花冠需要搜寻4层每次搜寻都从根开始，寻找任何一球的概率相等，平均每次检索的比较次数是多少？平均搜寻次数=8*4/815第四讲数据结构—二叉树非线性数据结构--二叉树数据结构的效率二叉树的基本概念与性质完全二叉树定义在二叉树上的操作遍历节点计数层次遍历二叉树二叉排序树定义二叉排序树的节点插入二叉排序树的节点删除九宫格基本概念数据结构--队列应用树的基本概念树根root根的子树有一个分叉，节点度=1节点度=0，叶子深度=2深度=3最大的节点度数是树的度有三个分叉，节点度=3最大的节点层次是树的深度节点指针域与节点度无关,指针域个数是树的度节点同构树的指针域个数R＝节点数n×树的度k共有10个节点无需指向root,故仅需9个指针空指针域m=n(k-1)+1R=30m=30-9n个节点，只需n-1个指针k越大,指针域浪费越多二叉树的基本概念二叉树它或为空树，或由一个根节点和两棵互不相交的左右子树组成。树根root根的左子树左子树的根右子树的根根的右子树树的定义是递归的叶子的度为0树的度为2这棵子树没有度为1的节点二叉树链式存储结构左指针域右指针域数据域指针域非空，还有孩子指针域空，无后继孩子二叉树基本性质（1）（1）第i层上至多有2i-1个节点第1层有21-1个节点第2层有22-1个节点第3层有23-1

个节点第4层6个节点<24-1每个节点度数最大为2，故第i层上节点数目最多是第i-1层上的2倍，为2i-1个。（2）深度为h的二叉树中至多有2h-1个节点

设深度为h的二叉树有节点数n显然二叉树基本性质（2）（3）任一棵二叉树有n0=n2+1成立n2是度为2节点数n1是度为1节点数n0是度为0节点数左指针数右指针数设指针总数为b，则b=n1+2n2

而n=b+1=n1+2n2+1

因为n=n1+n2+n0

所以只有根节点没有指针指向它满二叉树深度为h且含有2h-1个节点的二叉树为满二叉树1层有21-1个节点2层有22-1个节点3层有23-1个节点4层有24-1个节点每层都有2i-1个节点，所以：二叉树的基本形态空树根节点根与左子树根与右子树左右子树均非空平衡二叉树（AVL）一个平衡二叉树是空树，或者是具有下列性质的二叉树，即它任一节点的左右子树都是平衡的，且左右子树的深度之差的绝对值≤1。它是平衡的它是不平衡的第四讲数据结构—二叉树非线性数据结构--二叉树数据结构的效率二叉树的基本概念与性质完全二叉树定义在二叉树上的操作遍历节点计数层次遍历二叉树二叉排序树定义二叉排序树的节点插入二叉排序树的节点删除九宫格基本概念数据结构--队列应用完全二叉树—逻辑结构n个节点，深度为k，当且仅当所有节点的编号与深度为k的满二叉树前n个结点编号完全相同，称为完全二叉树。12345678910111213节点编号从0开始，顺序进行，没有空缺，n个节点，编号为n-1。如果按照编号，顺序的排列所有节点：0，1,2,3,4,5,6,7,8,9,10,11,12,13root左子树根右子树根左孙1左孙2右孙1右孙2左重孙1左重孙2左重孙3左重孙4右重孙1右重孙2右重孙3从上到下，从左至右顺序展开了二叉树节点逻辑关系与编号一一对应把它看成一个数组，节点编号就是数组下标可以用数组存储一棵完全二叉树0完全二叉树--顺序存储结构顺序存储的物理结构数组下标逻辑关系与物理映射已知节点下标r，查找其右兄弟由数组下标r查找完全二叉树节点逻辑关系已知节点下标r，查找其父节点已知节点下标r，查找其左孩子(4-1)/2=1，a1是父节点2×4+1=9，a9是左孩子2×4+2=10，a10是右孩子4-1=3，a3是左兄弟4不是奇数，没有右兄弟，他也不应该有已知节点下标r，查找其右孩子已知节点下标r，查找其左兄弟完全二叉树--顺序存储结构用二叉树可以描述族谱？第四讲数据结构—二叉树非线性数据结构--二叉树数据结构的效率二叉树的基本概念与性质完全二叉树定义在二叉树上的操作遍历节点计数层次遍历二叉树二叉排序树定义二叉排序树的节点插入二叉排序树的节点删除九宫格基本概念数据结构--队列应用遍历二叉树的方式访问二叉树中每个节点一次且仅一次的过程称为二叉树的遍历先序遍历访问根节点；先序遍历左子树；先序遍历右子树a0a1a3a7a8a4a9a10a2a5a11a6先序序列中序遍历中序遍历左子树；访问根节点；中序遍历右子树a7a3a8a1a9a4a10a0a11a5a2a6后序遍历后序遍历左子树；后序遍历右子树；访问根节点；a7a8a3a9a10a4a1a11a5a6a2a0遍历的定义是递归的中序遍历程序设计二叉树节点treenode：structtreenode{ intinfo； structtreenode*left，*right；

}；structtreenode*inorder(structtreenode*root){ if(!root)return(0)；

inorder(root->left)；

printf(“%d”，root->info)；

inorder(root->right)；}递归过程中子树根为空返回一棵二叉树由一组左、右子树构成分解：遍历一棵二叉树的任务可看成遍历一组子树，每一子树仍然是左、右子树构成，直至左、右子树为空后返回。中序遍历，访问一棵左子树直至为空，访问叶子，访问右子树。否则遍历左子树访问根遍历右子树遍历子树的问题是互相独立，且与原问题形式相同，同一个函数、参数不同的逐级调用--分治算法与递归第四讲数据结构—二叉树非线性数据结构--二叉树数据结构的效率二叉树的基本概念与性质完全二叉树定义在二叉树上的操作遍历节点计数层次遍历二叉树二叉排序树定义二叉排序树的节点插入二叉排序树的节点删除九宫格基本概念数据结构--队列应用后序遍历的二叉树结点计数intcounter(structtree*root){ inti=0; if(!root)return(0); i+=counter(root->left);

i+=counter(root->right);

return(++i);}对左子树结点累计对右子树结点累计对子树根结点累计如何设计一个前序形式？中序遍历的的二叉树结点计数structtree*inorder(structtree*root,int*n){ if(!root)return(0); inorder(root->left,n); *n+=1; printf("%d,",root->key); inorder(root->right,n);}利用中序遍历对二叉树中的节点计数树根指针使用指针返回参数值该地址里的内容加一计数中序输出二叉树节点序列遍历右子树遍历左子树通过引用对二叉树中的节点计数structtree*inorder_ref(structtree*root,int&rn){ if(!root)return(0); inorder_ref(root->left,rn); rn+=1; printf("%d,",root->key); inorder_ref(root->right,rn);}获得参数别名继续向下传递参数别名参数值加一注意，n是指针第四讲数据结构—二叉树非线性数据结构--二叉树数据结构的效率二叉树的基本概念与性质完全二叉树定义在二叉树上的操作遍历节点计数层次遍历二叉树二叉排序树定义二叉排序树的节点插入二叉排序树的节点删除九宫格基本概念数据结构--队列应用层次遍历二叉树输入根节点指针，按照第1层至第h层的顺序（每层从左至右）遍历二叉树所有节点。访问根访问左子树访问右子树访问左孙1访问左孙2访问右孙1访问右孙2最近的节点先访问队列结构排列出要被访问节点的所有子孙a1

a2

a3

按排列顺序访问节点a4

a5

已知节点所有的子孙，可以舍弃它a6

a7

if(root->left)左根入队if(root->right)右根入队输出根队头元素出队层次遍历二叉树程序设计问题structtree*stack[M],*x;出入队元素是指针，因此队是指针型数组intqueue_out(int&front,intrear,structtree*p[],structtree**rx){ if(rear==front)return(-1); *rx=p[front]; front+=1; return(0);}要返回参数值，需要定义为指针的指针queue_out(front,rear,stack,&x);要返回参数值，需要传递指针变量的地址，就是指针的指针指针出队队满提示队操作正常提示层次遍历二叉树程序设计（引用）voidlayer_traversal(structtree*root){structtree*stack[M],*x,*&rx=x;intfront=0,rear=0,&rfront=front,&rrear=rear;if(root)printf("%d,",root->key);if(root->left)queue_in(front,rrear,stack,root->left);if(root->right)queue_in(front,rrear,stack,root->right);while(rear!=front){ queue_out(rfront,rear,stack,rx); printf("%d,",x->key); if(x->left)queue_in(front,rrear,stack,x->left); if(x->right)queue_in(front,rrear,stack,x->right); }}对指针x的引用定义队头和队尾指针及引用遍历操作左根指针入队右根指针入队队非空，继续遍历过程当前的根出队遍历操作左根指针入队右根指针入队intqueue_out(int&front,intrear,structtree*p[],structtree*&rx){if(rear==front)return(-1);rx=p[front];front+=1;return(0);}指针引用指针出队这是一个指针的队列第四讲数据结构—二叉树九宫格基本概念数据结构--队列应用非线性数据结构--二叉树数据结构的效率二叉树的基本概念与性质完全二叉树定义在二叉树上的操作遍历节点计数层次遍历二叉树二叉排序树定义二叉排序树的节点插入二叉排序树的节点删除二叉排序树—定义与性质二叉排序树或者是空树，或者任一节点具有下列性质：若左子树不空，则左子树每一节点的关键码均小于它的根节点关键码；若它右子树不空，则右子树每一节点的关键码均大于它的根节点关键码；其左右子树也分别是二叉排序树。4523531224907845235312249078左子树结点的值都小于根的值右子树结点的值都大于根的值树的形状依赖于节点输入顺序输入的节点总是被插入到叶子位置每次从根节点开始搜寻要插入或者删除的节点位置

二叉排序树—节点插入输入:45structtree*root; //指示二叉树根节点的指针s=(structtree*)malloc(sizeof(tree));45输入23s=(structtree*)malloc(sizeof(tree));23输入5353s=(structtree*)malloc(sizeof(tree));s=(structtree*)malloc(sizeof(tree));输入12if(s->key<root->key){root->left=s;}12if(!root){s->left=0;s->right=0;root=s;}if(s->key>root->key){root->right=s;}新结点总是插入到叶子位置二叉树节点插入程序structtree*addtree(structtree*root，structtree*r，structtree*s){ if(!r){ r=s; r->left=NULL; r->right=NULL; if(!root)return(r); if(r->key<root->key)root->left=r; else root->right=r; return(root); } else{ if(s->key<r->key)addtree(r,r->left,s); elseif(s->key>r->key)addtree(r,r->right,s); }}root是当前节点r的父亲待插入节点r为空，S被插在根或叶子上空树被插入根、非空被插入到叶子空树时返回当前节点是根若是叶子，小于根入左节点大于根入右节点r非空且非叶子，则开始递归寻找叶子关键码小于父节点递归搜索左子树否则搜索右子树rootrrr->leftr->right二叉排序树—节点删除45235338432010221541被删节点P度为0释放节点free(p)被删节点P度为1Fleft=Pleft;pp被删节点P度为2p为保持有序,用p右子树的最小节点s取代psS左分支必空三种情况：被删节点的度=0；度=1；度=2F左指针置空512free(p)双亲指针置空33二叉排序树—节点删除程序structtree*removehelp(structtree*root,intkey){structtree*p,*q,*temp;if(!root)return(NULL);if(root->key==key){ if(root->left==root->right){free(root);return(NULL);} else{if(root->left==NULL){ p=root->right; free(root);return(p);} else{if(root->right==NULL){ p=root->left;free(root);return(p);} else{ temp=deletemin(root->right); root->key=temp->key;return(root);}}}}else{ if(root->key<key)root->right=removehelp(root->right,key);else root->left=removehelp(root->left,key);return(root);}}找到被删节点对叶子直接删除被删节点左分枝空被删节