二叉树：二叉树是一棵特殊的树，二叉树每个节点最多有两个孩子结点，分别称为左孩子和右孩子。
让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：申请域名、网页空间、营销软件、网站建设、廉江网站维护、网站推广。
二叉树节点结构：
struct BinaryTreeNode
{
T _data; //数据
BinaryTreeNode* _left; //指向左子树
BinaryTreeNode* _right; //指向右子树
BinaryTreeNode(const T& d)
:_data(d)
,_left(NULL)
,_right(NULL)
{}
};二叉树的创建：
Node* _CreateTree(const T* a, size_t size, size_t& index, const T& invilid)
{
Node* root = NULL;
if(index_left = _CreateTree(a, size, ++index, invilid); //递归实现左子树
root->_right = _CreateTree(a, size, ++index, invilid); //递归实现右子树
}
return root; //返回根节点
}前序遍历：
/* 前序遍历：根->左子树->右子树 */
void _PrevOrder(Node* root)
{
if(root == NULL)
{
return;
}
cout<_data<<" "; //打印根节点数据
_PrevOrder(root->_left); //递归遍历左子树
_PrevOrder(root->_right); //递归遍历右子树
}中序遍历：
/* 中序遍历：左子树->根->右子树 */
void _InOrder(Node* root)
{
if(root == NULL)
{
return;
}
_InOrder(root->_left); //递归遍历左子树
cout<_data<<" "; //打印根节点数据
_InOrder(root->_right); //递归遍历右子树
}后序遍历：
/* 后序遍历：左子树->右子树->根 */
void _PostOrder(Node* root)
{
if(root == NULL)
{
return;
}
_PostOrder(root->_left); //递归遍历左子树
_PostOrder(root->_right); //递归遍历右子树
cout<_data<<" "; //打印根节点数据
}层次遍历：
/* 层次遍历：第一层->最后一层 */
void _LevelOrder(Node* root)
{
queue qt;
if(root == NULL)
{
return;
}
qt.push(root); //将根节点压到队列中
while(!qt.empty())
{
/* 当根节点的左孩子不为空，就说明这一层还没有完全压入队列中 */
if(qt.front()->_left != NULL)
{
qt.push(qt.front()->_left); //将根节点左子树压到队列中
}
/* 当根节点的右孩子不为空，就说明这一层还没有完全压入队列中 */
if(qt.front()->_right != NULL)
{
qt.push(qt.front()->_right); //将根节点右子树压到队列中
}
cout<_data<<" "; //依次打印节点
qt.pop(); //将打印的节点出队列
}
}二叉树节点的个数 = 就是左子树节点个数加上右子树节点的个数再加上根节点
size_t _Size(Node* root)
{
if(root == NULL)
{
return 0;
}
return _Size(root->_left)+_Size(root->_right)+1;//左子树节点+右子树节点+根节点
}二叉树的深度 = 左子树 >= 右子树 ? 左子树+1， 右子树+1；
size_t _Depth(Node* root)
{
if(root == NULL)
{
return 0;
}
size_t LeftDepth = _Depth(root->_left);
size_t RightDepth = _Depth(root->_right);
if(LeftDepth >= RightDepth)
{
return LeftDepth+1;
}
else
{
return RightDepth+1;
}
}二叉树叶子节点的个数 = 左子树的叶子节点 个数+ 右子树的叶子节点个数
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);
}整体代码：
#include
#include
using namespace std;
template
struct BinaryTreeNode
{
T _data; //数据域
BinaryTreeNode* _left; //指向左子树
BinaryTreeNode* _right; //指向右子树
BinaryTreeNode(const T& d)
:_data(d)
,_left(NULL)
,_right(NULL)
{}
};
template
class BinaryTree
{
typedef BinaryTreeNode Node; //类型重命名，方便后面使用
public:
BinaryTree()
:_root(NULL)
{}
BinaryTree(const T* a, size_t size, const T& invilid)
:_root(NULL)
{
size_t index = 0;
_root = _CreateTree(a, size, index, invilid);
}
BinaryTree(const BinaryTree& tree)
{
_root = _Copy(tree._root);
}
BinaryTree& operator= (BinaryTree tree) //现代式写法
{
swap(_root, tree._root);
return *this;
}
~BinaryTree()
{
if(_root != NULL)
{
_Destroy(_root);
}
}
public:
void PrevOrder()
{
_PrevOrder(_root);
cout<_left)+_Size(root->_right)+1;
}
size_t _Depth(Node* root)
{
if(root == NULL)
{
return 0;
}
size_t LeftDepth = _Depth(root->_left);
size_t RightDepth = _Depth(root->_right);
if(LeftDepth >= RightDepth)
{
return LeftDepth+1;
}
else
{
return RightDepth+1;
}
}
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);
}
protected:
/* 前序遍历：根->左子树->右子树 */
void _PrevOrder(Node* root)
{
if(root == NULL)
{
return;
}
cout<_data<<" "; //打印根节点数据
_PrevOrder(root->_left); //递归遍历左子树
_PrevOrder(root->_right); //递归遍历右子树
}
/* 中序遍历：左子树->根->右子树 */
void _InOrder(Node* root)
{
if(root == NULL)
{
return;
}
_InOrder(root->_left); //递归遍历左子树
cout<_data<<" "; //打印根节点数据
_InOrder(root->_right); //递归遍历右子树
}
/* 后序遍历：左子树->右子树->根 */
void _PostOrder(Node* root)
{
if(root == NULL)
{
return;
}
_PostOrder(root->_left); //递归遍历左子树
_PostOrder(root->_right); //递归遍历右子树
cout<_data<<" "; //打印根节点数据
}
/* 层次遍历：第一层->最后一层 */
void _LevelOrder(Node* root)
{
queue qt;
if(root == NULL)
{
return;
}
qt.push(root);
while(!qt.empty())
{
if(qt.front()->_left != NULL)
{
qt.push(qt.front()->_left);
}
if(qt.front()->_right != NULL)
{
qt.push(qt.front()->_right);
}
cout<_data<<" ";
qt.pop();
}
}
protected:
Node* _Copy(Node* root)
{
if(root == NULL)
{
return NULL;
}
Node* NewRoot = new Node(root->_data); //创建新的根节点
Node* NewCur = NewRoot;
NewCur->_left = _Copy(root->_left);
NewCur->_right = _Copy(root->_right);
return NewRoot;
}
void _Destroy(Node* root)
{
if(root == NULL)
{
return;
}
if(root->_left == NULL && root->_right == NULL)
{
delete root;
root = NULL;
return;
}
_Destroy(root->_left);
_Destroy(root->_right);
}
Node* _CreateTree(const T* a, size_t size, size_t& index, const T& invilid)
{
Node* root = NULL;
if(index_left = _CreateTree(a, size, ++index, invilid);//递归实现左子树
root->_right = _CreateTree(a, size, ++index, invilid);//递归实现右子树
}
return root; //返回根节点
}
protected:
Node* _root; //根节点
};
int main()
{
Test();
system("pause");
return 0;
}
测试结构：
测试代码：
void Test()
{
int array[10] = {1, 2, 3, '#', '#', 4, '#' , '#', 5, 6};
BinaryTree tree(array, 10, '#');
tree.PrevOrder();
tree.InOrder();
tree.PostOrder();
tree.LevelOrder();
BinaryTree tree2(tree);
tree2.PrevOrder();
BinaryTree tree3 = tree2;
tree3.PrevOrder();
}测试结果：
当前文章：二叉树基础
本文链接：
http://cdkjz.cn/article/gpieeg.html
