二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^（i - 1）个结点；深度为k的二叉树至多有2^k - 1个结点。由于树的定义是递归实现的，所以在进行二叉树的前序、中序和后序遍历可通过递归实现，但也可通过非递归的栈来实现，二叉树的层次遍历可通过队列实现。
目前创新互联已为上千多家的企业提供了网站建设、域名、
虚拟主机、
成都网站托管、企业网站设计、
白沙黎族网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。
下面我对二叉树及前序、中序、后序遍历二叉树等方法进行实现
例如二叉树:
测试用例：
int arrary[10] = {1,2,3,'$','$',4,'$','$',5,6};
arrary为上图所示二叉树，通过前序存储的，'$'表示非法值，即没有结点
二叉树的结构：
template
struct BinaryTreeNode
{
BinaryTreeNode* _left;
BinaryTreeNode* _right;
T _data;
BinaryTreeNode();
BinaryTreeNode(const T& x);
};
template
class BinaryTree
{
typedef BinaryTreeNode Node;
public:
BinaryTree();
BinaryTree(const T* a, size_t size, const T& invalid);
BinaryTree(const BinaryTree& t);
BinaryTree& operator=(BinaryTree t);
~BinaryTree();
void PrevOrder();//前序遍历-递归
void InOrder();//中序遍历-递归
void PostOrder();//后序遍历-递归
void PrevOrder_NonR();//前序遍历-非递归
void InOrder_NonR();//中序遍历-非递归
void PostOrder_NonR();//后序遍历-非递归
void LevelOrder();//层次遍历
size_t Size();//结点个数
size_t Depth();//树的深度
size_t LeafSize();//叶子结点个数
size_t GetkLevel();//第k层结点个数
protected:
Node* _CreateTree(const T* a, size_t size, size_t& index, const T& invalid);//树的建立
Node* _CopyTree(Node* t);//复制树
void _Distory(Node* root);//清空结点，先释放子树，再释放根结点
void _PrevOrder(Node* root);//前序遍历
void _InOrder(Node* root);//中序遍历
void _PostOrder(Node* root);//后序遍历
size_t _Size(Node* root);//结点个数
size_t _Depth(Node* root);//树的深度
//size_t _LeafSize(Node* root);//叶子结点个数
size_t _LeafSize(Node* root,size_t& size);//叶子结点个数
//size_t _GetkLevel(int k, Node* root);//第k层结点个数
size_t _GetkLevel(int k, Node* root, int& size, int level);//第k层结点个数
private:
Node* _root;// BinaryTreeNode* _root;
};
二叉树的构造、拷贝构造、赋值运算和析构的实现，由于二叉树存在左子树和右子树，故用递归实现其功能，具体实现如下：
template
BinaryTreeNode::BinaryTreeNode()
:_left(NULL)
, _right(NULL)
, _data(0)
{}
template
BinaryTreeNode::BinaryTreeNode(const T& x)
: _left(NULL)
, _right(NULL)
, _data(x)
{}
template
BinaryTree::BinaryTree()
:_root(NULL)
{}
template
BinaryTree::~BinaryTree()
{
_Distory(_root);
}
template
void BinaryTree::_Distory(Node* root)//清空结点，先释放子树，再释放根结点
{
if (root == NULL)
{
return;
}
if (root->_left)//递归释放子结点
{
_Distory(root->_left);
}
if (root->_right)
{
_Distory(root->_right);
}
delete root;
root = NULL;
}
template
BinaryTree::BinaryTree(const T* a, size_t size, const T& invalid)
{
size_t index = 0;//标记数组下标
_root = _CreateTree(a, size, index, invalid);
}
template
BinaryTreeNode* BinaryTree::_CreateTree(const T* a, size_t size, size_t& index, const T& invalid)//树的建立
{
Node* root = NULL;
if (index < size && a[index] != invalid)//indx_left = _CreateTree(a, size, ++index, invalid);//左子树递归
root->_right = _CreateTree(a, size, ++index, invalid);//右子树递归
}
return root;
}
template
BinaryTree::BinaryTree(const BinaryTree& t)
{
_root = _CopyTree(t._root);
}
template
BinaryTreeNode* BinaryTree::_CopyTree(Node* t)//此处的返回类型不能用Node表示
{
Node* root = NULL;
if (t != NULL)
{
root = new Node(t->_data);
root->_left = _CopyTree(t->_left);
root->_right = _CopyTree(t->_right);
}
return root;
}
template
BinaryTree& BinaryTree::operator=(BinaryTree t)//现代写法
{
if (this != &t)
{
BinaryTree tmp = t;
swap(_root, tmp._root);
}
return *this;
}
前序遍历(先根遍历)：(1)先访问根节点；(2)前序访问左子树；(3)前序访问右子树.【1 2 3 4 5 6】
下面分别用递归和非递归两种方法实现。
二叉树的递归实现前序遍历
//递归实现
template
void BinaryTree::PrevOrder()//前序遍历(先根结点)
{
_PrevOrder(_root);
}
template
void BinaryTree::_PrevOrder(Node* root)
{
if (root == NULL)
{
return;
}
cout << root->_data << " ";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}
二叉树的非递归实现前序序列，利用栈实现。
由于栈是后进先出，对于二叉树的前序遍历先访问左子树后访问右子树，故右结点比左结点先进栈
//非递归实现（利用栈实现）
template
void BinaryTree::PrevOrder_NonR()//前序遍历-非递归
{
stack s;
if (_root)
{
s.push(_root);
}
while (!s.empty())
{
Node* top = s.top();//访问栈顶元素
cout << top->_data << " ";
s.pop();
//右结点比左结点先进栈
if (top->_right)
{
s.push(top->_right);
}
if (top->_left)
{
s.push(top->_left);
}
}
cout << endl;
}
中序遍历：(1)中序访问左子树；(2)访问根节点；(3)中序访问右子树.【3 2 4 1 6 5】
下面分别用递归和非递归两种方法实现
二叉树的递归实现中序序列
template
void BinaryTree::InOrder()//中序遍历（中根结点）
{
_InOrder(_root);
}
template
void BinaryTree::_InOrder(Node* root)
{
if (root == NULL)
{
return;
}
_InOrder(root->_left);
cout << root->_data << " ";
_InOrder(root->_right);
}
二叉树的非递归实现中序序列
//非递归实现（利用栈实现）
template
void BinaryTree::InOrder_NonR()//中序遍历-非递归
{
if (_root == NULL)
{
return;
}
stack s;
Node* cur = _root;
while (cur || !s.empty())
{
//压一棵树的左结点，直到最左结点
while (cur)
{
s.push(cur);
cur = cur->_left;
}
if (!s.empty())
{
Node* top = s.top();
cout << top->_data << " ";
s.pop();
cur = top->_right;//使cur指向最左结点top的右结点
}
}
cout << endl;
}
后序遍历(后根遍历)：(1)后序访问左子树；(2)后序访问右子树；(3)访问根节点.【3 4 2 6 5 1】
下面分别用递归和非递归两种方法实现
二叉树的递归实现后序序列
//递归实现
template
void BinaryTree::PostOrder()//后序遍历（后根结点）
{
_PostOrder(_root);
}
template
void BinaryTree::_PostOrder(Node* root)//后序遍历
{
if (root == NULL)
{
return;
}
_PostOrder(root->_left);
_PostOrder(root->_right);
cout << root->_data << " ";
}
//非递归实现（利用栈实现）
二叉树的非递归实现后序序列
template
void BinaryTree::PostOrder_NonR()//后序遍历-非递归
{
if (_root == NULL)
{
return;
}
stack s;
Node* cur = _root;
Node* prev = NULL;
while (cur || !s.empty())
{
//压一棵树的左结点，直到最左结点
while (cur)
{
s.push(cur);
cur = cur->_left;
}
Node* top = s.top();
if (top->_right == NULL || top->_right == prev)
{
cout << top->_data << " ";
s.pop();
prev = top;
}
else//当未访问过栈顶的右子树，则继续右子树的访问
{
cur = top->_right;
}
cout << endl;
}
}
层序遍历：一层层节点依次遍历。【1 2 5 3 4 6】
下面用非递归方法实现，利用队列进行访问。
//递归实现
template
void BinaryTree::LevelOrder()//层次遍历,通过队列实现
{
queue q;//建立队列存放Note*类型值
if (_root != NULL)
{
q.push(_root);
}
while (!q.empty())
{
Node* front = q.front();
cout << front->_data << " ";//访问队头
q.pop();//队头出队列
if (front->_left != NULL)//存在左或右结点入队列
{
q.push(front->_left);
}
if (front->_right != NULL)
{
q.push(front->_right);
}
}
cout << endl;
}
求树的结点个数，递归实现：
template
size_t BinaryTree::Size()//结点个数
{
return _Size(_root);
}
template
size_t BinaryTree::_Size(Node* root)
{
if (root == NULL)
{
return 0;
}//root不为0，则Size+1
return _Size(root->_left) + _Size(root->_right) + 1;
}
求树的深度，递归实现：
template
size_t BinaryTree::Depth()//树的深度
{
return _Depth(_root);
}
template
size_t BinaryTree::_Depth(Node* root)
{
if (root == NULL)
{
return 0;
}
size_t LeftDepth = _Depth(root->_left);
size_t RightDepth = _Depth(root->_right);
if (LeftDepth > RightDepth)//root不为0，则深度+1
{
return LeftDepth + 1;
}
else
{
return RightDepth + 1;
}
}
求树的叶子结点个数，递归实现：
//方法一
template
size_t BinaryTree::LeafSize()//叶子结点个数
{
return _LeafSize(_root);
}
template
size_t BinaryTree::_LeafSize(Node* root)
{
if (root == 0)
{
return 0;
}
if (root->_left == 0 && root->_right == 0)
{
return 1;
}
return _LeafSize(root->_left) + _LeafSize(root->_right);
}
//方法二:在LeafSize中定义_size表示叶子结点个数
template
size_t BinaryTree::LeafSize()//叶子结点个数
{
size_t _size = 0;
return _LeafSize(_root, _size);
}
template
size_t BinaryTree::_LeafSize(Node* root, size_t& size)
{
if (root == 0)
{
return 0;
}
if (root->_left == 0 && root->_right == 0)
{
++size;
return size;
}
_LeafSize(root->_left, size);
_LeafSize(root->_right, size);
return size;
}
二叉树中第k层结点的个数，递归实现：
//方法一
template
size_t BinaryTree::GetkLevel(int k)
{
assert(k>0);
return _GetkLevel(k, _root);
}
template
size_t BinaryTree::_GetkLevel(int k, Node* root)//第k层结点个数
{
if (root == NULL)
{
return 0;
}
if (k == 1)//利用递归使k递减，k==1结束
{
return 1;
}
size_t size1 = _GetkLevel(k - 1, root->_left);
size_t size2 = _GetkLevel(k - 1, root->_right);
return size1 + size2;
}
//方法二:在GetkLevel中定义size表示第k层结点个数
template
size_t BinaryTree::GetkLevel(int k)
{
assert(k > 0);
int size = 0;//size为二叉树第level层结点个数
int level = 1;//第level层
return _GetkLevel(k, _root, size, level);
}
template
size_t BinaryTree::_GetkLevel(int k, Node* root, int& size, int level)//第k层结点个数
{
if (root == NULL)
{
return 0;
}
if (level == k)
{
++size;
return size;
}
_GetkLevel(k, root->_left, size, level+1);
_GetkLevel(k, root->_right, size, level+1);
return size;
}
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
文章标题：递归与非递归实现二叉树-创新互联
网页URL：
http://cdkjz.cn/article/ddsssd.html
