包含的二叉树运算: 删除一个二叉树, 求一颗二叉树的高度, 求一颗二叉树中叶子结点数, 复制一颗二叉树, 交换一颗二叉树的左右子树,
自上到下, 自左到右层次遍历一颗二叉树.
增加相关功能完善即可, 层次遍历利用队列作为辅助的数据结构, 元素类型是指向二叉树中结点的指针类型.
实现代码:
~~~
#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 <class T>
struct BTNode
{
/* data */
BTNode() { lChild = rChild = NULL; }
BTNode(const T& x) {
element = x;
lChild = rChild = NULL;
}
BTNode(const T& x, BTNode<T>* l, BTNode<T>* r) {
element = x;
lChild = l;
rChild = r;
}
T element;
BTNode<T>* lChild, *rChild;
};
template <class T>
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 T>
class SeqQueue:public Queue<T>
{
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 <class T>
SeqQueue<T>::SeqQueue(int mSize)
{
maxSize = mSize;
q = new T[maxSize];
front = rear = 0;
}
template <class T>
bool SeqQueue<T>::Front(T &x) const
{
if(IsEmpty()) { // 空队列处理
cout << "SeqQueue is empty" << endl;
return false;
}
x = q[(front + 1) % maxSize];
return true;
}
template <class T>
bool SeqQueue<T>::EnQueue(T x)
{
if(IsFull()) { // 溢出处理
cout << "SeqQueue is full" << endl;
return false;
}
q[(rear = (rear + 1) % maxSize)] = x;
return true;
}
template <class T>
bool SeqQueue<T>::DeQueue()
{
if(IsEmpty()) { // 空队列处理
cout << "SeqQueue is empty" << endl;
return false;
}
front = (front + 1) % maxSize;
return true;
}
template <class T>
class BinaryTree
{
public:
BinaryTree(): s(100){ root = NULL; }
bool IsEmpty() const; // 判断是否为空, 是返回true
void Clear(); // 移去所有结点, 成为空二叉树
bool Root(T& x) const; // 若二叉树为空, 则x为根的值, 返回true
BTNode<T>* Root();
int Size();
int Count() { return Count(root); }
void MakeTree(const T& x, BinaryTree<T>& left, BinaryTree<T>& right); // 构造一颗二叉树, 根的值为x, left & right为左右子树
void BreakTree(T& x, BinaryTree<T>& left, BinaryTree<T>& 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<T> *p); // 返回二叉树高度
int Num(BTNode<T> *p); // 返回二叉树叶子结点数
BTNode<T> *Copy(BTNode<T> *t); // 复制二叉树
void Exchange(BTNode<T> *&t); // 交换二叉树左右子树
void Level_Traversal(void(*Visit)(T &x)); // 层次遍历二叉树
BTNode<T>* root;
protected:
SeqQueue<T> s;
private:
void Clear(BTNode<T> *t);
int Size(BTNode<T> *t); // 返回二叉树结点个数
int Count(BTNode<T> *t); // 返回二叉树只有一个孩子的结点个数
void PreOrder(void (*Visit)(T &x), BTNode<T> *t);
void InOrder(void (*Visit)(T &x), BTNode<T> *t);
void PostOrder(void (*Visit)(T &x), BTNode<T> *t);
void Level_Traversal(void(*Visit)(T &x), BTNode<T> *t);
};
template <class T>
void Visit(T &x)
{
cout << x << '\t';
}
template <class T>
BTNode<T>* BinaryTree<T>::Root()
{
return root;
}
template <class T>
bool BinaryTree<T>::Root(T &x) const
{
if(root) {
x = root -> element;
return true;
}
return false;
}
template <class T>
void BinaryTree<T>::Clear()
{
Clear(root);
}
template <class T>
void BinaryTree<T>::Clear(BTNode<T> *t)
{
if(t) {
Clear(t -> lChild);
Clear(t -> rChild);
cout << "delete" << t -> element << "..." << endl;
delete t;
}
}
template <class T>
void BinaryTree<T>::MakeTree(const T& x, BinaryTree<T>& left, BinaryTree<T>& right)
{
if(root || &left == &right) return;
root = new BTNode<T>(x, left.root, right.root);
left.root = right.root = NULL;
}
template <class T>
void BinaryTree<T>::BreakTree(T& x, BinaryTree<T>& left, BinaryTree<T>& 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 <class T>
void BinaryTree<T>::PreOrder(void (*Visit)(T& x))
{
PreOrder(Visit, root);
}
template <class T>
void BinaryTree<T>::PreOrder(void (*Visit)(T& x), BTNode<T>* t)
{
if(t) {
Visit(t -> element);
PreOrder(Visit, t -> lChild);
PreOrder(Visit, t -> rChild);
}
}
template <class T>
void BinaryTree<T>::InOrder(void (*Visit)(T& x))
{
InOrder(Visit, root);
}
template <class T>
void BinaryTree<T>::InOrder(void (*Visit)(T& x), BTNode<T>* t)
{
if(t) {
InOrder(Visit, t -> lChild);
Visit(t -> element);
InOrder(Visit, t -> rChild);
}
}
template <class T>
void BinaryTree<T>::PostOrder(void (*Visit)(T& x))
{
PostOrder(Visit, root);
}
template <class T>
void BinaryTree<T>::PostOrder(void (*Visit)(T& x), BTNode<T>* t)
{
if(t) {
PostOrder(Visit, t -> lChild);
PostOrder(Visit, t -> rChild);
Visit(t -> element);
}
}
template <class T>
int BinaryTree<T>::Size()
{
return Size(root);
}
template <class T>
int BinaryTree<T>::Size(BTNode<T> *t)
{
if(!t) return 0;
return Size(t -> lChild) + Size(t -> rChild) + 1;
}
template <class T>
int BinaryTree<T>::Count(BTNode<T> *t)
{
if(!t) return 0;
if(((t -> lChild) && (!t -> rChild)) || ((!t -> lChild) && (t -> rChild))) return 1;
return Count(t -> lChild) + Count(t -> rChild);
}
template <class T>
int BinaryTree<T>::High(BTNode<T> *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 <class T>
int BinaryTree<T>::Num(BTNode<T> *p)
{
if(p) {
if(p -> lChild == NULL && p -> rChild == NULL) return 1;
else return Num(p -> lChild) + Num(p -> rChild);
}
else return 0;
}
template <class T>
BTNode<T>*BinaryTree<T>::Copy(BTNode<T> *t)
{
if(t == NULL) return NULL;
BTNode<T> *q = new BTNode<T>(t -> element);
q -> lChild = Copy(t -> lChild);
q -> rChild = Copy(t -> rChild);
return q;
}
template <class T>
void BinaryTree<T>::Exchange(BTNode<T> *&t)
{
if(t) {
BTNode<T> *q = t -> lChild;
t -> lChild = t -> rChild;
t -> rChild = q;
Exchange(t -> lChild);
Exchange(t -> rChild);
}
}
template <class T>
void BinaryTree<T>::Level_Traversal(void(*Visit)(T &x), BTNode<T> *t)
{
BTNode<T> *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<char> 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;
}
~~~
- 前言
- 线性表的顺序表示：顺序表ADT_SeqList
- 结点类和单链表ADT_SingleList
- 带表头结点的单链表ADT_HeaderList
- 堆栈的顺序表示ADT_SeqStack
- 循环队列ADT_SeqQueue
- 一维数组ADT_Array1D
- 稀疏矩阵ADT_SeqTriple
- 数据结构实验1(顺序表逆置以及删除)
- 数据结构实验1(一元多项式的相加和相乘)
- 二叉树ADT_BinaryTree
- 优先队列ADT_PrioQueue
- 堆ADT_Heap
- 数据结构实验2(设计哈弗曼编码和译码系统)
- ListSet_无序表搜索
- ListSet_有序表搜索
- ListSet_对半搜索的递归算法
- ListSet_对半搜索的迭代算法
- 二叉搜索树ADT_BSTree
- 散列表ADT_HashTable
- 图的邻接矩阵实现_MGraph
- 图的邻接表实现_LGraph
- 数据结构实验2(二叉链表实现二叉树的基本运算)
- 数据结构实验3(图的DFS和BFS实现)
- 数据结构实验3(飞机最少环城次数问题)
- 拓扑排序的实现_TopoSort
- 数据结构实验4(排序算法的实现及性能分析)