一、二叉树
是结点的一个有限集合，每个根结点最多只有两颗子树，二叉树有左右之分，子树的次序不能颠倒。
二、二叉树的种类
1.满二叉树：每个结点都有左右子树，且叶结点都在同一层。
2.完全二叉树：一颗有N个结点的树，与满二叉树的前N个结点结构相同。
三、性质
1.度为0的结点的个数=度为2的结点的个数+1
2.以层序的方式对结点进行编号，规定第一个结点（根结点）为0。
1）i大于0时，其父母结点为(i-1)/2
2）序号为i的结点的左孩子为2i+1,右孩子为2i+2
四、二叉树的基本操作
1.二叉树的遍历
有前序（根左右），中序（左根右），后续（左右根），层序四种遍历方式
2.访问指对结点进行一些操作
五、操作代码
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
using namespace std;
template<class T>
struct BinTreeNode
{
BinTreeNode(const T& data) //结构体构造函数
:_left(NULL)
, _right(NULL)
, _data(data)
{}
BinTreeNode<T>* _left;
BinTreeNode<T>* _right;
T _data;
};
template<class T>
class BinTree
{
typedef BinTreeNode<T>* pNode;
typedef BinTreeNode<T> Node;
public:
BinTree()
: _pRoot(NULL)
{}
BinTree(const T* array, size_t size, const T& invalid)
{
size_t index = 0;//常数0不能引用
_CreateBinTree(_pRoot, array, size, index, invalid);
}
//拷贝构造函数，一个一个初始化
BinTree(const BinTree& bt)
{
_pRoot=_CopyBinTree(bt._pRoot);
}
//赋值运算符的重载，赋地址
BinTree& operator=(const BinTree& bt)
{
//删除旧空间
_DestroyBinTree(_pRoot);
_pRoot = _CopyBinTree(bt._pRoot);
return *this;
}
~BinTree()
{
_DestroyBinTree(_pRoot);
}
void PreOrder()
{
cout << "前序打印->";
_PreOrder(_pRoot);
}
void InOrder()
{
cout << "中序打印->";
_InOrder(_pRoot);
}
void PostOrder()
{
cout << "后序打印->";
_PostOrder(_pRoot);
}
//层序遍历
void LevelOrder()
{
cout << "层序打印->";
_LevelOrder(_pRoot);
}
size_t Size()
{
return _Size(_pRoot);
}
size_t GetLeefCount()
{
return _GetLeefCount(_pRoot);
}
// 获取第K层结点的个数
size_t GetKLevelCount(size_t K)
{
return _GetKLevelCount(_pRoot, K);
}
size_t Height()
{
return _Height(_pRoot);
}
pNode Find(const T& data)
{
return _Find(_pRoot, data);
}
pNode Parent(pNode pnode)
{
return _Parent(_pRoot,pnode);
}
pNode LeftChild(pNode pnode)
{
return _LeftChild(_pRoot, pnode);
}
pNode RightChild(pNode pnode)
{
return _RightChild(_pRoot, pnode);
}
private:
// 根+左子树+右子树，前序创建
void _CreateBinTree(pNode& pRoot, const T* array, size_t size, size_t& index, const T& invalid)
{
if (array == NULL)
{
return;
}
pNode proot = NULL;
while (index < size&&array[index] != invalid)//有效元素创建结点
{
proot = new Node(array[index]); //创建一个结点
_CreateBinTree(proot->_left, array, size, ++index,invalid);
_CreateBinTree(proot->_right, array, size, ++index, invalid);
}
pRoot = proot;
}
//前序递归构造
pNode _CopyBinTree(pNode pRoot)
{
if (_pRoot == pRoot)
{
return NULL;
}
pNode tmp = NULL;
if (pRoot)
{
tmp = new Node(pRoot->_data);
tmp->_left = _CopyBinTree(pRoot->_left);
tmp->_right = _CopyBinTree(pRoot->_right);
}
_pRoot = tmp;
return _pRoot;
}
//按照后序销毁，左-右-根
void _DestroyBinTree(pNode pRoot)
{
if (pRoot == NULL)
{
return;
}
if (pRoot)
{
_DestroyBinTree(pRoot->_left);
_DestroyBinTree(pRoot->_right);
delete pRoot;
pRoot = NULL;
}
}
// 根--->左子树--->右子树
void _PreOrder(pNode pRoot)
{
if (pRoot == NULL)
{
return;
}
cout << pRoot->_data;
_PreOrder(pRoot->_left);
_PreOrder(pRoot->_right);
}
// 左子树--->根节点--->右子树
void _InOrder(pNode pRoot)
{
if (pRoot == NULL)
{
return;
}
_InOrder(pRoot->_left);
cout << pRoot->_data;
_InOrder(pRoot->_right);
}
// 左子树--->右子树--->根节点
void _PostOrder(pNode pRoot)
{
if (pRoot == NULL)
{
return;
}
_PostOrder(pRoot->_left);
_PostOrder(pRoot->_right);
cout << pRoot->_data;
}
//层序打印，保存左右结点
void _LevelOrder(pNode pRoot)
{
if (_pRoot == NULL)
{
return;
}
queue<pNode> q;//队列中保存结点
pNode root = _pRoot;
q.push(root);
while (!q.empty())
{
pNode head = q.front();
cout << head->_data;
q.pop(); //读取后弹出，先进先出
if (head->_left)
{
q.push(head->_left);
}
if (head->_right)
{
q.push(head->_right);
}
}
}
size_t _Size(pNode pRoot)
{
if (pRoot == NULL)
{
return 0;
}
return _Size(pRoot->_left) + _Size(pRoot->_right) + 1;
}
size_t _GetLeefCount(pNode pRoot)
{
if (pRoot == NULL)
{
return 0;
}
if (pRoot->_left == NULL&&pRoot->_right == NULL)
{
return 1;
}
//左右子树都需要遍历
return _GetLeefCount(pRoot->_left) + _GetLeefCount(pRoot->_right);
}
size_t _Height(pNode pRoot)
{
if (pRoot == NULL)
{
return 0;
}
if (pRoot->_left == NULL&&pRoot->_right == NULL)
{
return 1;
}
size_t lefth = _Height(pRoot->_left)+1; //每遇到一层加一
size_t righth = _Height(pRoot->_right)+1;
return ((lefth > righth) ? lefth : righth);
}
pNode _Find(pNode pRoot, const T& data)
{
if (pRoot == NULL)
{
return NULL;
}
pNode root = pRoot;
if (root->_data == data)
{
return root;
}
if (root->_left)
{
return _Find(pRoot->_left, data);
}
if (root->_right)
{
return _Find(pRoot->_right, data);
}
}
size_t _GetKLevelCount(pNode pRoot, size_t K)
{
if (pRoot == NULL)
{
return 0;
}
if (K == 1)
{
return 1; //第一层有一个结点
}
size_t leftcount = _GetKLevelCount(pRoot->_left, K - 1);//K为3，则调用两次
size_t rightcount = _GetKLevelCount(pRoot->_right, K - 1);
return leftcount + rightcount;
}
pNode _Parent(pNode pRoot, pNode pnode)
{
if (pnode == NULL || pRoot == NULL)
{
return NULL;
}
pNode proot = pRoot;
if (proot->_left == pnode || proot->_right == pnode)
{
return proot;
}
if (proot->_left)
{
return _Parent(proot->_left,pnode);
}
if (proot->_right)
{
return _Parent(proot->_right,pnode);
}
}
pNode _LeftChild(pNode pRoot,pNode pnode)
{
if (pRoot == NULL || pnode == NULL)
{
return NULL;
}
if (pRoot == pnode)
{
return pRoot->_left;
}
if (pRoot->_left)
{
return _LeftChild(pRoot->_left, pnode);
}
if (pRoot->_right)
{
return _LeftChild(pRoot->_right, pnode);
}
}
pNode _RightChild(pNode pRoot, pNode pnode)
{
if (pRoot == NULL || pnode == NULL)
{
return NULL;
}
if (pRoot == pnode)
{
return pRoot->_right;
}
if (pRoot->_left)
{
return _RightChild(pRoot->_left, pnode);
}
if (pRoot->_right)
{
return _RightChild(pRoot->_right, pnode);
}
}
private:
pNode _pRoot;
};#include "BinTree.h"
int main()
{
char* arr = "ABD#G###CE##F##";
BinTree<char> bt(arr,15,'#');
BinTree<char> bt1;
bt1 = bt;
bt1.LevelOrder();
cout<<bt1.RightChild(bt1.Find('D'));
getchar();
return 0;
}