二叉树遍历算法集合(前中后序遍历的递归和非递归算法,层序遍历算法)
费了两天时间写的,包括前中后序遍历的递归和非递归算法,还有层序遍历总共2*3 + 1 = 7中遍历二叉树的算法,感觉其中后序遍历的非递归算法比较困难,想了很久最后的实现还是不够优雅,请大家指正~~
总共三个文件,一个头文件,一个对应的cpp文件,还有一个用于测试的文件.
头文件:
/**//********************************************************************
created: 2006/07/04
filename: BinaryTree.h
author: 李创
http://www.cppblog.com/converse/
purpose: 演示二叉树的算法
*********************************************************************/
#ifndef BinaryTree_H
#define BinaryTree_H
#include <stdlib.h>
#include <stack>
class BinaryTree
{
private:
typedef int Item;
typedef struct TreeNode
{
Item Node;
TreeNode* pRight;
TreeNode* pLeft;
TreeNode(Item node = 0, TreeNode* pright = NULL, TreeNode* pleft = NULL)
: Node(node)
, pRight(pright)
, pLeft(pleft)
{
}
}TreeNode, *PTreeNode;