数据结构_二叉树_实验报告北邮.doc

2011级数据结构实验报告 实验名称： 实验三——二叉树 学生姓名： 班 级： 班内序号： 学 号： 日 期： 2012年12月3日 1．实验要求 1.1实验目的 通过选择下面两个题目之一进行实现，掌握如下内容： 掌握二叉树基本操作的实现方法 了解赫夫曼树的思想和相关概念 学习使用二叉树解决实际问题的能力 1.2实验内容 根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。 二叉树的基本功能： 1、二叉树的建立 2、前序遍历二叉树 3、中序遍历二叉树 4、后序遍历二叉树 5、按层序遍历二叉树 6、求二叉树的深度 7、求指定结点到根的路径 8、二叉树的销毁 9、其他：自定义操作 编写测试main()函数测试线性表的正确性 2. 程序分析 2.1 存储结构 2.2 关键算法分析 创建一个二叉树 通过构造函数创建一个二叉树，构造函数通过调用函数creat()创建二叉树 关于函数creat()的伪代码： 1.定义根指针，输入节点储存的data，若输入“#”，则该节点为空； 2.申请一个新节点，判断它的父结点是否不为空，如果不为空在判断其为左或者右孩子，并把地址付给父结点，把data写入。 char ch; BiNodeT *Q[100]; int front,rear; BiNodeT *root,*S; root=NULL; front=1;rear=0; cout(按层次输入二叉树虚结点输入#，以@结束输入\n); cinch; while(ch!=@) { S=NULL; if(ch!=#) { S=new BiNodeT; S-data=ch; S-lchild=NULL; S-rchild=NULL; } rear++; Q[rear]=S; //结点队 if(rear==1) root=S; else { while(Q[front]== NULLfrontrear) // 如果父结点为空则跳过 { front++; } if (front==rear) break; if(rear%2==0) Q[front]-lchild=S; //新结点为父结点的左孩子 else { Q[front]-rchild=S;//新结点为父结点的右孩子 front++; } } cinch; } return root; } if(root==NULL) return; else{ coutroot-data ; PreOrder(root-lchild); PreOrder(root-rchild); } 时间复杂度：O(n) （3）中序遍历 伪代码： 设置递归边界条件：if root==null则停止递归 递归遍历左子树 打印根节点数据域内容 递归遍历右子树 if (root==NULL) return; //递归调用的结束条件 else{ InOrder(root-lchild); //中序递归遍历root的 左子树 coutroot-data ; //访问根结点的数据域 InOrder(root-rchild); //中序递归遍历root的右子树 } 时间复杂度：O(n) （4）后序遍历 伪代码： 设置递归边界条件：if root==null则停止递归 递归遍历左子树 递归遍历右子树 访问根结点数据域 if (root==NULL) return; //递归调用的结束条件 else{ PostOrder(root-lchild); //后序递归遍历root的左子树 PostOrder(root-rchild); //后序递归遍历root的右子树 coutroot-data ; //访问根结点的数据域 } 时间复杂度：O(n) （5）层序遍历 1.队列Q及所需指针的定义和初始化 2.如果二叉树非空，将根指针入队 3.循环直到队列Q为空 3.1 q=队列Q的队头元素出队 3.2 访问节点q的数据域 coutq-data ; 3.3 若节点q存在左孩子，则将左孩子指针入队 if (q