数据结构实验2(二叉链表实现二叉树的基本运算)
最后更新于：2022-04-01 20:51:55
包含的二叉树运算: 删除一个二叉树, 求一颗二叉树的高度, 求一颗二叉树中叶子结点数, 复制一颗二叉树, 交换一颗二叉树的左右子树,
自上到下, 自左到右层次遍历一颗二叉树.
增加相关功能完善即可, 层次遍历利用队列作为辅助的数据结构, 元素类型是指向二叉树中结点的指针类型.
实现代码:
~~~
#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "queue"
#include "stack"
#include "cmath"
#include "utility"
#include "map"
#include "set"
#include "vector"
#include "list"
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
template
struct BTNode
{
/* data */
BTNode() { lChild = rChild = NULL; }
BTNode(const T& x) {
element = x;
lChild = rChild = NULL;
}
BTNode(const T& x, BTNode* l, BTNode* r) {
element = x;
lChild = l;
rChild = r;
}
T element;
BTNode* lChild, *rChild;
};
template
class Queue
{
public:
virtual bool IsEmpty() const = 0; // 队列为空返回true
virtual bool IsFull() const = 0; // 队列满返回true
virtual bool Front(T &x) const = 0; // 队头元素赋给x，操作成功返回true
virtual bool EnQueue(T x) = 0; // 队尾插入元素x，操作成功返回true
virtual bool DeQueue() = 0; // 删除队头元素，操作成功返回true
virtual bool Clear() = 0; // 清除队列中所有元素
};
template
class SeqQueue:public Queue
{
public:
SeqQueue(int mSize);
~SeqQueue() { delete []q; }
bool IsEmpty() const { return front == rear; } // front与rear相等时循环队列为空
bool IsFull() const { return (rear + 1) % maxSize == front; } // front与(rear + 1) % maxSize相等时循环队列满
bool Front(T &x) const;
bool EnQueue(T x);
bool DeQueue();
bool Clear() { front = rear = 0; return true; }
/* data */
private:
int front, rear, maxSize; // 队头元素 队尾元素 数组最大长度
T *q;
};
template
SeqQueue::SeqQueue(int mSize)
{
maxSize = mSize;
q = new T[maxSize];
front = rear = 0;
}
template
bool SeqQueue::Front(T &x) const
{
if(IsEmpty()) { // 空队列处理
cout << "SeqQueue is empty" << endl;
return false;
}
x = q[(front + 1) % maxSize];
return true;
}
template
bool SeqQueue::EnQueue(T x)
{
if(IsFull()) { // 溢出处理
cout << "SeqQueue is full" << endl;
return false;
}
q[(rear = (rear + 1) % maxSize)] = x;
return true;
}
template
bool SeqQueue::DeQueue()
{
if(IsEmpty()) { // 空队列处理
cout << "SeqQueue is empty" << endl;
return false;
}
front = (front + 1) % maxSize;
return true;
}
template
class BinaryTree
{
public:
BinaryTree(): s(100){ root = NULL; }
bool IsEmpty() const; // 判断是否为空, 是返回true
void Clear(); // 移去所有结点, 成为空二叉树
bool Root(T& x) const; // 若二叉树为空, 则x为根的值, 返回true
BTNode* Root();
int Size();
int Count() { return Count(root); }
void MakeTree(const T& x, BinaryTree& left, BinaryTree& right); // 构造一颗二叉树, 根的值为x, left & right为左右子树
void BreakTree(T& x, BinaryTree& left, BinaryTree& right); // 拆分二叉树为三部分, x为根的值, left & right为左右子树
void PreOrder(void (*Visit)(T& x)); // 先序遍历二叉树
void InOrder(void (*Visit)(T& x)); // 中序遍历二叉树
void PostOrder(void (*Visit)(T& x)); // 后序遍历二叉树
int High(BTNode *p); // 返回二叉树高度
int Num(BTNode *p); // 返回二叉树叶子结点数
BTNode *Copy(BTNode *t); // 复制二叉树
void Exchange(BTNode *&t); // 交换二叉树左右子树
void Level_Traversal(void(*Visit)(T &x)); // 层次遍历二叉树
BTNode* root;
protected:
SeqQueue s;
private:
void Clear(BTNode *t);
int Size(BTNode *t); // 返回二叉树结点个数
int Count(BTNode *t); // 返回二叉树只有一个孩子的结点个数
void PreOrder(void (*Visit)(T &x), BTNode *t);
void InOrder(void (*Visit)(T &x), BTNode *t);
void PostOrder(void (*Visit)(T &x), BTNode *t);
void Level_Traversal(void(*Visit)(T &x), BTNode *t);
};
template
void Visit(T &x)
{
cout << x << '\t';
}
template
BTNode* BinaryTree::Root()
{
return root;
}
template
bool BinaryTree::Root(T &x) const
{
if(root) {
x = root -> element;
return true;
}
return false;
}
template
void BinaryTree::Clear()
{
Clear(root);
}
template
void BinaryTree::Clear(BTNode *t)
{
if(t) {
Clear(t -> lChild);
Clear(t -> rChild);
cout << "delete" << t -> element << "..." << endl;
delete t;
}
}
template
void BinaryTree::MakeTree(const T& x, BinaryTree& left, BinaryTree& right)
{
if(root || &left == &right) return;
root = new BTNode(x, left.root, right.root);
left.root = right.root = NULL;
}
template
void BinaryTree::BreakTree(T& x, BinaryTree& left, BinaryTree& right)
{
if(!root || &left == &right || left.root || right.root) return;
x = root -> element;
left.root = root -> lChild;
right.root = root -> rChild;
delete root;
root = NULL;
}
template
void BinaryTree::PreOrder(void (*Visit)(T& x))
{
PreOrder(Visit, root);
}
template
void BinaryTree::PreOrder(void (*Visit)(T& x), BTNode* t)
{
if(t) {
Visit(t -> element);
PreOrder(Visit, t -> lChild);
PreOrder(Visit, t -> rChild);
}
}
template
void BinaryTree::InOrder(void (*Visit)(T& x))
{
InOrder(Visit, root);
}
template
void BinaryTree::InOrder(void (*Visit)(T& x), BTNode* t)
{
if(t) {
InOrder(Visit, t -> lChild);
Visit(t -> element);
InOrder(Visit, t -> rChild);
}
}
template
void BinaryTree::PostOrder(void (*Visit)(T& x))
{
PostOrder(Visit, root);
}
template
void BinaryTree::PostOrder(void (*Visit)(T& x), BTNode* t)
{
if(t) {
PostOrder(Visit, t -> lChild);
PostOrder(Visit, t -> rChild);
Visit(t -> element);
}
}
template
int BinaryTree::Size()
{
return Size(root);
}
template
int BinaryTree::Size(BTNode *t)
{
if(!t) return 0;
return Size(t -> lChild) + Size(t -> rChild) + 1;
}
template
int BinaryTree::Count(BTNode *t)
{
if(!t) return 0;
if(((t -> lChild) && (!t -> rChild)) || ((!t -> lChild) && (t -> rChild))) return 1;
return Count(t -> lChild) + Count(t -> rChild);
}
template
int BinaryTree::High(BTNode *p)
{
if(p == NULL) return 0;
else if(p -> lChild == NULL && p -> rChild ==NULL) return 1;
else return(High(p -> lChild) > High(p -> rChild) ? High(p -> lChild) + 1 : High(p -> rChild) + 1);
}
template
int BinaryTree::Num(BTNode *p)
{
if(p) {
if(p -> lChild == NULL && p -> rChild == NULL) return 1;
else return Num(p -> lChild) + Num(p -> rChild);
}
else return 0;
}
template
BTNode*BinaryTree::Copy(BTNode *t)
{
if(t == NULL) return NULL;
BTNode *q = new BTNode(t -> element);
q -> lChild = Copy(t -> lChild);
q -> rChild = Copy(t -> rChild);
return q;
}
template
void BinaryTree::Exchange(BTNode *&t)
{
if(t) {
BTNode *q = t -> lChild;
t -> lChild = t -> rChild;
t -> rChild = q;
Exchange(t -> lChild);
Exchange(t -> rChild);
}
}
template
void BinaryTree::Level_Traversal(void(*Visit)(T &x), BTNode *t)
{
BTNode *a;
Visit(t -> element);
if(t -> lChild) s.EnQueue(t -> lChild);
if(t -> rChild) s.EnQueue(t -> rChild);
while(s.Front(a) == true) {
if(a -> lChild) s.EnQueue(a -> lChild);
if(a -> rChild) s.EnQueue(a -> rChild);
Visit(a -> element);
s.DeQueue();
}
}
int main(int argc, char const *argv[])
{
BinaryTree t[100], a, b, tmp;
int num = 0, high = 0;
t[7].MakeTree('H', a, b);
t[8].MakeTree('I', a, b);
t[3].MakeTree('D', t[7], t[8]);
t[4].MakeTree('E', a, b);
t[5].MakeTree('F', a, b);
t[6].MakeTree('G', a, b);
t[1].MakeTree('B', t[3], t[4]);
t[2].MakeTree('C', t[5], t[6]);
t[0].MakeTree('A', t[1], t[2]);
cout << "二叉树z的层次遍历结果:\n";
t[0].PreOrder(Visit);
cout << endl;
tmp.root = tmp.Copy(t[0].root);
cout << "tmp复制二叉树z后层次遍历结果:\n";
tmp.PreOrder(Visit);
cout << endl;
t[0].Exchange(t[0].root);
cout << "交换左右子树后二叉树z的层次遍历结果:\n";
t[0].PreOrder(Visit);
cout << endl;
num = t[0].Num(t[0].root);
cout << "二叉树z的叶子结点数为:\n" << num << endl;
high = t[0].High(t[0].root);
cout << "二叉树z的高度为:\n" << high << endl;
t[0].Clear();
return 0;
}
~~~
';