数据结构课件第十讲二叉树.ppt

算法和数据结构,1,数据结构大话数据结构,崔基哲2012年,算法和数据结构,2,第一章 绪论第二章 算法第三章 线性表第四章 栈和队列第五章 串第六章 树第七章 图第八章 查找第九章 排序,3.二叉树的存储结构,一、顺序存储结构按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。,ABCDEFGHI,问：顺序存储后能否复原成唯一对应的二叉树形状？答：若是完全/满二叉树则可以做到唯一复原。而且有规律：下标值为i的双亲，其左孩子的下标值必为2i，其右孩子的下标值必为2i1（即性质5）例如，对应2的两个孩子必为4和5,即B的左孩子必是D,右孩子必为E。,T0一般不用,讨论：不是完全二叉树怎么办？,答：一律转为完全二叉树！方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。,ABCDE,缺点：浪费空间；插入、删除不便,缺点：浪费空间；插入、删除不便,缺点：浪费空间；插入、删除不便,二、链式存储结构用二叉链表即可方便表示。,一般从根结点开始存储。（相应地，访问树中结点时也只能从根开始）注：如果需要倒查某结点的双亲，可以再增加一个双亲域（直接前趋）指针，将二叉链表变成三叉链表。,二叉树结点数据类型定义：typedef struct BiTNode TElemType data;struct BiTNode*left_child,*right_child;BiTNode,*BiTree;,例：,遍历,二叉树的遍历(traversing binary Tree)是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次,6.8 遍历二叉树和线索二叉树,一、遍历二叉树（Traversing Binary Tree）,遍历定义指按某条搜索路线遍访每个结点且不重复（又称周游）。遍历用途它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。遍历方法牢记一种约定，对每个结点的查看都是“先左后右”。,遍历规则,二叉树由根、左子树、右子树构成，定义为D、L、RD、L、R的组合定义了六种可能的遍历方案：LDR,LRD,DLR,DRL,RDL,RLD若限定先左后右，则有三种实现方案：DLR LDR LRD先(根)序遍历 中(根)序遍历 后(根)序遍历 注：“先、中、后”的意思是指访问的结点D是先于子树出现还是后于子树出现。,例1：,先序遍历的结果是：中序遍历的结果是：后序遍历的结果是：层序遍历的结果是：,A B D E CD B E A CD E B C AA B C D E,口诀：DLR先序遍历，即先根再左再右LDR中序遍历，即先左再根再右LRD后序遍历，即先左再右再根,先序遍历+*/A B C D E前缀表示中序遍历A/B*C*D+E中缀表示后序遍历A B/C*D*E+后缀表示层序遍历+*E*D/C A B,例2：用二叉树表示算术表达式,习题1：写出如图所示的二叉树的前(先)序中序和后序遍历序列.,习题2：若一棵二叉树，左右子树均有三个结点，其左子树的前（先）序序列与中序序列相同，右子树的中序序列与后序序列相同，试构造该树。习题3：一棵非空的二叉树其先序序列和后序序列正好相反，画出这棵二叉树的形状。习题4：已知一棵完全二叉树共有892个结点，试求：树的高度；叶结点数；单支(度为1)结点数；最后一个非终端结点的序号。,下课！,