[C++] 非递归实现前中后序遍历二叉树

网上代码一搜一大片，大同小异咯。

书上的函数实现代码甚至更胜一筹，而且抄一遍就能用，唯一问题是没有写二叉树节点和树的模版类的构造实现，和没有具体实现 visit 函数（也没说明，略坑）。

只需要前中后序遍历的话很多函数都不需要，此外值得吐槽的一点是，明明 BinaryTreeNode 类里面接口写的很明确，私有成员也都保护起来了，最后却把 BinaryTree 添加为了友元类，这波操作着实令人费解。

为了添加这个友元类还需要先进行两个类的声明，之后才能逐个实现，迷了。

但这都不是我按顺序实现了接口函数，最后还是没有调用接口函数的理由。所以根本原因其实就是懒。

前置技能

四种遍历方法分别为：

层次遍历 “ 从上到下，从左到右 ”
前序遍历 “ 根结点 -> 左子树 -> 右子树 ”
中序遍历 “ 左子树 -> 根结点 -> 右子树 ”
后序遍历 “ 左子树 -> 右子树 -> 根结点 ”

层次遍历使用了队列进行实现，而前中后序遍历是利用的栈来实现。而前序遍历、中序遍历和后序遍历中，后序遍历的实现无疑是最复杂的。

需求描述

直接上头文件，需要注意的是我没有实现建树、删树和插入的函数，顺手还多抄了一个层次遍历的函数。整体来看是一个很菜的代码，只在主函数里随便构了一个二叉树测试遍历函数。

全部都是模版类的实现写起来很麻烦，实现好了很舒服23333

binarytree.h



template<class T>

class BinaryTreeNode;

template<class T>

class BinaryTree;

template<class T>

class BinaryTreeNode{

private:

	T element;                        //数据域

	BinaryTreeNode<T> * leftChild;    //左孩子

	BinaryTreeNode<T> * rightChild;   //右孩子

public:

	BinaryTreeNode();                 //默认构造

	BinaryTreeNode(T& ele);           //给定数据域值的构造

	BinaryTreeNode(T& ele, BinaryTreeNode<T> * l, BinaryTreeNode<T> * r);

	BinaryTreeNode<T> * getLeftChild();           //返回左孩子

	BinaryTreeNode<T> * getRightChild();          //返回右孩子

	bool setLeftChild(BinaryTreeNode<T> * l);     //设置左孩子

	bool setRightChild(BinaryTreeNode<T> * r);    //设置右孩子

	T getValue() const;                           //返回数据值

	bool isLeaf() const;                          //判断是否为叶子节点

	friend class BinaryTree<T>;

};

template<class T>

class BinaryTree{

private:

	BinaryTreeNode<T> * root;  //根节点

public:

	BinaryTree();              //默认构造

	BinaryTree(BinaryTreeNode<T> * r);

	~BinaryTree();             //析构

	bool isEmpty() const;      //判断是否为空树

	void visit(BinaryTreeNode<T> * pointer);

	BinaryTreeNode<T> * getRoot() const;              //返回根节点

	void preOrder(BinaryTreeNode<T> * root);          //先序遍历

	void inOrder(BinaryTreeNode<T> * root);           //中序遍历

	void postOrder(BinaryTreeNode<T> * root);         //后序遍历

	void levelOrder(BinaryTreeNode<T> * root);        //层次遍历

};

具体实现

binarytree.cpp

#include"binarytree.h"

#include<iostream>

#include<queue>

#include<stack>

template<class T>

BinaryTreeNode<T>::BinaryTreeNode(){

	element = 0;

	leftChild = nullptr;

	rightChild = nullptr;

}

template<class T>

BinaryTreeNode<T>::BinaryTreeNode(T& ele){

	element = ele;

	leftChild = nullptr;

	rightChild = nullptr;

}

template<class T>

BinaryTreeNode<T>::BinaryTreeNode(T& ele, BinaryTreeNode<T> * l,

                                  BinaryTreeNode<T> * r){

	element = ele;

	leftChild = l;

	rightChild = r;

}

template<class T>

BinaryTreeNode<T> * BinaryTreeNode<T>::getLeftChild(){

	return leftChild;

}

template<class T>

BinaryTreeNode<T> * BinaryTreeNode<T>::getRightChild(){

	return rightChild;

}

template<class T>

T BinaryTreeNode<T>::getValue() const{

	return element;

}

template<class T>

bool BinaryTreeNode<T>::setLeftChild(BinaryTreeNode<T> * l){

	if(leftChild == nullptr){

		leftChild = l;

		return true;

	}

	else return false;

}

template<class T>

bool BinaryTreeNode<T>::setRightChild(BinaryTreeNode<T> * r){

	if(rightChild == nullptr){

		rightChild = r;

		return true;

	}

	else return false;

}

template<class T>

bool BinaryTreeNode<T>::isLeaf() const{

	if(leftChild == nullptr && rightChild == nullptr)

		return true;

	else return false;

}

template<class T>

BinaryTree<T>::BinaryTree(){

	root = nullptr;

}

template<class T>

BinaryTree<T>::BinaryTree(BinaryTreeNode<T> * r){

	root = r;

}

template<class T>

BinaryTree<T>::~BinaryTree(){

	root = nullptr;

}

template<class T>

bool BinaryTree<T>::isEmpty() const{

	if (root == nullptr)	return true;

	else return false;

}

template<class T>

BinaryTreeNode<T> * BinaryTree<T>::getRoot() const{

	return root;

}

template<class T>

void BinaryTree<T>::visit(BinaryTreeNode<T> * pointer){

	std::cout<<pointer->element<<std::endl;

}

template<class T>

void BinaryTree<T>::preOrder(BinaryTreeNode<T> * root){

	using std::stack;

	stack<BinaryTreeNode<T> * > nodeStack;

	BinaryTreeNode<T> * pointer = root;

	while(!nodeStack.empty()||pointer != nullptr){

		if(pointer != nullptr){

			visit(pointer);

			if(pointer -> rightChild !=  nullptr)

				nodeStack.push(pointer->rightChild);

			pointer = pointer->leftChild;

		}

		else{

			pointer = nodeStack.top();

			nodeStack.pop();

		}

	}

}

template<class T>

void BinaryTree<T>::inOrder(BinaryTreeNode<T> * root){

	using std::stack;

	stack<BinaryTreeNode<T> * > nodeStack;

	BinaryTreeNode<T> * pointer = root;

	while(!nodeStack.empty()||pointer){

		if(pointer){

			nodeStack.push(pointer);

			pointer = pointer -> leftChild;

		}

		else{

			pointer = nodeStack.top();

			visit(pointer);

			pointer = pointer -> rightChild;

			nodeStack.pop();

		}

	}

}

template<class T>

void BinaryTree<T>::postOrder(BinaryTreeNode<T> * root){

	using std::stack;

	stack<BinaryTreeNode<T> * > nodeStack;

	BinaryTreeNode<T> * pointer = root;

	BinaryTreeNode<T> * pre = root;

	while(pointer != nullptr){

		while(pointer -> leftChild != nullptr){

			nodeStack.push(pointer);

			pointer = pointer -> leftChild;

		}

		while(pointer != nullptr && (pointer -> rightChild == nullptr ||

                                     pre == pointer->rightChild)){

			visit(pointer);

			pre = pointer;

			pointer = nodeStack.top();

			nodeStack.pop();

		}

		nodeStack.push(pointer);

		pointer = pointer -> rightChild;

	}

}

template<class T>

void BinaryTree<T>::levelOrder(BinaryTreeNode<T> * root){

	using std::queue;

	queue<BinaryTreeNode<T> *>nodeQueue;

	BinaryTreeNode<T> * pointer = root;

	if(pointer)

		nodeQueue.push(pointer);

	while(!nodeQueue.empty()){

		pointer = nodeQueue.front();

		visit(pointer);

		nodeQueue.pop();

		if(pointer->leftChild)	nodeQueue.push(pointer->leftChild);

		if(pointer->rightChild)	nodeQueue.push(pointer->rightChild);

	}

}

main.cpp

#include"binarytree.h"

#include <iostream>

using namespace std;

int main(){

	int a1,a2,a3,a4,a5;

	cin>>a1>>a2>>a3>>a4>>a5;

	BinaryTreeNode<int> n1(a1),n2(a2),n3(a3),n4(a4),n5(a5);

	BinaryTree<int> t(&n1);

	n1.setLeftChild(&n2);

	n1.setRightChild(&n3);

	n2.setLeftChild(&n4);

	n2.setRightChild(&n5);          //真·随便接的

	cout<<"层次遍历："<<endl;

	t.levelOrder(&n1);

	cout<<"前序遍历："<<endl;

	t.preOrder(&n1);

	cout<<"中序遍历："<<endl;

	t.inOrder(&n1);

	cout<<"后序遍历："<<endl;

	t.postOrder(&n1);

	return 0;

}

前置技能
需求描述
- binarytree.h
具体实现
- binarytree.cpp
- main.cpp

巴特西