C++实现二叉树的存储与遍历

10年积累的成都做网站、网站设计、外贸营销网站建设经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先建设网站后付款的网站建设流程，更有马边彝族免费网站建设让你可以放心的选择与我们合作。

#pragma once
#include
#include
#include
using namespace std;
template
//定义二叉树的节点结构体
struct BinaryTreeNode
{
BinaryTreeNode * _left;
BinaryTreeNode * _right;
T _data;
//二叉树节点的构造函数,若去掉引用会构成死循环
BinaryTreeNode(T &data)
:_left(NULL)
,_right(NULL)
,_data(data)
{}
};
 
template
class BinaryTree
{
private:
typedef BinaryTreeNode Node;
Node* _root;
 
public:
//无参的构造函数
BinaryTree()
:_root(NULL)
{}
//带参的构造函数
BinaryTree( T* a,size_t size,size_t index, const T& Invalid)
{
_root=_CreateBinaryTree(a,size,index,Invalid);
}
 
//创造二叉树
Node* _CreateBinaryTree( T* a,size_t size,size_t &index,const T& Invalid)
{
Node* root=NULL;
   if(a[index]!=Invalid&&index_left=_CreateBinaryTree(a, size,++index,Invalid);
root->_right=_CreateBinaryTree(a, size,++index,Invalid);
   }
   return root;
}
//递归先序遍历二叉树
void PrevOrder( )
{
_PrevOrder(_root);
}
//
void _PrevOrder(Node* root)
{
if(root==NULL)
return;
cout<_data<<" ";
_PrevOrder(root->_left );
_PrevOrder(root->_right);
}
//非递归先序遍历
void PrevOrder_NonR()
{
 stack s;
 Node* cur=_root;
 while(cur||!s.empty())
 {
   if(cur)
   {//先将左子树遍历输出后压栈
     cout<_data <<" ";
 s.push(cur);
 cur=cur->_left;
   }
   else
   {//当左子树为空时开始访问右子树
    cur=s.top ();
s.pop();
cur=cur->_right;
   }
 }
}
 
 
//递归中序遍历二叉树
void InOrder()
{
_InOrder(_root);
}
//
void _InOrder(Node* root)
{
  if(root==NULL)
  return;
  _InOrder(root->_left );
  cout<_data <<" ";
   _InOrder(root->_right );
}
//非递归中序遍历
void InOrder_NonR()
{
  Node* cur=_root;
  stack s;
  while(cur||!s.empty())//cur非空或者栈非空
  {
if(cur)
{
  s.push(cur);//根节点进栈遍历左子书树
  cur=cur->_left;
}
else
{
  Node* top=s.top();
  cout<_data<<" ";
  s.pop();
  cur=top->_right;
}
  }
  cout<_left);
  _PostOrder(root->_right);
  cout<_data<<" ";
  }
}
 
//非递归后序遍历
void PostOrder_NonR()
{
  stack s;
  Node* cur=_root;
  Node* prev=NULL;//设置标志域
  s.push(_root);
  while(!s.empty())
  {
cur=s.top();
//
if((cur->_left ==NULL&&cur->_right ==NULL)
||(prev!=NULL&&(prev==cur->_left ||prev ==cur->_right )))
{
  cout<_data<<" ";
  prev=cur;
  s.pop();
}
 
else
{
if(cur->_right!=NULL)
  s.push(cur->_right);
    if(cur->_left!=NULL)
   s.push(cur->_left); 
}
  }
}
 

//层序遍历二叉树
void Leve1Order()
{
 queueq;
 if(_root!=NULL)
 {
 q.push(_root);
 }
while(!q.empty())
{
   Node* front=q.front();
   cout<_data <<" ";
   if(front->_left!=NULL)
q.push(front->_left);
   if(front->_right!=NULL)
q.push(front->_right);
   q.pop();
 }
 cout<_left)+_Size(root->_right);
}*/
//
size_t Size()
{
  return _Size(_root);
}
//
size_t _Size(Node* root)
{
  static size_t Ssize=0;
  if(root==NULL)
  return 0;
  ++Ssize;
  _Size(root->_left);
  _Size(root->_right);
  return Ssize;
}
 
//二叉树的深度
size_t Depth()
{
return _Depth(_root);
}
 
size_t _Depth(Node* root)
{
if(root==NULL)
return 0;
     size_t left=_Depth(root->_left )+1;
 size_t right=_Depth(root->_right)+1;
return (left>right)?left:right;
}
 
//递归求二叉树叶子节点的个数
size_t LeafSize()
{
  return _LeafSize(_root);
}
 
//
size_t _LeafSize(Node* root)
{
  if(root==NULL)
  return 0;
  if(root->_left  ==NULL&&root->_right ==NULL)
  {
    return 1;
  }
  return _LeafSize(root->_left )+_LeafSize(root->_right );
}
 
};
 
 
void test()
{
int arr[10]={1,2,3,'#','#',4,'#','#',5,6};
BinaryTreebt(arr,10,0,'#');
 
cout<<"先序递归遍历：";
bt.PrevOrder();
cout<            
            
                        

            分享文章：C++实现二叉树的存储与遍历            

            文章源于：http://cqcxhl.cn/article/jejojd.html