《数据结构 二叉树 实验报告》由会员分享，可在线阅读，更多相关《数据结构 二叉树 实验报告（24页珍藏版）》请在金锄头文库上搜索。
1、实验报告实验报告 组成员组成员: :常金娥、纪淼、窦慧敏、鲍娜娜、常金娥、纪淼、窦慧敏、鲍娜娜、一、需要求分析（徐林）一、需要求分析（徐林）1.二叉树的实现和运算 I）本演示程序中，先根据所输入的次序顺序字符，创建一个二叉树。输入时， 请按照先序遍历的方式建立二叉树 ，以 #代表此结点左子树或右子树为空。然 后接着便执行二叉树的先序遍历、二叉树的中序遍历、二叉树的后序遍历。 2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“请按照 先序遍历的方式建立二叉树#代表此结点左子树或右子树为空” ， “二叉树的先 序遍历： ” ， “二叉树的中序遍历： ” “二叉树的后序遍历： ” ，由
2、用户在键盘上输入 演示程序中规定的运算命令，相应的输入数据和运算结果显示在其后。 3）程序执行的命令包括： i请输入您要进行的操作 ii1 二叉树的先序遍历： iii2 二叉树的中序遍历： iv3 二叉树的后序遍历： v0 退出二叉树 4）测试数据 AB#C#D#分别执行“二叉树的先序遍历： ” “二叉树的中序遍历： ” “二叉树的后序遍历： ” 。 2.线索二叉树的实现 1）本演示程序中，先按前序输入建立二叉树，以#代表子树为空。增加二个标志 域 LTag 和RTag。 当 LTag=0时， lchild域指示结点的左孩子； 当LTag=1时， lchild 域指示结点的前驱。当 RTag=
3、0 时，lchild 域指示结点的右孩子；当 RTag=1 时， lchild 域指示结点的后继。Link=0 代表是指针，Thread=1 代表是线索。然后 接着线索化中序二叉树的内容，再先序输入数值，创建二叉树，#代表空树，中 序线索化二叉树，最后便执行先序线索输出，中序线索输出，后序线索输出。 2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“请输入 前序二叉树的内容：(线序输入 #代表子树为空） ” ， “输出线索化中序二叉树的内 容： ” ， “请输入一个二叉树： （先序输入数值，创建二叉树，#代表空树 ） ” ， “先 序线索输出” ， “中序线索输出” ， “后序线
4、索输出”之后，由用户在键盘上输入演 示程序中规定的运算命令，相应的输入数据和运算结果显示在其后。 3）程序执行的命令包括： i请输入您要进行的操作 ii请输入一个二叉树： （先序输入数值，创建二叉树，#代表空树 ） iii先序线索输出 iv中序线索输出 v后序线索输出 4）测试数据 AB#C#D#执行“先序线索输出” ， “中序线索输出” ， “后序线索输出” 3.二叉树的实现和运算 1）本演示程序中，先从键盘输入待构造的哈夫曼树中带权叶子结点数 n，来构 造赫夫曼树。接着从键盘输入%d 个整数作为权值，用空格间隔。求出 n 个字符 的赫夫曼树编码。 2）演示程序以用户和计算机的对话方式执行，
5、即在计算机终端上显示“从键盘 输入待构造的哈夫曼树中带权叶子结点数 n： ” ，“从键盘输入%d 个整数作为权值： (用空格间隔)” ， “广义表形式的哈夫曼树： ” ， “哈夫曼树的带权路径长度： ” ， “树 中每个叶子结点的哈夫曼编码： ” ， 由用户在键盘上输入演示程序中规定的运算命 令，相应的输入数据和运算结果显示在其后。 3）程序执行的命令包括： i请输入您要进行的操作 ii从键盘输入待构造的哈夫曼树中带权叶子结点数 n： iii从键盘输入%d 个整数作为权值：(用空格间隔) iv广义表形式的哈夫曼树： v哈夫曼树的带权路径长度： Vi树中每个叶子结点的哈夫曼编码： 4）测试数据
6、AB#C#D# 分别执行“哈夫曼树的带权路径长度： ” ， “树中每个叶子结点的哈夫曼编码： ” 。二概要设计（常金娥）二概要设计（常金娥）1.二叉树的实现和运算 BinTree*CreateTree1(BinTree *T) 初始条件：给二叉树 T 的定义。 操作结果：构造二叉树 T。 BinTree*CreateTree1(BinTree *T) 初始条件：二叉树 T 存在。 操作结果：计算叶子结点的数量。 PreOrderTraverse(T，visit() 初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。 操作结果： 先序遍历 T， 对每个结点调用函数 visit 一次
7、且仅一次。 一旦 visit() 失败，则操作失败。 InOrderTraverse(T，visit() 初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。 操作结果： 中序遍历 T， 对每个结点调用函数 visit 一次且仅一次。 一旦 visit() 失败，则操作失败。 PostOrderTraverse(T，visit() 初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。 操作结果： 后序遍历 T， 对每个结点调用函数 visit 一次且仅一次。 一旦 visit() 失败，则操作失败。2.线索二叉树的实现和运算/-二叉树的二叉线索存储表示- Typedef
8、 enum PointerTag Link,Thread ;/Link=0:指针，Thread=1:线索 Typedef struct BiThrNode TElemTypedata; StructBiThrNode*lchild,*rchild;/左右孩子指针 PointerTagLTag,RTag;/左右标志 BiThrNode, *BiThrTree; BiThreTree *CreateTree() 初始条件：给出二叉树的定义。 操作结果：构造线索二叉树。 void InThread(BiThreTree *T) 初始条件：二叉树 T 存在。 操作结果：对左子树和右子树分别进行线索化。
9、 BiThreTree *InOrderThrTree(BiThreTree *T) 初始条件：二叉树 T 存在。 操作结果：中序线索化二叉树。 void InThrTravel(BiThreTree *Thre) 初始条件：二叉树 T 存在。 操作结果：中序遍历二叉树。3.赫夫曼树的实现和运算 /-赫夫曼树和赫夫曼编码的存储表示- Typedef struct Unsigned int weight; Unsigned int parent, lchild, rchild; HTNode,*HuffmanTree;/动态存储数组赫夫曼树void PrintBTree_int(struct B
10、TreeNode* BT) 初始条件：二叉树 T 已存在。 操作结果：输出二叉树，可在前序遍历的基础上修改。采用广义表格式，元素类 型为 int 。 struct BTreeNode* CreateHuffman(ElemType a, int n) 初始条件：二叉树 T 已存在。 操作结果：根据数组 a 中 n 个权值建立一棵哈夫曼树，返回树根指针。 ElemType WeightPathLength(struct BTreeNode* FBT, int len) 初始条件：赫夫曼树 T 已存在。 操作结果：求哈夫曼树的带权路径长度。 void HuffManCoding(struct BT
11、reeNode* FBT, int len) 初始条件：赫夫曼树 T 已存在。 操作结果：对哈夫曼编码。三、三、详细设计（纪淼）详细设计（纪淼）1二叉树的实现与运算（1）定义结二叉树的结构体 typedef char TELemType; typedef struct BTree TELemType data; struct BTree *lChild; struct BTree *rChild; BinTree; （2）二叉树的创建 BinTree*CreateTree1(BinTree *T) char temp; /scanf(“%c“, temp=getch(); printf(“%c
12、“,temp); if(temp = #) return 0; T = (BinTree *)malloc(sizeof(BinTree); T-data = temp; T-lChild = CreateTree1(T-lChild);/递归创建左子树 T-rChild = CreateTree1(T-rChild);/递归创建右子树 return T; （3）计算叶子结点的个数 int sumleft(BinTree *T) int sum = 0, leftNum, rightNum; if(T) if(!T-lChild) leftNum = sumleft(T-lChild); su
13、m += leftNum; rightNum = sumleft(T-lChild); sum += rightNum; return sum; （4）先序遍历二叉树 void PreOrderTraverse(BinTree *T) if(T) printf(“%c“, T-data); PreOrderTraverse(T-lChild); PreOrderTraverse(T-rChild); （5）中序遍历二叉树 void InOrderTraverse(BinTree *T) if(T) InOrderTraverse(T-lChild); printf(“%c“, T-data);
14、 InOrderTraverse(T-rChild); （6）后序遍历二叉树 void PostOrderTraverse(BinTree *T) if(T) PostOrderTraverse(T-lChild); PostOrderTraverse(T-rChild ); printf(“%c“,T-data ); 2 线索二叉树的实现 （1）增加指针标志 typedef enumLink,Thread PointerTag; typedef char DataType; typedef struct BiThreTree （2）二叉树的二叉线索存储表示 struct BiThrNode
15、int num; char LTag,RTag; /为 1 时表示左右孩子分别指向前驱，后继。struct BiThrNode *lchild,*rchild; ; （3）以先序序列方式人工输入一棵二叉树，输入 0 表示某结点为空 int CreatBiTree(struct BiThrNode *(*T) char _data; /scanf(“%c“, _data=getch(); printf(“%c“,_data); if(_data=#)*T=0; else (*T)=(struct BiThrNode *)malloc(NodeSize); if(!(*T)return ERROR
16、; (*T)-num=_data;(*T)-LTag=0; (*T)-RTag=0; CreatBiTree( CreatBiTree( return OK; （4）中序线索化函数的中序遍历线索化子函数 void InThreadingDeal(struct BiThrNode *T,struct BiThrNode *(*pre) if(T) InThreadingDeal(T-lchild, if(!T-lchild) T-LTag=1; T-lchild=(*pre); if(!(*pre)-rchild) (*pre)-RTag=1;(*pre)-rchild=T; (*pre)=T; InThreadingDeal(T-rchild, （5）中序线索化函
