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