内容发布更新时间 : 2025/1/23 15:12:04星期一 下面是文章的全部内容请认真阅读。

山东大学软件工程 学院 数据结构 课程实验报告

学号： 姓名： 班级： 软件工程2014级2班 实验题目：堆和搜索树 实验学时： 实验日期： 2015.12.2 实验目的： 掌握堆和搜索树的基本概念，插入、删除方法。 硬件环境： 实验室 软件环境： Vistual Studio 2013 实验步骤与内容： 实验内容： 1、 创建最大堆类。最大堆的存储结构使用链表。 2、 提供操作:堆的插入、堆的删除。堆的初始化。Huffman树的构造。二叉搜索树的构造。 3、 接收键盘录入的一系列整数，输出其对应的最大堆、Huffman编码以及二叉搜索树。 4、 堆排序。 代码体： Binarytree.h #ifndef BINARYTREE_H #define BINARYTREE_H #include using namespace std; #include \ class BinaryTree{ friend class BSTree; friend class Huffman; BinaryTree(){ root = 0; num = 0; } bool IsEmpty(){ return root == 0; } public: };

bool Root(int &x);

void MakeTree(const int& element, BinaryTree& left, BinaryTree& right); void BreakTree(int& element, BinaryTree& left, BinaryTree& right); int Height() const{ return Height(root); }

int NumNode(){ num = 1; NumNode(root); return num; } void PreOrder(){ PreOrder(root); cout << endl; } void InOrder(){ InOrder(root); cout << endl; } void PostOrder(){ PostOrder(root); cout << endl; } void LevelOrder(){ LevelOrder(root); cout << endl; } void Transfer(BinaryTree* t){ t->root = root; root = 0; } void Visit(BinaryTreeNode*); int Height(BinaryTreeNode*) const; void NumNode(BinaryTreeNode*); void PreOrder(BinaryTreeNode*); void InOrder(BinaryTreeNode*); void PostOrder(BinaryTreeNode*); void LevelOrder(BinaryTreeNode*); BinaryTreeNode *root; int num;

private:

#endif

Binarytree.cpp

#include #include #include using namespace std; #include \

void BinaryTree::Visit(BinaryTreeNode *t){ }

void BinaryTree::PreOrder(BinaryTreeNode* t){

if (s.empty()){ } else{

return;

stack s; while (t){

Visit(t);

if (t->RightChild) s.push(t->RightChild); if (t->LeftChild) s.push(t->LeftChild); cout << t->data << \;

}

}

}

t = s.top(); s.pop();

void BinaryTree::InOrder(BinaryTreeNode* t){

stack s; BinaryTreeNode *pre = NULL; while (t){

if (t->LeftChild){

if (pre == t->LeftChild){ }

else if (t->LeftChild->RightChild){ }

BinaryTreeNode *d = t->LeftChild->RightChild; while (d->RightChild){ }

if (pre == d){ } else{ }

if (t->RightChild) s.push(t->RightChild); s.push(t); t = t->LeftChild; Visit(t); pre = t; if (s.empty()){ } else{ }

t = s.top(); s.pop(); return; d = d->RightChild; Visit(t); pre = t; if (s.empty()){ } else{ }

t = s.top(); s.pop(); return;