首页 > 层次遍历树

层次遍历树

发布时间：2023-03-25 10:53:24 来源：文档文库

小中大

字号：

手机查看

一．实验要求
设一棵二叉树中各结点的值互不相同，其前序序列和中序序列分别存于两个一维数组pre[1..n]和mid[1..n]中，试编写算法建立该二叉树的二叉链表。
二．程序设计的基本思想，原理和算法描述
（包括程序的框架结构组织，相关数据结构，输入/输出设计，主要算法和函数的设计思路）思路：
一：利用结构体作为单链表节点，结构体包括奥
（1）数据变量
（2）节点型数据指针的左儿子和右儿子二：输入输出设计

输入需要输入的节点个数和前序遍历的数组，中序遍历的数组输出建立好的二叉树的前序，中序，后序和层次遍历的结果主要运用了递归算法，建立二叉链表
（1）利用输入的二叉树的前序遍历数组，知道根节点的数据，然后在中序遍历数组中找到根节点的位置，在中序数组中将其分为二叉树的左子树和右子树
（2）在利用递归函数，重新调用建树的函数，以子树的前序和中序遍历数组找到其子树的根节点和子树的左子树和右子树
（3）遍历二叉树时也主要运用的递归算法，依次访问二叉树的节点例如
输入：前序数组：abdcef中序数组：dbaecf由前序数组可知根节点数据为a在中序数组中根据根节点的位置，将二叉树的左子树节点与右子树节点分开，得到两个子树的中序遍历数组

三：主要算法
左子树的中序遍历结果：

db(左子树有两个节点

左子树的前序遍历结果：

bd(根据中序在前序中确定确定其跟节点为b，将其地址传回

左子树的中序遍历结果：d(左子树有1个节点左子树的前序遍历结果：d(根据中序在前序中确定确定其跟节点为d，将其地址传回
d根节点为aabc右子树的中序遍历结果：ecf(右子树有三个节点右子树的前序遍历结果：
cef(根据中序在前序中确定确定其根节点为c，将其节点地址传回
ef左子树的中序遍历结果：f(右子树有1个节点左子树的前序遍历结果：f(根据中序在前序中确定确定其跟节点为f，将其地址传回
左子树的中序遍历结果：e(左子树有1个节点左子树的前序遍历结果：e(根据中序在前序中确定确定其跟节点为e，将其地址传回

三．算法的源程序及注释
#includeusingnamespacestd;constintMAXSIZE=100;templatestructbinode//树节点数据类型
{Tdata;binode*lchild,*rchild;};templateclassbitree{private:intnum;//记录树的节点个数binode*root;//树的根节点
Tpre[MAXSIZE],mid[MAXSIZE];//数的前序遍历数组与中序遍历数组
public:bitree({//构造函数，将根节点置空root=NULL;}binode*rooted(binode*r{//将建立的二叉树的根节点传回函数root=r;}binode*returned({//取得二叉树的根节点returnroot;}intnumed({//取得二叉树的节点个数returnnum;}voidputin(;binode*creattree(intl1/*树前序遍历的第一个节点数据在其数组的位置*/,inth1/*树前序遍历的最后一个节点在其数组中的位置*/,intl2/*树中序遍历第一个节点在其数组中的位置*/,inth2/*树中序遍历最后一个节点在其数组中的位置*/;voidpreorder(binode*root;//前序遍历二叉树voidineorder(binode*root;//中序遍历二叉树voidpostorder(binode*root;//后续遍历二叉树voidbianli(binode*root;//层次遍历二叉树

本文来源：https://www.2haoxitong.net/k/doc/2bc56d0ebe23482fb4da4c77.html