数据结构-二叉树的存储结构和遍历.ppt

《数据结构-二叉树的存储结构和遍历.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、二叉树的存储结构和遍历二叉树的遍历二叉树的存储结构小结和作业顺序存储二叉链表三叉链表链式存储问题的提出递归遍历算法遍历的应用实例二叉树的顺序存储顺序存储是用一组连续的存储单元存放数据顺序存储要求数据是线性结构二叉树是非线性结构如何把二叉树转换为线性结构，而且保持结点之间的父/子关系?二叉树的顺序存储ACGBDEFKLHJIMNO123456789101112131415满二叉树：从上到下，从左往右依次编号二叉树的顺序存储0123456789101112131415数组的下标，也是结点的编号0123456789101

2、112131415ABCEFDGHIJKLMNO二叉树的顺序存储ACGBDEFHJI12345678910完全二叉树：从上到下，从左往右依次编号012345678910ABCEFDGHIJ二叉树的顺序存储ABDCEF一般的二叉树：想象成一个完全二叉树ABDCEF00000000二叉树的顺序存储ABDCEF000000001234567891011121314二叉树的顺序存储ABDCEF125371401234567891011121314ABCDEF012345678910111213141111001000000

3、1如何知道有无数据？#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//1号单元存储根结点SqBiTreebt;二叉树的顺序存储#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefstruct{TElemTypedata[MAX_TREE_SIZE];charflag[MAX_TREE_SIZE];}SqBiTree;二叉树的顺序存储适用于一般的二叉树链式存储—二叉链表lchilddat

4、archild二叉链表的结点结构:左指针域，指向当前结点的左子树数据域，存储当前结点的取值信息右指针域，指向当前结点的右子树指向二叉树根结点头指针：前述二叉树的二叉链表如下所示：AF∧∧E∧C∧D∧∧B∧root链式存储—二叉链表a1a2a3LABDCEF1253714typedefstructBiTNode{//结点结构TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;lchilddatarchild结点结构:二叉链表的C语言类

5、型描述如下:左指针域数据域右指针域链式存储—二叉链表parentlchilddatarchild三叉链表的结点结构:指向双亲结点的指针域左指针域数据域右指针域链式存储—三叉链表rootAEF∧∧∧D∧∧C∧B∧∧二叉树的三叉链表表示：链式存储—三叉链表typedefstructTriTNode{TElemTypedata;structTriTNode*lchild,*rchild;structTriTNode*parent;}TriTNode,*TriTree;三叉链表的C语言类型描述如下:parentlchild

6、datarchild结点结构://结点结构//左右孩子指针//双亲指针链式存储—三叉链表问题的提出在实际应用中，经常需要在二叉树中查找具有某些特征的结点，或者对树中的全部结点逐一进行某种处理，这就提出了二叉树的遍历的问题。问题的提出定义：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。作用：遍历的目的是线性化，使二叉树中的结点能够按照某种次序排列在一个线性队列上，便于处理。问题的提出线性结构的遍历：因为每个结点均只有一个后继，所以只有一条搜索路径。二叉树的遍历：二叉树是非线性结构，

7、每个结点有两个后继，则存在如何遍历即按什么样的搜索路径进行遍历的问题。问题的提出二叉树存在下述三条搜索路径：1．先上后下的按层次遍历；2．先左（子树）后右（子树）的遍历；DLR，LDR，LRD3．先右（子树）后左（子树）的遍历。DRL，RDL，RLD先序（根）遍历左子树右子树根根左子树右子树若二叉树为空树，则空操作；否则，（1）访问根结点（2）先序遍历左子树（3）先序遍历右子树先序（根）遍历ABCDEFGHKABCDEFGHKABCDEFGHK课堂练习ABDCEFABC写出先序遍历的结果voidPreorder(B

8、iTreeT,void(*visit)(TElemType&e)){//先序遍历二叉树1if(!T)return;2visit(T->data);//访问根结点3Preorder(T->lchild,visit);//遍历左子树4Preorder(T->rchild,visit);//遍历右子树}先序遍历中序（根）遍历左子树右子树根根左子树右子树若二叉树为空