我们都知道现实生活中的树长什么样，那么，很明显，二叉树就是一棵“树”，不过它是一个存储数据的一种结构，根在上，向下生长，与现实生活中的相反，举个例子就比较容易理解些：比如要将1 2 3 4 5 6几个数据存到这样一个结构中，我们可以得到这样的一棵树
当然，这样的存储结构只是其中的一种。在这里，就要引出二叉树的存储和二叉树的遍历了！
树：n（n>=0）个结点的有限集合，n=0时为空树。
一、二叉树的存储结构
二叉树的存储方式有两种：
1、是以一组连续地址的空间存储的（数组），这种存储方式是针对于满二叉树或者完全二叉树来讲的
2、包装一个结点存储内容并连接起来（类似于链表），这个结点包括指针域和值域，指针域又包括两个内容（_left 和 _right,分别指向左子树与右子树），任意一种二叉树都可以利用这种存储方式
代码定义一个树的结点：
template<class T>
struct BinaryTreeNode
{
BinaryTreeNode(const T& x)
:_data(x)
,_left(NULL)
,_right(NULL)
{}
T _data; //数值域
BinaryTreeNode<T>* _left; //左子树
BinaryTreeNode<T>* _right; //右子树
};
二、二叉树的遍历
前序遍历---先遍历根节点，再遍历左子树，最后遍历右子树（根-左-右）
中序遍历---先遍历左子树，再遍历根节点，最后遍历右子树（左-根-右）
后序遍历---先遍历左子树，再遍历右子树，最后遍历根节点（左-右-根）
同样，以刚开始的1 2 3 4 5 6为例：
前序遍历结果：1 2 3 4 5 6
中序遍历结果：3 2 4 1 6 5
后序遍历结果：3 4 6 2 5 1
由于遍历二叉树的过程是一层一层往下循环的过程，因此在这里用递归方式就比较简单一些
前序：
这种遍历方式是遇到根节点先输出根节点，再递归遍历左子树，直到左子树为 NULL，就开始返回并遍历右子树
void _prevOrder(Node* root) //前---根、左、右---1 2 3 4 5 6
{
if(root == NULL)
return ;
Node* cur = root;
if(cur)
{
cout<<cur->_data<<" ";
_prevOrder(cur->_left);
_prevOrder(cur->_right);
}
}
这两种遍历方式的思想与前序遍历的方式类似，只是输出根节点的位置不同
void _inOrder(Node* root) //中---左、根、右---3 2 4 1 6 5
{
if(root == NULL)
return ;
Node* cur = root;
if (cur)
{
_inOrder(cur->_left);
cout<<cur->_data<<" ";
_inOrder(cur->_right);
}
}
void _postOrder(Node* root) //后---左、右、根---3 4 2 6 5 1
{
if (root == NULL)
return ;
Node* cur = root;
if (cur)
{
_postOrder(cur->_left);
_postOrder(cur->_right);
cout<<cur->_data<<" ";
}
}
以上就是递归实现的二叉树的三种遍历算法了，之后还会附上二叉树的非递归遍历算法！接下来是二叉树的实现代码：
//结点定义
template<class T>
struct BinaryTreeNode
{
BinaryTreeNode(const T& x)
:_data(x)
,_left(NULL)
,_right(NULL)
{}
T _data; //数值域
BinaryTreeNode<T>* _left; //左子树
BinaryTreeNode<T>* _right; //右子树
};
//二叉树实现
template<class T>
class BinaryTree
{
typedef BinaryTreeNode<T> Node;
public:
BinaryTree()
:_root(NULL)
{}
BinaryTree(T* a,size_t size,const T& invalid)
{
size_t index = 0;
_root = _CreatTree(a,size,index,invalid);<span style="white-space:pre"> </span>//构造树
}
BinaryTree(const BinaryTree<T>& t)<span style="white-space:pre"> </span>//拷贝构造
{
_root = _Copy(t._root);
}
BinaryTree<T>& operator=(const BinaryTree<T>& t)
{
if (this != &t)
{
BinaryTree<T> tmp(t); //拷贝构造
std::swap(_root,tmp._root);
}
}
~BinaryTree()
{
_Destory(_root);
}
void PrevOrder() //前序
{
if (_root)
_prevOrder(_root);
cout<<endl;
}
void InOrder() //中序
{
if (_root)
_inOrder(_root);
cout<<endl;
}
void PostOrder() //后序
{
if(_root)
_postOrder(_root);
cout<<endl;
}
protected:
Node* _CreatTree(T* a,size_t size,size_t& index,const T& invalid)
{
assert(a);
Node* root = NULL;
while((index<size) && a[index]!=invalid)
{
root = new Node(a[index]); //构造根节点
root->_left = _CreatTree(a,size,++index,invalid); //左子树
root->_right = _CreatTree(a,size,++index,invalid); //右子树
}
return root;
}
Node* _Copy(Node* root)
{
if (root == NULL)
{
return NULL;
}
Node* newroot = NULL;
if (root)
{
newroot = new Node(root->_data);
newroot->_left = _Copy(root->_left);
newroot->_right = _Copy(root->_right);
}
return newroot;
}
void _Destory(Node* root)
{
Node* cur = root;
if (cur != NULL)
{
_Destory(cur->_left);
_Destory(cur->_right);
delete cur;
cur = NULL;
}
}
void _prevOrder(Node* root) //前---根、左、右---1 2 3 4 5 6
{
if(root == NULL)
return ;
Node* cur = root;
if(cur)
{
cout<<cur->_data<<" ";
_prevOrder(cur->_left);
_prevOrder(cur->_right);
}
}
void _inOrder(Node* root) //中---左、根、右---3 2 4 1 6 5
{
if(root == NULL)
return ;
Node* cur = root;
if (cur)
{
_inOrder(cur->_left);
cout<<cur->_data<<" ";
_inOrder(cur->_right);
}
}
void _postOrder(Node* root) //后---左、右、根---3 4 2 6 5 1
{
if (root == NULL)
return ;
Node* cur = root;
if (cur)
{
_postOrder(cur->_left);
_postOrder(cur->_right);
cout<<cur->_data<<" ";
}
}
protected:
Node* _root;<span style="white-space:pre"> </span>//定义一个根结点
};
void TestBinaryTree()
{
int a1[10] = {1,2,3,'#','#',4,'#','#',5,6};
int a2[15] = {1,2,'#',3,'#','#',4,5,'#',6,'#',7,'#','#',8};
BinaryTree<int> t1(a1,10,'#');
BinaryTree<int> T1(a2,15,'#');
//BinaryTree<int> t2(t1);
//BinaryTree<int> t3 = t1;
t1.PrevOrder(); //1 2 3 4 5 6
t1.InOrder(); //3 2 4 1 6 5
t1.PostOrder(); //3 4 6 2 5 1
}