前序中序、中序后序构建二叉树，二叉树遍历（广度优先，前序中序后序递归非递归遍历）C++实现
运用C++实现二叉树遍历、确定二叉树等重点知识
- 前序中序串、中序后序串建立二叉树（前序后序无法确定一颗树）
- 二叉树遍历
- 深度优先遍历
- 递归：前序、中序、后序
- 非递归（较难）: 前序、中序、后序
- 广度优先遍历：从最高层（或最底层）开始，向下（向上）逐层访问每一个节点，每一层自左向右访问。
以下是代码实现（附加注释讲解）：
#编译环境：用的codeblocks，可以跑出来
- 深度优先遍历
#include <iostream>
#include <string>
//#include <stack>
#include <queue>
using namespace std;
//建立一个自制的栈，也可以用库中的stack栈
template<class T>
class node {
public:
T data;
node<T>* next;
node(T a) :data(a) { next = NULL; }
};
template<class T>
class Stack {
node<T>* tail;
public:
Stack() { tail = NULL; }
void pop() {
if (isempty())
cout << "is empty." << endl;
else {
node<T>* tem = tail;
tail = tail->next;
delete tem;
}
}
bool isempty() { return tail == NULL; }
T returntail() {
if (isempty()) {
cout << "is empty." << endl;
}
else {
return tail->data;
}
}
void push(T a) {
node<T>* tem = new node<T>(a);
if (isempty())
tail = tem;
else {
tem->next = tail;
tail = tem;
}
}
};
//建立二叉树数据结点
template <class T>
class BinaryTreeNode {
private:
T data;
int count;
BinaryTreeNode<T> * lchild;
BinaryTreeNode<T> * rchild;
public:
BinaryTreeNode(T data) {
lchild = NULL;
rchild = NULL;
this->data = data;
}
BinaryTreeNode(const T &data, BinaryTreeNode<T> * l, BinaryTreeNode<T> *r) {
data = this->data; l = this->lchild; r = this->rchild;
}
BinaryTreeNode<T> * &getLchild() { return lchild; }
BinaryTreeNode<T> * &getRchild() { return rchild; }
void setLchild(BinaryTreeNode<T> *l) { l = this->lchild; }
void setRchild(BinaryTreeNode<T> *r) { r = this->rchild; }
T getData() const { return data; }
void visit() { cout << this->getData() << endl; }
void setData(const T&d) { d = this->data; }
bool isLeaf() const {
if (this->lchild == NULL && this->rchild == NULL) {
return true;
}
else {
return false;
}
}
};
//建立二叉树
template <class T>
class BinaryTree {
private:
BinaryTreeNode<T> *root;
Stack<BinaryTreeNode<T> *>nodeStack;
queue<BinaryTreeNode<T> *>nodeQueue;
public:
BinaryTree<T>() {//默认构造了一颗简单的二叉树
root = new BinaryTreeNode<T>('a');
root->getLchild() = new BinaryTreeNode<T>('b');
root->getRchild() = new BinaryTreeNode<T>('c');
root->getLchild()->getLchild() = new BinaryTreeNode<T>('d');
root->getLchild()->getRchild() = new BinaryTreeNode<T>('e');
root->getRchild()->getLchild() = new BinaryTreeNode<T>('f');
}
BinaryTree<T>(BinaryTreeNode<T> *node):root(node){}
~BinaryTree<T>() {}
bool isEmpty() const {
if (this->root == NULL) {
return true;
}
else {
return false;
}
}
BinaryTreeNode<T> *getRoot() { return this->root; }
//前序递归遍历
void preOrder(BinaryTreeNode<T> *root) {
if (root != NULL) {
root->visit();
preOrder(root->getLchild());
preOrder(root->getRchild());
}
}
//中序递归遍历
void inOrder(BinaryTreeNode<T> *root) {
if (root != NULL) {
inOrder(root->getLchild());
root->visit();
inOrder(root->getRchild());
}
}
//后序递归遍历
void nextOrder(BinaryTreeNode<T> *root){
if(root!=NULL){
nextOrder(root->getLchild());
nextOrder(root->getRchild());
root->visit();
}
}
//前序非递归遍历
void preOrderWithoutRe(BinaryTreeNode<T> *root) {
BinaryTreeNode<T> *p = root;//保存根节点
while (!nodeStack.isempty() || p) {
if (p != NULL) {
p->visit();
if (p->getRchild() != NULL) {
nodeStack.push(p->getRchild());//当前节点的右子树根节点入栈
}
p = p->getLchild();//转向访问左子树
}
else {//左子树访问完毕，访问右子树
p = nodeStack.returntail();
nodeStack.pop();
}
}
}
//中序非递归遍历
void inOrderWithoutRe(BinaryTreeNode<T> *root) {
BinaryTreeNode<T>*p = root;
while (!nodeStack.isempty() || p) {
if (p != NULL) {
nodeStack.push(p);
p = p->getLchild();
}
else {
p = nodeStack.returntail();
p->visit();
p = p->getRchild();
nodeStack.pop();
}
}
}
//后序非递归遍历
void nextOrderWithoutRe(BinaryTreeNode<T> *root){
BinaryTreeNode<T> p = root;
//每次访问根节点，都需要判断左右孩子是否存在，需要访问两次根节点，用count记录访问次数
while(!nodeStack.isempty()||p){
while(p != NULL){
p.count=1;
nodeStack.push(p);
p = p->getLchild();
}
if(!nodeStack.isempty()){
p=nodeStack.returntail();
if(p.count==1){
p.count=2;
p=p.getRchild();
}
}else{
if(p.count==2){
p.visit();
nodeStack.pop(p);
}
}
}
}
//广度优先遍历
void FromToptoButtom(BinaryTreeNode<T> *node){
BinaryTreeNode<T> *p=node;
if(p==NULL){
return;
}
nodeQueue.push(p);
while(!nodeQueue.empty()){
p=nodeQueue.front();
p->visit();
nodeQueue.pop();
if(p->getLchild()!=NULL){
nodeQueue.push(p->getLchild());
}
if(p->getRchild()!=NULL){
nodeQueue.push(p->getRchild());
}
}
}
};
//前序中序确定二叉树
int FindRoot1(char* b, int n, char v)
{
int pos = -1;
for (int i = 0; i < n; i++)
{
if (b[i] == v)
{
pos = i;
break;
}
}
return pos;
}
template<class T>
BinaryTreeNode<T> * BuildTree1(T *a, T *b, int len) {
BinaryTreeNode<T> *root = NULL;
if (len > 0) {
root = new BinaryTreeNode<T>(a[0]);
int pos = FindRoot1(b, len, a[0]);
if (pos == -1)
exit(1);//异常退出
root->getLchild() = BuildTree1(a + 1, b, pos);//递归建立左子树
root->getRchild() = BuildTree1(a + pos + 1, b + 1 + pos, len - pos - 1);//递归建立右子树
}
return root;
}
//中序后序确定二叉树
int FindRoot2(char* b, int n, char v){
int pos = -1;
for (int i = n-1 ; i >= 0 ; i--)
{
if (b[i] == v)
{
pos = i;
break;
}
}
return pos;
}
template<class T>
BinaryTreeNode<T> *BuildTree2(T *c, T *b ,int len){
BinaryTreeNode<T> *root = NULL;
if(len>0){
root = new BinaryTreeNode<T>(c[len-1]);
int pos = FindRoot2(b,len,c[len-1]);
if(pos == -1)
exit(1);
root->getLchild()=BuildTree2(c,b,pos);
root->getRchild()=BuildTree2(c+pos,b+pos+1,len-pos-1);
}
return root;
}
int main() {
char a[10] = {'A','B','D','G','C','E','F'};
char b[10] = {'D','G','B','A','E','C','F'};
char c[10] = {'G','D','B','E','F','C','A'};
BinaryTree<char> tree1(BuildTree1(a, b, 10));
cout<<"前序中序构建二叉树"<<endl;
preOrder(tree1.getRoot());
cout<<"中序后序构建二叉树"<<endl;
BinaryTree<char> tree3(BuildTree2(c,b,7));
tree3.preOrder(tree3.getRoot());
BinaryTree<char> tree2;
cout<<"广度优先遍历"<<endl;
tree2.FromToptoButtom(tree2.getRoot());
cout<<"前序递归遍历"<<endl;
tree2.preOrder(tree2.getRoot());
cout<<"中序递归遍历"<<endl;
tree2.inOrder(tree2.getRoot());
cout<<"后序递归遍历"<<endl;
tree2.nextOrder(tree2.getRoot());
cout<<"前序非递归遍历"<<endl;
tree2.preOrderWithoutRe(tree2.getRoot());
cout<<"中序非递归遍历"<<endl;
tree2.inOrderWithoutRe(tree2.getRoot());
cout<<"后序非递归遍历"<<endl;
tree2.nextOrder(tree2.getRoot());
}
在csdn上发的第一篇原创文章！纪念一下！
后续会继续更新数据结构、安卓、大数据等相关内容（包括但不限于此）