二叉树的遍历学习心得（四）.doc

二叉树的遍历学习心得 数据结构实验报告 实验三名称：二叉树 姓名：高宁鑫学号：202117525班级：2021175专业：数学与应用数学 指导老师：黄春艳 一、实验目的 （1）掌握二叉树的定义和存储表示，学会建一棵二叉树的方法（2）掌握二叉树的遍历（前序，中序，后序）采用递归和非递归方法 二、实验要求（1）建二叉树（2）遍历 三、实验原理 （1）利用递归原理建立一棵二叉链表的二叉树： 为了让每个结点确认是否有左右孩子，对原二叉树进行扩展，将二叉树中的每个结点的空指针引出一个虚结点，其值为一个特定值“.”获得一个扩展二叉树，通过遍历序列确定一棵二叉树。 （2）进行二叉树的遍历。指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。 四、实验环境 windowsxp系统，vc6软件 五、算法实现及步骤实现的主要算法： （1）首先定义二叉树的存储形式，这里使用了二叉链表typedefstructnode/创建结点类型结构体datatypedata;structnode*lchild;structnode*rchild;bitnode，*bittree;（2）建立一个二叉树 voidcreatbitree（bittree*bt）/用扩展前序遍历序列创建二叉树如果是当前树根置为空否则申请一个新节点/charch;ch=getchar;if（ch=.）*bt=null;else*bt=（bittree）malloc（sizeof（bitnode）;（*bt）->data=ch;creatbitree（&（*bt）->lchild）;creatbitree（&（*bt）->rchild）;（3）建立递归方法二叉树的前序、中序、后序遍历 voidpreorder（bittreeroot）/前序遍历二叉树的递归算法if（root。=null）visit（root->data）;preorder（root->lchild）;preorder（root->rchild）;voidinorder（bittreeroot）/中序遍历二叉树的递归算法if（root。=null）inorder（root->lchild）;visit（root->data）;inorder（root->rchild）;voidpostorder（bittreeroot）/后序遍历求二叉树的递归算法if（root。=null）postorder（root->lchild）;postorder（root->rchild）;visit（root->data）;（4）建立非递归方法二叉树的前序、中序、后序遍历voidpreorder2（bintree*root）/非递归前序遍历stacks;bintree*p=root;while（p。=null|。s.empty）while（p。=null）coutlchild;if（。s.empty）p=s.top;coutisfirst=true;s.push（btn）;p=p->lchild;if（。s.empty）temp=s.top;s.pop;if（temp->isfirst=true）/表示是第一次出现在栈顶temp->isfirst=false;s.push（temp）;p=temp->btnode->rchild;else/第二次出现在栈顶coutdatalchild）;creatbitree（&（*bt）->rchild）;voidvisit（charch）/访问根节点printf（”%c”，ch）;voidpreorder（bittreeroot）/前序遍历二叉树的递归算法if（root。=null）visit（root->data）;preorder（root->lchild）;preorder（root->rchild）;voidinorder（bittreeroot）/中序遍历二叉树的递归算法if（root。=null）inorder（root->lchild）;visit（root->data）;inorder（root->rchild）;voidpostorder（bittreeroot）/后序遍历求二叉树的递归算法if（root。=null）postorder（root->lchild）;postorder（root->rchild）;visit（root->data）;voidmainbittreet;intlayer;layer=0;printf（”请输入二叉树中的元素（以扩展前序遍历序列输入，其中.代表空子树）：n”）;creatbitree（&t）;printf（”前序遍历序列为：”）;preorder（t）;printf（”n中序遍历序列为：”）;inorder（t）;printf（”n后序遍历序列为：”）;postorder（t）; 非递归方法 #include#include#includeusingnamespacestd;typedefstructnodechardata;structnode*lchild，*rchild;bintree;typedefstructnode1bintree*btnode;boolisfirst;btnode;voidcreatbintree（char*s，bintree*&root）/创建二叉树，s为形如a（b，c（d，e）形式的字符串inti;boolisright=false;stacks1;/存放结点stacks2;/存放分隔符bintree*p，*temp;root->data=s0;root->lchild=null;root->rchild=null;s1.push（root）;i=1;while（idata=si;p->lchild=null;p->rchild=null;temp=s1.top;if（isright=true）temp->rchild=p;cout 第 4 页 共 4 页免责声明：图文来源于网络搜集，版权归原作者所以若侵犯了您的合法权益，请作者与本上传人联系，我们将及时更正删除。