二叉树的存储与遍历

《二叉树的存储与遍历》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二叉树的存储与遍历【学习目标】1.熟练掌握二叉链表存储结构；2.熟练掌握遍历二叉树的递归算法，并能够实现二叉树的其它操作；3.了解按层次遍历二叉树的算法，能够熟练写出给定二叉树的各种遍历序列，会根据给定的遍历序列画出二叉树。4.理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系。了解二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。能够熟练地画出给定二叉树的各种线索。【重点难点】遍历二叉树的递归算法及其应用，二叉树线索化§6.2.3二叉树的存储结构§6.3.

2、1遍历二叉树§6.3.2线索二叉树【教学内容】【内容回顾】6.1树的定义和基本术语6.2二叉树-6.2.1二叉树的定义-6.2.2二叉树的性质【课题导入】回顾线性表的存储方法？顺序存储链式存储#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0号单元存储根结点SqBiTreebt;§6.2.3二叉树的存储结构1.顺序存储结构约定用一组地址连续的存储单元依次自上而下，自左至右存储完全二叉树上的结点元素

3、。例1:完全二叉树存储1234567891018910452673例2:非完全二叉树存储ABCDEFABD0C0E000000F12345678910111213142511437注意：1）对于一棵二叉树，若采用顺序存储时，对完全二叉树，比较方便；对非完全二叉树，将会浪费大量存储单元。2）最坏的非完全二叉树是只有右分支,设高度为K,则需占用2K-1个存储单元,而实际只有k个元素,实际只需k个存储单元。因此，对于非完全二叉树，不宜采用顺序存储结构。?顺序结构存储二叉树的优点1）存储时，元素的位置(下标

4、+1)对应其在完全二叉树中的序号。2）可快速方便地访问元素的双亲和左右孩子。2、链式存储表示1）二叉链表2）三叉链表ADEBCFrootlchilddatarchild结点结构1)二叉链表ADECBF例1：typedefstructBiTNode{//结点结构TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;类型定义root2）三叉链表lchilddataparentrchild结点结构例2：对例1C

5、AFEDBtypedefstructTriTNode{//结点结构TElemTypedata;structTriTNode*lchild,*rchild;//左右孩子指针structTriTNode*parent;//双亲指针}TriTNode,*TriTree;类型定义例3：链式存储结构示例ACFEDBADBCEF∧∧∧∧∧∧∧A∧∧∧∧∧BCDEF∧∧∧∧∧∧∧二叉链表三叉链表注意：对于一棵二叉树,若采用二叉链表存储时,当二叉树为非完全二叉树时,比较方便,若为完全二叉树时,将会占

6、用较多存储单元(存放地址的指针)。若一棵二叉树有n个结点,采用二叉链表作存储结构时,共有2n个指针域,其中只有n-1个指针指向左右孩子,其余n+1个指针为空。??在二叉链表结构中的操作查询元素？查询元素的后继？查询元素的前驱？这种存储结构的特点是:寻找孩子结点容易，双亲比较困难。§6.3.1遍历二叉树3、先左后右的遍历算法1、导入2、先上后下的按层次遍历4、遍历二叉树的应用问题：怎样在二叉树中查找具有某种特征的结点？怎样对二叉树中全部结点逐一进行某种处理？1、导入遍历二叉树：即如何按照某条搜索路径巡

7、访二叉树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。“访问”的含义可以很广，如：输出结点的信息，对结点进行统一的操作等。对“二叉树”而言，可以有两条搜索路径：先上后下的按层次遍历；先左（子树）后右（子树）的遍历；从第一层开始，同一层从左到右。例1：如右图按层次遍历序列为：ABFCGDEH特点:先被遍历的结点的孩子先于后遍历的结点的孩子遍历。BACDEFGHBACDEFGH2、先上后下的按层次遍历根据二叉树的结构，分为三部分：L左子树D根结点R右子树遍历二叉树的方法：先序遍历DLR中序遍历

8、LDR后序遍历LRD由于其中的左右子树也是二叉树，属于递归结构，所以常常借助递归算法实现。DLR3、先左后右的遍历算法若二叉树为空，则空操作；否则，访问根结点；先序遍历左子树；先序遍历右子树。DLRDLR1）先序遍历算法DLRADLRDLR□B□□D□□CDLR先序遍历序列：ABDC例2:先序遍历ADBC□□□□□voidPreorder(BiTreeT){if(T){//如果二叉树不为空printf(T->data);//输出根结点Preorder(T->lchil