计算机软件技术基础4 数据结构_3.ppt

数据结构课程的内容 2.4 树和二叉树 一、树的基本概念 1. 树的定义 2. 若干术语 2. 若干术语（续） 3. 树的逻辑结构 一对多（1:n），有多个直接后继（如家谱树、目录树等），但只有一个根结点，且子树之间互不相交。 讨论3：树的链式存储方案应该怎样制定？ 复原困难 5. 树的运算 要明确： 1. 普通树（即多叉树）若不转化为二叉树，则运算很难实现。 2. 二叉树的运算仍然是插入、删除、修改、查找、排序等，但这些操作必须建立在对树结点能够“遍历”的基础上。 二、二叉树的表示和实现 为何要重点研究每结点最多只有两个 “叉” 的树？ 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。 1. 二叉树的定义 2. 二叉树的性质 讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？ 满二叉树：一棵深度为k 且有2k -1个结点的二叉树。（特点：每层都“充满”了结点） 课堂讨论： 对于两种特殊形式的二叉树（满二叉树和完全二叉树）还特别具备以下2个性质： 3. 二叉树的存储结构 讨论2：不是完全二叉树怎么办？ (二) 链式存储结构用二叉链表即可方便表示。 二叉树的链式存储示例： 课堂练习：用二叉链表法（l_child, r_child）存储包含n个结点的二叉树，结点的指针区域中会有 个空指针？ 4. 二叉树的运算——遍历 题1：针对下图写出3种基本的遍历序列。 若已知先序（或后序）遍历结果和中序遍历结果，能否“恢复”出二叉树？ 思考题：　　已知一棵二叉树的先序遍历序列和中序遍历序列分别为：ABDEGCFH和DBEGACFH，则该二叉树的后序遍历序列是什么？ 思路：先画树然后进行后序遍历 　　　　 　　　　 遍历算法如何编程？ 对遍历的分析： 例1：编写递归算法，计算二叉树中叶子结点的数目。 注：要实现遍历运算，必须先把二叉树存入电脑内 三、树与二叉树的转换 树转二叉树举例： 二叉树还原为树举例： 四、树的应用（二叉排序树） 1. 二叉排序树的定义 二叉排序树的优点： 思路：输出叶子结点比较简单，用任何一种遍历算法，凡是左右指针均空者，则为叶子，将其统计并打印出来。 DLR(Node *root) //采用先序遍历的递归算法 { if ( root!=NULL ) //非空二叉树条件，等效于 if(root) {if(!root-lchild!root-rchild) //是叶子结点则统计并打印 {sum++; printf(%d\n,root-data);} DLR(root-lchild); //递归遍历左子树，直到叶子处； DLR(root-rchild); } //递归遍历右子树，直到叶子处； } return(0); } 用空格字符表示‘无孩子’或设指针为空 怎样建树？ 试将下面的二叉树以二叉链表形式存入计算机内。 A B G D F C E 考虑1：输入结点时怎样表示“无孩子”？ 考虑2：以何种遍历方式来输入并建树？ 可以自行设计，将二叉树按先序遍历次序输入： A B C ? ? D E ? G ? ? F ? ? ? (/n) 以先序遍历最为合适，让每个结点都能及时被连接到位。 附：建树算法： BiTNode *CreateBiTree( BiTNode *T ){ //构造二叉树T scanf(“%c”,ch); if(ch==‘ ’)T=NULL; else{ T-data=ch; //生成根结点 BiTNode *t; t= ( BiTNode*)malloc(sizeof(BiTNode)); T-lchild = CreateBiTree(t); //构造左子树 t= ( BiTNode*)malloc(sizeof(BiTNode)); T-rchild = CreateBiTree(t); //构造右子树 } return T; } //CreateBiTree 演 示 程 序 | 建 树 及 遍 历 例2. 如何按层次输出二叉树中所有结点？ 算法思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法，不能用递归算法。 技巧：当根结点入队后，令其左、右孩子结点入队，而左孩子出队时又令它的左右孩子结点入队，……由此便可产生按层次输出的效果。 A B C D E 转换步骤： step1: 将树中同一结点的兄弟相连; 加线 抹线 旋转 讨论1：树如何转为二叉树？