二叉树
在蕉岭等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供网站建设、成都网站建设 网站设计制作按需规划网站,公司网站建设,企业网站建设,高端网站设计,全网营销推广,外贸网站制作,蕉岭网站建设费用合理。
二叉树:二叉树是一棵特殊的树，二叉树每个节点最多有两个孩子结点，分别称为左孩子和右孩子
满二叉树:高度为N的满二叉树有2^N - 1个节点的二叉树。
完全二叉树: 若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树
二叉树的存储结构
数组表示存储
链表存储表示：
数组表示法用于完全二叉树的存储非常有效，但表示一般的二叉树则不是很理想。此外，在一棵树中进行插入和删除时，为了反映节点的层次变化，可能需要移动许多节点，降低了算法效率，二使用连接表示，可以克服这些缺点。
根据二叉树的定义，可以设计出二叉树的节点结构。二叉树的每一个节点有三个域：数据域_data，左子女节点指针_leftChild，右子女节点指针_rightChild。这中链表称为二叉链表。使用这种结构，可以很方便的根据左右孩子指针找到他的左右孩子。但要找到他的双亲很难。为了找到双亲节点，可以在节点中在增加一个双亲指针域_parent，他被称为三叉链表结构。
楼主主要实现的是二叉链表结构
节点的定义
//节点结构
template
struct BinaryTreeNode
{
//构造函数
BinaryTreeNode(const T& data)
:_data(data)
,_leftChild(NULL)
,_rightChild(NULL)
{}
public:
T _data;//数据域
BinaryTreeNode* _leftChild;//左孩子指针
BinaryTreeNode* _rightChild;//右孩子指针
};
二叉树的实现
//二叉树类
template
class BinaryTree
{
typedef BinaryTreeNode Node;
public:
BinaryTree()
:_root(NULL)
{}
//构造函数
BinaryTree(const T* a, size_t size, const T& invalid)
{
assert(a);
size_t index = 0;
_root = _CreateTree(a, size, invalid,index);
}
//拷贝构造
BinaryTree(const BinaryTree& t)
{
_root = _Copy(t._root);
}
//赋值运算符的重载
BinaryTree& operator=(BinaryTree t)
{
swap(_root, t._root);
return *this;
}
//析构函数
~BinaryTree()
{
_Destory(_root);
}
public:
//前序遍历
void PrevOrder()
{
_PrevOrder(_root);
cout << endl;
}
//中序遍历
void InOrder()
{
_InOrder(_root);
cout << endl;
}
//后序遍历
void PostOrder()
{
_PostOrder(_root);
cout << endl;
}
//层次遍历
void LevelOrder()
{
_LevelOrder(_root);
cout << endl;
}
//求二叉树的节点个数
size_t Size()
{
return _Size(_root);
}
//求二叉树的深度
size_t Depth()
{
return _Depth(_root);
}
//求二叉树的叶子节点的个数
size_t LeafSize()
{
return _LeafSize(_root);
}
protected:
Node* _CreateTree(const T* a, size_t size, const T& invalid, size_t& index)
//index要传引用，需要更改index的值
{
Node* root = NULL;
//判断数组是否越界和输入的值是否合法
if (index < size&&a[index] != invalid)
{
root = new Node(a[index]);//创建根节点
root->_leftChild = _CreateTree(a, size, invalid, ++index);//递归创建左子树
root->_rightChild = _CreateTree(a, size, invalid, ++index);//递归创建右子树
}
return root;//返回根节点
}
void _PrevOrder(Node* root)
{
//如果节点为空则直接返回
if (root == NULL)
{
return;
}
cout << root->_data << " ";//访问根节点
_PrevOrder(root->_leftChild);//递归访问左子树
_PrevOrder(root->_rightChild);//递归访问右子树
}
void _InOrder(Node* root)
{
//如果节点为空则直接返回
if (root == NULL)
{
return;
}
_InOrder(root->_leftChild);//访问左子树
cout << root->_data << " ";//递归访问根节点
_InOrder(root->_rightChild);//递归访问右子树
}
void _PostOrder(Node* root)
{
//如果节点为空则直接返回
if (root == NULL)
{
return;
}
_PostOrder(root->_leftChild);//访问左子树
_PostOrder(root->_rightChild);//递归访问右子树
cout << root->_data << " ";//递归访问根节点
}
//层次遍历
void _LevelOrder(Node* root)
{
if (root == NULL)
{
return;
}
queue q;
q.push(root);//根节点入队
while (!q.empty())//当队列不为空
{
if (q.front()->_leftChild)
{
q.push(q.front()->_leftChild);
}
if (q.front()->_rightChild)
{
q.push(q.front()->_rightChild);
}
cout << q.front()->_data << " ";
q.pop();
}
}
size_t _Size(Node* root)
{
size_t count = 0;
if (root == NULL)
{
return count;//树为空
}
count++;//根节点
count += _Size(root->_leftChild);//计算左子树大小
count+= _Size(root->_rightChild);//计算右子树大小
return count;
}
//返回左右子树深度较大的
size_t _Depth(Node* root)
{
if (root == NULL)
{
return 0;
}
size_t LeftDepth = _Depth(root->_leftChild);
size_t RightDepth= _Depth(root->_rightChild);
if (LeftDepth > RightDepth)
{
return ++LeftDepth;
}
else
{
return ++RightDepth;
}
}
size_t _LeafSize(Node*root)
{
if (root == NULL)
{
return 0;
}
if (root->_leftChild == NULL && root->_rightChild == NULL)
{
return 1;
}
return _LeafSize(root->_leftChild)+ _LeafSize(root->_rightChild);
}
Node* _Copy(Node* root)
{
if (root == NULL)
{
return NULL;
}
Node* newRoot = new Node(root->_data);
newRoot->_leftChild = _Copy(root->_leftChild);
newRoot->_rightChild = _Copy(root->_rightChild);
return newRoot;
}
void _Destory(Node* root)
{
if (root == NULL)
{
return;
}
//删除叶结点
if (root->_leftChild == NULL&&root->_rightChild == NULL)
{
delete root;
root = NULL;
return;
}
_Destory(root->_leftChild);//递归删除左子树
_Destory(root->_rightChild);//递归删除右子树
delete root;
}
private:
BinaryTreeNode* _root;//根节点
};
测试代码
#include"BinaryTree.h"
void TestBinary()
{
/*int a1[10] = { 1,2,3,'#','#',4,'#','#',5,6 };
BinaryTree t1(a1, 10, '#');
cout << "先序遍历：";
t1.PrevOrder();
cout << "中序遍历：";
t1.InOrder();
cout << "后序遍历：";
t1.PostOrder();
cout << "层次遍历：";
t1.LevelOrder();
cout << "size:" << t1.Size() << endl;
cout << "depth:" << t1.Depth() << endl;
cout << "leafSize:" << t1.LeafSize() << endl;*/
int a2[15] = { 1,2,'#',3,'#','#',4,5,'#',6 ,'#' ,7,'#' ,'#' ,8 };
int a[] = { 1,2,'#','#',3 };
BinaryTree t1(a, 5, '#');
BinaryTree t2;
t2 = t1;
cout << "先序遍历：";
t2.PrevOrder();
cout << "中序遍历：";
t2.InOrder();
cout << "后序遍历：";
t2.PostOrder();
cout << "层次遍历：";
t2.LevelOrder();
cout << "size:" << t2.Size() << endl;
cout << "depth:" << t2.Depth() << endl;
cout << "leafSize:" << t2.LeafSize() << endl;
}
int main()
{
TestBinary();
getchar();
return 0;
}测试结果
本文标题：二叉树的简单递归实现（创建，遍历，高度，大小）
网页链接：
http://cdxtjz.cn/article/pjjhei.html
