网上代码一搜一大片，大同小异咯。
书上的函数实现代码甚至更胜一筹，而且抄一遍就能用，唯一问题是没有写二叉树节点和树的模版类的构造实现，和没有具体实现 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;
}
