数据结构--二叉树(链式存储)C++(模板类实现)
作者:
AmbitionX
,
2022-05-07 09:30:57
,
所有人可见
,
阅读 228
#include <iostream>
using namespace std;
template <typename DataType>
struct BiNode
{
DataType data;
BiNode<DataType> * lchild, * rchild; // 左右孩子指针
};
template <typename DataType>
class BiTree
{
public:
BiTree( ){root = Creat();} //构造函数,建立一棵二叉树
~BiTree( ){Release(root);} //析构函数,释放各结点的存储空间
void PreOrder( ){PreOrder(root);} //前序遍历二叉树
void InOrder( ){InOrder(root);} //中序遍历二叉树
void PostOrder( ){PostOrder(root);} //后序遍历二叉树
void LevelOrder( ); //层序遍历二叉树
private:
BiNode<DataType> *Creat(); //构造函数调用
void Release(BiNode<DataType> *bt); //析构函数调用
void PreOrder(BiNode<DataType> *bt); //前序遍历函数调用
void InOrder(BiNode<DataType> *bt); //中序遍历函数调用
void PostOrder(BiNode<DataType> *bt); //后序遍历函数调用
BiNode<DataType> * root; //指向根结点的头指针
};
// 利用二叉树的扩展构造二叉树
template <typename DataType>
BiNode<DataType> * BiTree<DataType> :: Creat()
{
BiNode<DataType> * bt;
char ch;
cin >> ch; // 输入结点的数据信息,假设为字符
if (ch == '#') bt = nullptr; // 建设一个空树
else if (ch == '!') return bt;
else
{
bt = new BiNode<DataType>;
bt->data = ch;
bt->lchild = Creat(); // 递归建立左子树
bt->rchild = Creat(); // 递归建立右子树
}
return bt;
}
// 析构函数
template <typename DataType>
void BiTree<DataType> :: Release(BiNode<DataType> * bt)
{
if (bt == nullptr) return; // 递归调用的结束条件
else
{
Release(bt->lchild); // 释放左子树
Release(bt->rchild); // 释放右子树
delete bt; // 释放根节点
}
}
// 前序遍历二叉树
template <typename DataType>
void BiTree<DataType> :: PreOrder(BiNode<DataType> * bt)
{
if (bt == nullptr) return; // 递归调用的结束条件
else
{
cout << bt->data << "\t"; // 访问根节点bt的数据域
PreOrder(bt->lchild); // 前序遍历结点bt的左子树
PreOrder(bt->rchild); // 前序遍历结点bt的右子树
}
}
// 中序遍历二叉树
template <typename DataType>
void BiTree<DataType> :: InOrder(BiNode<DataType> * bt)
{
if (bt == nullptr) return; // 递归调用的结束条件
else
{
InOrder(bt->lchild); // 中序遍历结点bt的左子树
cout << bt->data << "\t"; // 访问根节点bt的数据域
InOrder(bt->rchild); // 中序遍历结点bt的右子树
}
}
// 后序遍历二叉树
template <typename DataType>
void BiTree<DataType> :: PostOrder(BiNode<DataType> * bt)
{
if (bt == nullptr) return; // 递归调用的结束条件
else
{
PostOrder(bt->lchild); // 后序遍历结点bt的左子树
PostOrder(bt->rchild); // 后序遍历结点bt的右子树
cout << bt->data << "\t"; // 访问根节点bt的数据域
}
}
// 层序遍历二叉树
template <typename DataType>
void BiTree<DataType> :: LevelOrder()
{
BiNode<DataType> * Q[100], *q = nullptr;
int front = -1, rear = -1; // 队列初始化
if (root == nullptr) return; // 二叉树为空
Q[++ rear] = root; // 根指针入队
while (front != rear) // 当队非空时
{
q = Q[++ front]; // 出队
cout << q->data << "\t";
if (q->lchild != nullptr) Q[++ rear] = q->lchild;
if (q->rchild != nullptr) Q[++ rear] = q->rchild;
}
}
int main()
{
// 测试输入: a b # d # # c # #
BiTree<char> T{ }; // 建立一颗树
cout << "二叉树的前序遍历是 " << endl;
T.PreOrder();
cout << endl;
cout << "二叉树的中序遍历是 " << endl;
T.InOrder();
cout << endl;
cout << "二叉树的后序遍历是 " << endl;
T.PostOrder();
cout << endl;
cout << "二叉树的层序遍历是 " << endl;
T.LevelOrder();
cout << endl;
return 0;
}