数据库结构p05_(2)VIP专享VIP免费

第5章树形结构5.1树的概念5.2二叉树5.2.1二叉树的概念5.2.2二叉树的性质5.2.3二叉树的存储5.3二叉树的遍历5.3.1二叉树的遍历方法5.3.2二叉树遍历与递归举例5.4二叉树的生成5.5递归消除5.5.1简单递归消除5.5.2基于栈的递归消除5.6线索二叉树非线性结构，可描述数据元素间一对多的逻辑关系，结点之间形成分支和层次关系，类似于自然界中的树。5.7树和森林5.7.1树、林和二叉树的转换5.7.2树的存储5.7.3树的遍历5.8哈夫曼树及应用5.8.1最优二叉树5.8.2哈夫曼编码5.8.3分类与判定树5.3二叉树的遍历遍历(Traversal)：沿某条搜索路径周游二叉树，对每个结点访问一次且仅访问一次访问是指对结点进行某种处理，处理的内容依具体问题而定，可以是读、写、修改等对非线性结构遍历，得到结点按某种次序排列的一个线性序列，所以遍历可看成非线性结构到线性结构的一种映射方法。5.3.1二叉树的遍历方法一、递归遍历二、层次遍历AAFFGGEEDDCCBB•约定先左后右，则有三种遍历方法：DLR、LDR、LRD，分别称为先序遍历、中序遍历、后序遍历。•二叉树的遍历可分解为3个子问题：访问根，遍历左子树和遍历右子树，分别用D、L、R表示，则有六种遍历方法：DLR、LDR、LRD；DRL、RDL、RLD。•二叉树由根、左子树、右子树三部分组成一、递归遍历一、递归遍历先序遍历(DLR)若二叉树非空(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树。后序遍历(LRD)先序遍历序列：A,B,D,E,G,C,F中序遍历序列：D,B,G,E,A,C,F后序遍历序列：D,G,E,B,F,C,A若二叉树非空(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树。中序遍历(LDR)若二叉树非空(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。AAFFGGEEDDCCBBvoidpreorder(bitreet){//先根遍历if(t==NULL)return;cout<data<lchild);//先根遍历左子树preorder(t−>rchild);//先根遍历右子树}voidinorder(bitreet){//中根遍历if(t==NULL)return;inorder(t−>lchild);//中根遍历左子树cout<data<rchild);//中根遍历右子树}voidpostorder(bitreet){//后根遍历if(t==NULL)return;postorder(t−>lchild);//后根遍历左子树postorder(t−>rchild);//后根遍历右子树cout<data<lchild==NULL&&t−>rchild==NULL)num++;//访问根：若为叶子，则叶子数+1leaf(t−>lchild);//访问左子树：累计其中的叶子...