#include <iostream>
using namespace std;
///////////////////////////////////////////////////////////////////////
//stack
template <class T>
class Stack{
public:
Stack(int size = 50);
~Stack();
void push(T* data);
T* pop();
bool isEmpty();
T* peek();
private:
int size;
int top;
bool isFull();
T **data;
};
template <class T>
Stack<T>::Stack(int size){
if(size <= 0){
cout << "分配的内存太小了" << endl;
}
data = new T*[size];
top = -1;
this->size = size;
}
template <class T>
Stack<T>::~Stack(){
delete []data;
}
template <class T>
void Stack<T>::push(T* data){
++top;
if(isFull()){
cout << "貌似栈满了耶" << endl;
exit(1);
}
this->data[top] = data;
}
template <class T>
T* Stack<T>::pop(){
if(isEmpty()){
cout << "栈为空,不可以再出元素了!" << endl;
exit(1);
}
return data[top--];
}
template <class T>
T* Stack<T>::peek(){
if(isEmpty()){
cout << "栈为空" << endl;
exit(1);
}
return data[top];
}
template <class T>
bool Stack<T>::isFull(){
if(top == size){
return true;
}
return false;
}
template <class T>
bool Stack<T>::isEmpty(){
if(top < 0){
return true;
}
return false;
}
///////////////////////////////////////////////////////////////////////
//tree
template <class T>
class BTree{
public:
BTree *left;
BTree *right;
T data;
BTree() : left(NULL), right(NULL), data(NULL){};
~BTree(){};
};
///////////////////////////////////////////////////////////////////////
template <class T>
void PreOrder(BTree<T> *root){
if(root != NULL){
Stack<BTree<T> > stack ;
BTree<T> *ptr = root;
BTree<T> *temp;
stack.push(ptr);
while(!stack.isEmpty()) {
temp = stack.pop();
cout << temp->data << " ";
if(temp->right != NULL){
stack.push(temp->right);
}
if(temp->left != NULL){
stack.push(temp->left);
}
}
cout << endl;
}
}
///////////////////////////////////////////////////////////////////////
template <class T>
void InOrder(BTree<T> *root){
if(root != NULL){
Stack<BTree<T> > stack ;
BTree<T> *ptr = root;
while(!stack.isEmpty() || ptr != NULL){
while(ptr != NULL){
stack.push(ptr);
ptr = ptr->left;
}
if(!stack.isEmpty()){
ptr = stack.pop();
cout << ptr->data << " ";
ptr = ptr->right;
}
}
cout << endl;
}
}
///////////////////////////////////////////////////////////////////////
template <class T>
void PostOrder(BTree<T> *root){
if(root != NULL){
Stack<BTree<T> > stack;
BTree<T> *ptr = root;
BTree<T> *temp;
bool flags;
do{
while(ptr != NULL){
stack.push(ptr);
ptr = ptr->left;
}
temp = NULL;
flags = true;
while(flags && !stack.isEmpty()){
ptr = stack.peek();
if(ptr->right == temp){
cout << ptr->data << " ";
stack.pop();
temp = ptr;
}else{
ptr = ptr->right;
flags = false;
}
}
}while(!stack.isEmpty());
cout << endl;
}
}
///////////////////////////////////////////////////////////////////////
template <class T>
void PreOrder1(BTree<T> * root){
if(root != NULL){
cout << root->data << " ";
PreOrder1(root->left);
PreOrder1(root->right);
}
}
///////////////////////////////////////////////////////////////////////
template <class T>
void InOrder1(BTree<T> * root){
if(root != NULL){
InOrder1(root->left);
cout << root->data << " ";
InOrder1(root->right);
}
}
///////////////////////////////////////////////////////////////////////
template <class T>
void PostOrder1(BTree<T> * root){
if(root != NULL){
PostOrder1(root->left);
PostOrder1(root->right);
cout << root->data << " ";
}
}
///////////////////////////////////////////////////////////////////////
int main(){
BTree<int> *root = new BTree<int>;
BTree<int> *A, *B, *C, *D, *E;
A = new BTree<int>;
B = new BTree<int>;
C = new BTree<int>;
D = new BTree<int>;
E = new BTree<int>;
A->data = 5;
B->data = 6;
C->data = 4;
D->data = 2;
E->data = 7;
root = A;
A->left = B;
A->right = E;
B->left = C;
B->right = D;
/*C->left = NULL;
C->right = NULL;
D->left = NULL;
D->right = NULL;
E->left = NULL;
E->right = NULL;*/
cout << "非递归: " << endl;
PreOrder(root);
InOrder(root);
PostOrder(root);
cout << "递归: " << endl;
PreOrder1(root);
cout << endl;
InOrder1(root);
cout << endl;
PostOrder1(root);
cout << endl;
return 0;
}
分享到:
相关推荐
二叉树的非递归前序,中序,后序遍历C++模板类实现,供大家参考。
用模板类 构造二叉树,并进行中序非递归遍历。
使用C++模板、类的技术实现了二叉树的中序遍历,在BC3.1已经测试成功
前序中序后序的递归遍历,游标类的非递归遍历,复制树,求深度,重载==,,!,交换子树,层次遍历都用模板实现了,栈和队列用的是以前自己写的模板 程序的输入是数组,通过二叉树的数组表示创建的链表表示的二叉树,输出没有做...
用c++的模板类来实现二叉树,其中包含前序遍历,中序遍历,后序遍历,以及层次遍历。用了递归和非递归2中方法
用c++代码实现数据结构中,二叉树的前序遍历,中序遍历,后序遍历的算法 为大家提供学习与参考
二叉树前序、中序、后序遍历的递归实现和非递归实现及层次遍历8. 二叉树的复制9. 二叉树的输出等其它操作可根据具体需要自行补充。三、实验要求1.独立完成实验内容2.自行实现二叉树的存储结构与相关操作,不得使用...
深度优先遍历的实现; 广度优先遍历的实现;
以及前序遍历、中序遍历、后序遍历、层序遍历等。运用了C++的模板template ,以泛型编程的原则写的,泛型编程指编写完全一般化并可重复使用的算法,其效率与针对某特定的数据类型而设计的算法相同。所谓泛型,是指...
二叉树模版:包括先序中序构造,后序中序构造,结点的度,统计度为n的结点个数,高度,宽度,结点的最大值,交换每个结点的左右,删除叶结点,是否完全二叉树,广度优先遍历,先序遍历,中序遍历,后序遍历;...
C++实现类模板 包括二叉树、搜索二叉树、AVL树及它们的各种算法实现(包括建立、输出、前序遍历、中序遍历、后序遍历、插入、删除、搜索、重构、求树高、统计叶子总数等等)
C++实现类模板,压缩包内为工程文件,其中的前序、中序、后序采用非递归遍历。
基于二叉链表的二叉树,实现了二叉树的多种操作:添加、删除、拷贝、清空、树深度计算、父节点、兄弟节点获取、先中后序递归及非遍历、按层次遍历、中序迭代器(非递归算法)、节点查找、先序和中序序列重建二叉树、...
二叉搜索树的实现算法、插入算法、搜索算法、前序遍历、中序遍历、后序遍历,以及判断一课二叉树是否为二叉搜索树的算法。其中删除算法采用“用右子树上具有最小关键码的结点顶替被删结点”和“用左子树上具有最大...
二叉树实现(C++)包括三种遍历方式,分别用递归和非递归方式实现。二叉树的生成有头插入和尾插入实现,可添加、删除结点
二叉树的简历模板,C++模板,后序遍历的模板类
AVL平衡二叉树的C++实现(模板),实现了插入、查找、删除,前序、后序、中序遍历等
线索二叉树的一些基本功能 遍历 二叉树线索化 等等
内容: 1、计算二叉树叶子节点的个数。 2、交换二叉树所有节点的左、右孩子节点。 3、根据二叉树的前序遍历和中序遍历的结果,构造二叉树。
自动显示先序遍历、中序遍历、后序遍历以及层次遍历。使用画笔,清空描绘的二叉树。 使用MFC编写程序,软件为Visual Studio 2019,进行可视化绘制使用MFC中的CDC类封装的GDI和DC,GDI函数就成了CDC的方法,然后使用...