二叉树是一种树形结构，它每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点）。
创新互联建站专注于白云企业网站建设,
成都响应式网站建设公司,
商城开发。白云网站建设公司,为白云等地区提供建站服务。全流程按需求定制开发，专业设计，全程项目跟踪，
创新互联建站专业和态度为您提供的服务
所谓度是结点拥有的子树数。
对于二叉树，它具有以下的性质：
1、在二叉树的第i层上至多有2^(i-1)个结点（i>=1）。
2、深度为k的二叉树至多有2^k-1个结点。
3、对任何一棵二叉树，如果它的叶子结点个数为n0，度为2的结点为n2，那么m = n + 1;
eg.如果设一个二叉树中度为1的结点个数为n1
故总结点数 N = n0 + n1 + n2; (1)
二叉树除了根结点外，其余结点都有一个分支，设M为分支总数，则 N = M + 1;由于这些分支是由度为1或2的结点射出的，则M = n1 + 2*n2;
则有 N = n1 + 2*n2 + 1 (2)
由（1）（2）得 n0 = n2 + 1;
4、具有n个结点的完全二叉树的深度为∟log 2 n」+1.(其中“∟x」 ”表示不大于x的大整数)。
5、如果对一棵有n个结点的完全二叉树的结点按层序编号（每一层从左到右，直到∟log 2 n」+1），则对任意一结点i（1=（1）如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点∟i/2」.
（2）如果2i>n,则结点i无左右孩子（结点i为叶子结点）否则其左孩子是结点2i；
（3）如果2i+1>n，则结点i无左右孩子；否则其右孩子是结点2i+1；
#pragma once
#include
#include
#include
using namespace std;
template
struct BinaryTreeNode
{
BinaryTreeNode *_left;
BinaryTreeNode *_right;
T _data;
public:
BinaryTreeNode(const T& x)
:_data(x)
,_right(NULL)
,_left(NULL)
{}
};
template
class BinaryTree
{
typedef BinaryTreeNode Node;
public:
BinaryTree()
:_root(NULL)
{}
BinaryTree(const T* a, size_t size, const T& invalid)
{
size_t index = 0;
_root = _CreatTree(a, size, index, invalid);
}
BinaryTree(const BinaryTree& t)
{
_root=_Copy(t._root);
}
BinaryTree& operator=( BinaryTree t)
{
swap(_root, t._root);
return *this;
}
~BinaryTree()
{
_Clear(_root);
_root=NULL;
}
void PrevOrder()
{
cout << "先序：" << endl;
_PrevOrder(_root);
}
void InOrder()
{
cout << "中序：" << endl;
_InOrder(_root);
}
void PostOrder()
{
cout << "后序：" << endl;
_PostOrder(_root);
}
//层序
//思想：队列
//1.先判断根节点是否为NULL
//2.如果根节点不为空，节点入队（不是入值）
//3.判断队列是否为空，如果不为空，出队
//4.判断左 右子树节点是否为空，
//5.如果不为空，入队 左右节点，跳至2
void LeveLorder() //层序
{
cout << "层序：" << endl;
queue tmp;
if (_root == NULL)
return;
else
{
tmp.push(_root);
while (!tmp.empty())
{
Node* Front = tmp.front();
cout << Front->_data << " ";
tmp.pop();
if (Front->_left)
{
tmp.push(Front->_left);
}
if (Front->_right)
{
tmp.push(Front->_right);
}
}
}
}
size_t Size()
{
return _Size(_root);
}
size_t Depth()
{
_Depth(_root);
}
size_t LeafSize()
{
return _leafSize(_root);
}
protected:
Node* _CreatTree(const T*a, size_t size, size_t& index, const T& invalid)
{
Node* root = NULL;
if (a[index] != invalid&&index < size)
{
root = new Node(a[index]);
root->_left = _CreatTree(a, size, ++index, invalid);//++index 返回index index++返回临时变量（在此编译不通过）
root->_right = _CreatTree(a, size, ++index, invalid);
}
return root;
}
//先序遍历 递归形式
void _PrevOrder(Node* root)
{
if (root == NULL)
return;
cout << root->_data << " ";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}
//先序遍历 非递归 借助栈
//和层序实现差不多，只是一个是借助队，一个是借助栈
void _PrevOrder(Node* root)
{
stack cur;
if (root == NULL) //1.先判断根结点是否为空
return;
else
{
cur.push(root); //2,压栈
while (!cur.empty()) // 3.判断栈是否为空，不为空，先压右 再压左子树
{
Node* temp = cur.top();
cout << temp->_data << " ";
cur.pop();
if (temp->_right)
{
cur.push(temp->_right);
}
if (temp->_left)
{
cur.push(temp->_left);
}
}
}
}
//中序遍历 递归形式
void _InOrder(Node* root)
{
if (root == NULL)
return;
_InOrder(root->_left);
cout << root->_data << " ";
_InOrder(root->_right);
}
//中序遍历 非递归 借助栈
void _InOrder(Node* root)
{
Node* cur = root;
stack tack;
while (cur || !tack.empty())
{
while (cur)
{
tack.push(cur);
cur = cur->_left;
}
if (!tack.empty())
{
Node* Top = tack.top();
tack.pop();
cout << Top->_data <<" ";
cur = Top->_right;
}
}
}
//后序遍历 递归形式
void _PostOrder(Node* root)
{
if (root == NULL)
return;
_PostOrder(root->_left);
_PostOrder(root->_right);
cout << root->_data << " ";
}
//后序遍历 非递归 借助栈
void _PostOrder(Node* root)
{
Node* prev=NULL;
Node* cur = root;
stack tmp;
while (cur || !tmp.empty())
{
while (cur)
{
tmp.push(cur);
cur = cur->_left;
}
Node* Top = tmp.top();
if (Top->_right == NULL||Top->_right==prev)
{
cout << Top->_data << " ";
tmp.pop();
prev = Top;
cur = NULL;
}
else
{
cur = Top->_right;
}
}
}
void _Size(Node* root)
{
if (root == NULL)
return 0;
return _Size(root->_left) + _Size(root->_right) + 1;
}
size_t _Depth(Node* root)
{
if (root == NULL)
return 0;
int leftdepth = _Depth(root->_left);
int rightdepth = _Depth(root->_right);
return leftdepth > rightdepth ? leftdepth + 1 : rightdepth + 1;
}
size_t _leafSize(Node* root)
{
static size_t size = 0;
if (root == NULL)
return 0;
if (root->_left == NULL&&root->_right == NULL)
{
++size;
return size;
}
_leafSize(root->_left);
_leafSize(root->_right);
return size;
}
void _Clear(Node* root)
{
if (root)
{
_Clear(root->_left);
_Clear(root->_right);
delete root;
}
}
Node* _Copy(Node* root)
{
if (root==NULL)
{
return NULL;
}
Node *tem = new Node(root->_data);
tem->_left=_Copy(root->_left);
tem->_right=_Copy(root->_right);
return tem;
}
private:
Node* _root;
};
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
分享题目：二叉树的先序、中序、后序、层序递归及非递归遍历-创新互联
转载来源：http://cdxtjz.com/article/jsppj.html
