1.树的节点：节点包含数据和指向其它节点的指针，因为不知道有几个指向其它节点的指针呢个，所以树的结构变得难以定义（因为子节点的个数是未知的），这是可以采用左孩子和右兄弟的表示方法，左孩子可以访问左子树的节点，用右子树可以一直往下访问它的兄弟节点，这样就可以实现树的定义和访问。
2.二叉树：对于二叉树，它只有左子树和右子树，所以二叉树就不难表示，二叉链中包含数据，指向左子树的指针和指向右子树的指针，三叉链中包含数据，指向左子树的指针，指向右子树的指针和指向父亲节点的指针。
3.二叉树的遍历：
先序：根节点->左子树节点->右子树节点
中根：左子树节点->根节点->右子树节点
后根：左子树节点->左子树节点->根节点
#pragma once
#include<iostream>
#include<queue>
using namespace std;
template <typename T>
struct BinaryTreeNode
{
BinaryTreeNode<T >* _left;
BinaryTreeNode<T >* _right;
T _data;
BinaryTreeNode( const T & data)
:_data( data)
, _left( NULL)
, _right( NULL)
{
}
};
template<typename T>
class BinaryTree
{
public:
BinaryTree()
:_root( NULL)
{
}
BinaryTree( const T * a,int size,const T& invalid)
{
int pos = 0;
_root = _CreatBinaryTree( a,pos,size ,invalid);
}
~BinaryTree()
{
int pos = 0;
_DelBinaryTree(_root);
cout << endl;
}
BinaryTree( const BinaryTree <T>& b)//树的拷贝构造
{
_root=_CopyBinaryTree( b._root);
}
BinaryTree<T >& operator=(BinaryTree< T> b )
{
swap(_root, b._root);//现代写法
return *this ;
}
void PrevOrder()//先序遍历
{
_PrintPrevOrder(_root);
cout << endl;
}
void InOrder()//中序遍历
{
_PrintInOrder(_root);
cout << endl;
}
void PostOrder()//后序遍历
{
_PrintPostOrder(_root);
cout << endl;
}
void LevelOrder()//层序遍历
{
_PrintLevelOrder(_root);
}
size_t Size()
{
return _Size(_root);
}
size_t Depth()
{
return _Depth(_root);
}
size_t LeafSize()//叶子节点个数
{
return _LeafSize(_root);
}
protected:
BinaryTreeNode<T >* _CopyBinaryTree(BinaryTreeNode< T>* root )//复制树
{
BinaryTreeNode<T >* newroot = NULL;
if (root == NULL)
{
return NULL ;
}
newroot = new BinaryTreeNode <T>(root->_data);
newroot->_left = _CopyBinaryTree( root->_left);
newroot->_right = _CopyBinaryTree( root->_right);
return newroot;
}
int _LeafSize(BinaryTreeNode <T>* root)//树的叶子节点个数(左子树叶子节点个数+右子树叶子节点个数)
{
if (root ==NULL)
{
return 0;
}
else if (root->_left == NULL&&root ->_right == NULL)
{
return 1;
}
else
{
return _LeafSize(root ->_left) + _LeafSize(root->_right);
}
}
int _Depth(BinaryTreeNode <T>* root)//树的深度
{
int leftdepth = 0;
int rightdepth = 0;
if (root == NULL)
{
return 0;
}
leftdepth = _Depth( root->_left);
rightdepth = _Depth( root->_right);
return _Depth(root ->_left) > _Depth(root->_right) ? leftdepth + 1: rightdepth + 1;
}
int _Size(BinaryTreeNode <T>* root)//树的节点个数
{
if (root ==NULL)
{
return 0;
}
return _Size(root ->_left) + _Size(root->_right) + 1; //左子树个数+右子树个数+跟节点
}
void _PrintLevelOrder(BinaryTreeNode <T>* root)//层序遍历(借助队来实现)
{
queue<BinaryTreeNode <T>*> q;
if (root == NULL)
{
return;
}
q.push( root);
while (q.size())
{
if (q.front()->_left != NULL )
{
q.push(q.front()->_left);
}
if (q.front()->_right != NULL )
{
q.push(q.front()->_right);
}
cout << q.front()->_data << " " ;
q.pop();
}
}
void _PrintPrevOrder(BinaryTreeNode <T>* root)//先序打印
{
if (root == NULL)
{
return;
}
cout << root->_data << " " ;
_PrintInOrder( root->_left);
_PrintInOrder( root->_right);
}
void _PrintInOrder(BinaryTreeNode <T>* root)//中序遍历
{
if (root == NULL)
{
return;
}
_PrintInOrder( root->_left);
cout << root->_data << " " ;
_PrintInOrder( root->_right);
}
void _PrintPostOrder(BinaryTreeNode <T>* root)//后序遍历
{
if (root == NULL)
{
return;
}
_PrintPostOrder( root->_left);
_PrintPostOrder( root->_right);
cout << root->_data << " " ;
}
void _DelBinaryTree(BinaryTreeNode <T>* root)//删除二叉树
{
if (root == NULL)
{
return;
}
if (root ->_left == NULL&& root->_right == NULL )
{
delete root ;
return;
}
_DelBinaryTree( root->_left);
_DelBinaryTree( root->_right);
}
BinaryTreeNode<T >* _CreatBinaryTree(const T* a, int& pos,int size, const T& invalid)//创建一个二叉树
{
BinaryTreeNode<T >* root=NULL;
if (a [pos] != invalid&&pos <size)
{
root = new BinaryTreeNode <T>(a[pos]);
root->_left = _CreatBinaryTree(a , ++pos, size, invalid);
root->_right = _CreatBinaryTree(a ,++pos, size, invalid);
}
return root;
}
private:
BinaryTreeNode<T >* _root;
};
/*******************************/
#include"BinaryTree.h"
void test()
{
int a1[10] = { 1, 2, 3, '#' , '#', 4, '#', '#' , 5, 6 };
BinaryTree<int > b1(a1, 10, '#');//将#封装，这样灵活性更强，可以改变
//b1.PrevOrder();
/*b1.InOrder();
b1.PostOrder();
b1.LevelOrder();*/
//cout << endl;
//cout << b1.Size() << endl;;
BinaryTree<int > b2;
b2 = b1;
b2.PrevOrder();
b2.InOrder();
b2.PostOrder();
//cout<<b2.Size()<<endl;
//cout<<b2.Depth()<<endl;
cout << b1.LeafSize() << endl;
}