二叉树遍历c++实现
文章中部分内容和思路来自《数据结构、算法与应用 c++语言描述》
接续上一篇文章《二叉树的存储与c++描述》:http://blog.****.net/superyang_/article/details/79213272
遍历策略
- 前序遍历：先访问一个节点，再访问左右子树。以图11-5 为例，访问次序依次为+*ab/cd；+++abcd；/+-a+xy*+b*ca
- 中序遍历：先访问左子树，再访问该节点，再访问右子树。以图11-5为例，访问次序依次为a*b+c/d；a+b+c+d；-a+x+y/+b*c*a
- 后序遍历：先访问左右子树，再访问该节点。以图11-5为例，访问次序依次为ab*cd/+；ab+c+d+；a-xy++b+ca**/
- 层次遍历：从上到下，从左到右，依次访问树的元素。以图11-5为例，访问次序依次为+*/abcd；++d+cab；/+*-++*axybca
代码实现
-------------
BinaryTree.h:
-------------
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <QDebug>
template <class T>
struct BinaryTreeNode
{
public:
BinaryTreeNode() {lChild = rChild = NULL;}
BinaryTreeNode(const T &value)
{
this->value = value;
lChild = rChild = NULL;
}
BinaryTreeNode(const T &value, BinaryTreeNode *lChild, BinaryTreeNode *rChild)
{
this->value = value;
this->lChild = lChild;
this->rChild = rChild;
}
public:
T value;
BinaryTreeNode *lChild;
BinaryTreeNode *rChild;
};
//template <class E>
class ExpressBinaryTree
{
public:
ExpressBinaryTree();
explicit ExpressBinaryTree(const QString &express);
public:
void preOrder(BinaryTreeNode<char> *root = NULL);
void inOrder(BinaryTreeNode<char> *root = NULL);
void postOrder(BinaryTreeNode<char> *root = NULL);
void levelOrder(BinaryTreeNode<char> *root = NULL);
BinaryTreeNode<char> *getRoot() const;
protected:
void printNodeValue(BinaryTreeNode<char> *node);
QString Middle2After(const QString &str); // 中缀表达式转换成后缀表达式
private:
BinaryTreeNode<char> *_root; // 根节点
};
#endif // BINARYTREE_H
---------------
BinaryTree.cpp:
---------------
#include "BinaryTree.h"
#include <QStack>
#include <QQueue>
#include <iostream>
using namespace std;
ExpressBinaryTree::ExpressBinaryTree()
{
_root = NULL;
}
ExpressBinaryTree::ExpressBinaryTree(const QString &express)
{
_root = NULL;
// 中缀表达式转换成后缀表达式
QString outFixexpress = Middle2After(express);
// 利用后缀表达式构造表达式树
QStack<BinaryTreeNode<char> *> stack;
char *arr = new char[outFixexpress.size() + 1];
memset(arr, 0, outFixexpress.size() + 1);
memcpy(arr, outFixexpress.toLocal8Bit().data(), outFixexpress.size());
for (int i = 0; (unsigned)i < strlen(arr); i++)
{
BinaryTreeNode<char> *newNode = new BinaryTreeNode<char>(arr[i]);
if (arr[i] == '+' || arr[i] == '-' || arr[i] == '*' || arr[i] == '/')
{
if (!stack.isEmpty())
{
newNode->rChild = stack.top();
stack.pop();
}
if (!stack.isEmpty())
{
newNode->lChild = stack.top();
stack.pop();
}
}
stack.push(newNode);
}
_root = stack.top();
}
// 前序遍历
void ExpressBinaryTree::preOrder(BinaryTreeNode<char> *root)
{
if (NULL == root)
return;
printNodeValue(root);
preOrder(root->lChild);
preOrder(root->rChild);
}
// 中序遍历
void ExpressBinaryTree::inOrder(BinaryTreeNode<char> *root)
{
if (NULL == root)
return;
inOrder(root->lChild);
printNodeValue(root);
inOrder(root->rChild);
}
// 后续便利
void ExpressBinaryTree::postOrder(BinaryTreeNode<char> *root)
{
if (NULL == root)
return;
postOrder(root->lChild);
postOrder(root->rChild);
printNodeValue(root);
}
// 层次便利
void ExpressBinaryTree::levelOrder(BinaryTreeNode<char> *root)
{
if (NULL == root)
return;
QQueue<BinaryTreeNode<char> *> queue;
while(NULL != root)
{
printNodeValue(root); // 访问节点数据
// 左右子树入队列
if (NULL != root->lChild)
{
queue.push_back(root->lChild);
}
if (NULL != root->rChild)
{
queue.push_back(root->rChild);
}
// 取队首元素为当前访问节点
if (!queue.isEmpty())
{
root = queue.front();
queue.pop_front();
}
else
{
return;
}
}
}
BinaryTreeNode<char> *ExpressBinaryTree::getRoot() const
{
return _root;
}
void ExpressBinaryTree::printNodeValue(BinaryTreeNode<char> *node)
{
cout << node->value;
}
QString ExpressBinaryTree::Middle2After(const QString &str)
{
/*
* Step1：遇到操作数直接输出[ps:以下输出皆表示输出到后缀表达式]
* Step2：栈空，遇到运算符直接入栈
* Step3：遇到左括号，直接入栈
* Step4：遇到右括号，将栈中元素依次出栈输出[ps:最后的左括号不输出]
* Step5：遇到+-*除，出栈所有栈顶优先级大于或等于该运算符的栈顶元素，运算符入栈
**/
QStack<char> st;
char stackCh;
char *arr = new char[str.size() + 1];
memset(arr, 0, str.size() + 1);
memcpy(arr, str.toLocal8Bit().data(), str.size());
char retArr[str.size() + 1];
memset(retArr, 0, str.size() + 1);
// QString ret(str.size() + 1, 0);
// char *p = ret.toLocal8Bit().data();
char *p = retArr;
for (int i = 0; (unsigned)i < strlen(arr); i++)
{
if (arr[i] == '+' || arr[i] == '-' || arr[i] == '*' || arr[i] == '/' || arr[i] == '(' || arr[i] == ')')
{
if (st.isEmpty() || arr[i] == '(') // 栈空或左括号入栈
{
st.push(arr[i]);
continue;
}
if (arr[i] == ')')
{
while(!st.isEmpty())
{
stackCh = st.top();
if (stackCh != '(')
{
memcpy(p++, &stackCh, 1);
}
st.pop();
}
continue;
}
if (arr[i] == '+' || arr[i] == '-' || arr[i] == '*' || arr[i] == '/')
{
if (arr[i] == '+' || arr[i] == '-')
{
stackCh = st.top();
while(!st.isEmpty() && stackCh != '(')
{
memcpy(p++, &stackCh, 1);
st.pop();
}
}
if (arr[i] == '*' || arr[i] == '/')
{
stackCh = st.top();
while(!st.isEmpty() && (stackCh == '*' || stackCh == '/'))
{
memcpy(p++, &stackCh, 1);
st.pop();
}
}
st.push(arr[i]);
continue;
}
}
else
{
memcpy(p++, &arr[i], 1); // 操作数直接输出
continue;
}
}
return QString::fromLocal8Bit(retArr);
}
---------
main.cpp:
---------
#include <QCoreApplication>
#include "BinaryTree.h"
#include <QDebug>
int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
QString express = "(a*b)+(c/d)";
ExpressBinaryTree bNode(express); // 构造一个表达式树
qDebug() << "前序遍历结果：";
bNode.preOrder(bNode.getRoot());
qDebug() << "\n中序遍历结果：";
bNode.inOrder(bNode.getRoot());
qDebug() << "\n后续遍历结果：";
bNode.postOrder(bNode.getRoot());
qDebug() << "\n层次遍历结果：";
bNode.levelOrder(bNode.getRoot());
return a.exec();
}