二叉树是重要的数据结构, 这里用c++简单实现,暂时不考虑其增加、删除和修改。
二叉树在底层其实就是用数组存储,可以用数组实现二叉树
首先创建一个结构体,在其中存储指针以及数据,这个结构体作为二叉树的节点使用
template <class T>
struct BinaryTreeNode //定义节点
{
BinaryTreeNode <T>* _left;
BinaryTreeNode <T>* _right;
T _data;
BinaryTreeNode(const T& data)
:_data(data)
,_left(NULL)
,_right(NULL)
{}
};
然后就可以利用数组建立二叉树:
BinaryTree(T * a, size_t n, const T& invalid) //创建二叉树,invalid为非法数据
{
size_t index = 0;
_root = CreateTree(a, n, invalid, index);
}
Node* CreateTree(T *a, size_t n, const T& invalid, size_t& index)
{
Node * root = NULL;
if (index < n && a[index] != invalid)
{
root = new Node(a[index]);
root->_left = CreateTree(a, n, invalid, ++index);
root->_right = CreateTree(a, n, invalid, ++index);
}
return root;
}
建立二叉树之后就得实现它的遍历,前序、中序和后序遍历用递归可以实现(二叉树较小可以使用,数据量太大时递归容易栈溢出)。
前序遍历:
前序遍历先访问根节点,其次是左根,最后才是右根
如图,从根节点开始,先访问根节点,然后是其左子树的根节点,继续往左边访问左子树的子树,当遇到NULL时则已经是叶子节点,此时最小的左子树已经访问完毕,即图中a区访问完毕,接下来就是a区根节点的右子树即b区,访问完毕之后就该b区根节点的右子树了,如此类推。
在访问完a区之后,访问b区和c区时的逻辑和访问a区相同,可以用递归实现,代码如下:
void PrevOrder()//前序遍历
{
_PrevOrder(_root);
cout << endl;
}
void _PrevOrder(Node* root)
{
if (NULL == root)
return;
cout << root->_data << " ";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}
中序遍历和后序遍历:
中序遍历和后序遍历的逻辑和前序遍历的逻辑相似,只是访问的顺序不同而已,代码见下:
void InOrder()//中序遍历
{
_InOrder(_root);
cout << endl;
}
void PostOrder()//后序遍历
{
_PostOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (NULL == root)
return;
_InOrder(root->_left);
cout << root->_data << " ";
_InOrder(root->_right);
}
void _PostOrder(Node* root)
{
if (NULL == root)
return;
_PostOrder(root->_left);
_PostOrder(root->_right);
cout << root->_data << " ";
}
层序遍历:
层序遍历需要用到队列实现,队列只能从队尾入队、从对头出队,先将根节点入队,然后在访问,访问之后就需要将其左根和右根分别入队,之后将对头的根节点删除,左根变为对头数据,取出访问再将其左右根节点分别入队,再删除头结点,拿出新的头结点访问……
整个过程逻辑相同,可以用一个循环就能实现,如下:
void LevlOrder()//层序遍历
{
_LevlOrder(_root);
}
void _LevlOrder(Node* root)//层序遍历依靠队列实现
{
queue<Node*> q;
if (NULL != root)
q.push(root);
while (!q.empty())
{
Node* front = q.front();
cout << front->_data << " ";
if (NULL != front->_left)
q.push(front->_left);
if (NULL != front->_right)
q.push(front->_right);
q.pop();
}
cout << endl;
}
除了遍历,还要实现查找函数、求深度、叶子结点的个数、每层的个数等等接口,完整代码如下:
#pragma once
#include <queue>
#include<iostream>
using namespace std;
template <class T>
struct BinaryTreeNode //节点
{
BinaryTreeNode <T>* _left;
BinaryTreeNode <T>* _right;
T _data;
BinaryTreeNode(const T& data)
:_data(data)
,_left(NULL)
,_right(NULL)
{}
};
template <class T>
class BinaryTree //二叉树
{
typedef BinaryTreeNode <T> Node;
public:
BinaryTree()
:_root(NULL)
{}
BinaryTree(T * a, size_t n, const T& invalid)//创建二叉树
{
size_t index = 0;
_root = CreateTree(a, n, invalid, index);
}
BinaryTree(const BinaryTree<T>& t)//拷贝构造函数
{
_root = _CopyBinaryTree(t._root);
}
//BinaryTree<T>& operator=(const BinaryTree<T>& t)//赋值运算符的重载
//{
// if (this != &t)
// {
// Destory(_root); //释放旧空间
// _root = _CopyBinaryTree(t._root);
// }
// return *this;
//}
BinaryTree<T>& operator=(BinaryTree<T>& t)//赋值运算符的重载
{
swap(_root, t._root);
return *this;
}
void PrevOrder()//前序遍历
{
_PrevOrder(_root);
cout << endl;
}
void InOrder()//中序遍历
{
_InOrder(_root);
cout << endl;
}
void PostOrder()//后序遍历
{
_PostOrder(_root);
cout << endl;
}
void LevlOrder()//层序遍历
{
_LevlOrder(_root);
}
Node* Find(const T& data)
{
return _Find(_root, data);
}
size_t Size()//节点数
{
return _Size(_root);
}
size_t LeafSize()//叶子结点数
{
return _LeafSize(_root);
}
size_t Depth()//深度
{
return _Depth(_root);
}
size_t GetKLevel(size_t k)//第k层的数据个数
{
return _GetKLevel(_root, k);
}
~BinaryTree()
{
Destroy(_root);
}
protected:
Node * CreateTree(T *a, size_t n, const T& invalid, size_t& index)
{
Node * root = NULL;
if (index < n && a[index] != invalid)
{
root = new Node(a[index]);
root->_left = CreateTree(a, n, invalid, ++index);
root->_right = CreateTree(a, n, invalid, ++index);
}
return root;
}
Node* _CopyBinaryTree(Node* root)
{
if (NULL == root)
{
return NULL;
}
Node* newRoot = new Node(root->_data);//拷贝根节点
newRoot->_left = _CopyBinaryTree(root->_left);
newRoot->_right = _CopyBinaryTree(root->_right);
return newRoot;
}
void Destroy(Node * root)
{
if (root == NULL)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
void _PrevOrder(Node* root)
{
if (NULL == root)
return;
cout << root->_data << " ";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}
void _InOrder(Node* root)
{
if (NULL == root)
return;
_InOrder(root->_left);
cout << root->_data << " ";
_InOrder(root->_right);
}
void _PostOrder(Node* root)
{
if (NULL == root)
return;
_PostOrder(root->_left);
_PostOrder(root->_right);
cout << root->_data << " ";
}
void _LevlOrder(Node* root)//层序遍历依靠队列实现
{
queue<Node*> q;
if (NULL != root)
q.push(root);
while (!q.empty())
{
Node* front = q.front();
cout << front->_data << " ";
if (NULL != front->_left)
q.push(front->_left);
if (NULL != front->_right)
q.push(front->_right);
q.pop();
}
cout << endl;
}
Node* _Find(Node* root, const T& x)
{
if (NULL == root)
return 0;
if (x == root->_data)
return root;
Node* ret = _Find(root->_left, x);
if (ret)
return ret;
return _Find(root->_right, x);
}
size_t _Size(Node* root)
{
if (NULL == root)
return 0;
return _Size(root->_left) + _Size(root->_right) + 1;
}
size_t _LeafSize(Node* root)
{
if (NULL == root)
return 0;
if ((NULL == root->_left) || (NULL == root->_right))
{
return 1;
}
return _LeafSize(root->_left) + _LeafSize(root->_right);
}
size_t _Depth(Node* root)
{
if (NULL == root)
return 0;
if ((NULL == root->_left) && (NULL == root->_right))
return 1;
size_t left = _Depth(root->_left);
size_t right = _Depth(root->_right);
return left > right ? left + 1 : right + 1;
}
size_t _GetKLevel(Node* root, size_t k)
{
if (NULL == root)
return 0;
if (1 == k)
return 1;
return _GetKLevel(root->_left, k - 1) + _GetKLevel(root->_right, k - 1);
}
protected:
Node * _root;
};
cs