二叉树：树的每个节点最多有两个子节点。
我们看下它的结构，有二叉链表结构与三叉链表结构，具体结果如我摘自《C++Primer》中的图。
相比之下，三叉链表的优势在于当我们知道父亲节点要找他的子女节点比较方便和便捷，反之当我们知道子女节点找它的父亲节点时也方便。
下面，我实现下二叉链表的结构。
template <class T>
struct BinaryTreeNode
{
BinaryTreeNode<T>* _left; //左子树
BinaryTreeNode<T>* _right; //右子树
T _data;
BinaryTreeNode(const T& x)
:_left(NULL)
, _right(NULL)
, _data(x)
{}
};（1）求二叉树的叶子节点数leafsize:
叶子节点指的是，节点无子女节点。我们有两种思路：
1）设置一下全局变量或者静态变量的size，遍历二叉树，每次遇到一个节点就加加一次size
2)总叶子节点数就等于左子树叶子节点个数+右子树叶子节点个数+根节点个数1
//思路1：
size_t _LeafSize(Node* root)
{
static int size = 0;
if (root == NULL)
{
return size;
}
if (root->_left == NULL && root->_right == NULL)
{
size++;
return size;
}
_LeafSize(root->_left);
_LeafSize(root->_right);
}//思路2：
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);
}（2）求二叉树的深度depth:
深度也称作为高度，就是左子树和右子树深度的较大值。
size_t _Depth(Node* root)
{
if (root == NULL)
{
return 0;
}
int LeftDepth = _Depth(root->_left);
int RightDepth = _Depth(root->_right);
return LeftDepth > RightDepth ? LeftDepth +1: RightDepth+1;
}（3）求二叉树的节点个数size:
总节点数就等于左子树节点个数+右子树节点个数+根节点个数1
size_t _Size(Node* root)
{
if (root == NULL)
{
return 0;
}
return _Size(root->_left) + _Size(root->_right) + 1;
}（4）遍历二叉树：
注意：前中后序遍历要不要漏掉递归出口。
1）前序遍历：访问根节点->左子树->右子树
void _PrevOrder(Node* root)
{
if (root == NULL)
{
return;
}
cout << root->_data << " ";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}2）中序遍历：访问左子树->根节点->右子树
void _InOrder(Node* root)
{
if (root == NULL)
{
return;
}
_InOrder(root->_left);
cout << root->_data << " ";
_InOrder(root->_right);
}3）后序遍历：访问左子树->右子树->根节点
void _PostOrder(Node* root)
{
if (root == NULL)
{
return;
}
_PostOrder(root->_left);
_PostOrder(root->_right);
cout << root->_data << " ";
}4）层次遍历：
即一层一层地遍历结束，再遍历下一层节点，如int a1[10] = { 1, 2, 3, ‘#‘, ‘#‘, 4, ‘#‘, ‘#‘, 5, 6 }（注意：#表示空。）则层次遍历就应为：1，2，5，3，4，6。
我们用队列解决该问题：首先先给队列无条件入队根节点，下面在出队根节点之前先入队它的子女节点2、5。此时，出队1后队头元素为2，在出队它之前入队它的根节点3，4……
void _LevelOrder(Node* root)
{
queue<Node*> q;
if (root == NULL)
{
return;
}
q.push(root);
while (!q.empty())
{
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();
}
}我给出完整程序代码（测试用例我就不要在此处多加阐述了，你们可以自己实现）。
#include<iostream>
using namespace std;
#include<queue>
template <class T>
struct BinaryTreeNode
{
BinaryTreeNode<T>* _left; //左子树
BinaryTreeNode<T>* _right; //右子树
T _data;
BinaryTreeNode(const T& x)
:_left(NULL)
, _right(NULL)
, _data(x)
{}
};
template<class T>
class BinaryTree
{
typedef BinaryTreeNode<T> Node; //重命名在于想简化代码，避免过长。
public:
BinaryTree()
:_root(NULL)
{}
BinaryTree(const T* a, size_t size, const T& invalid)
:_root(NULL)
{
size_t index = 0;
_root = _CreateTree(a, size, invalid, index);
}
BinaryTree<T>(const BinaryTree<T>& t)
: _root(NULL)
{
_Copy(t._root);
}
BinaryTree<T>& operator=(const BinaryTree<T>& t)
{
if (&t != this)
{
_Copy(t._root);
_Destroy(_root);
}
return *this;
}
~BinaryTree()
{
if (_root)
{
_Destroy(_root);
}
}
//前序遍历
void PreOrder()
{
_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:
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);
}
void _Copy(Node* troot)
{
if (troot == NULL)
{
return;
}
if (troot->_left == NULL&&troot->_right == NULL)
{
Node* root = new Node(troot->_data);
return;
}
root->_left = _Copy(troot->_left);
root->_right = _Copy(troot->_right);
}
//方法1：
/*size_t _LeafSize(Node* root)
{
static int size = 0;
if (root == NULL)
{
return size;
}
if (root->_left == NULL && root->_right == NULL)
{
size++;
return size;
}
_LeafSize(root->_left);
_LeafSize(root->_right);
}*/
//方法2：
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);
}
size_t _Size(Node* root)
{
if (root == NULL)
{
return 0;
}
return _Size(root->_left) + _Size(root->_right) + 1;
}
size_t _Depth(Node* root)
{
if (root == NULL)
{
return 0;
}
int LeftDepth = _Depth(root->_left);
int RightDepth = _Depth(root->_right);
return LeftDepth > RightDepth ? LeftDepth +1: RightDepth+1;
}
Node* _CreateTree(const T* a, size_t size, const T& invalid, size_t& index)
{
Node* root = NULL;
if (index < size && a[index] != invalid)
{
root = new Node(a[index]);
root->_left = _CreateTree(a, size, invalid, ++index);
root->_right = _CreateTree(a, size, invalid, ++index);
}
return root;
}
//前序遍历：访问根节点->左子树->右子树
void _PrevOrder(Node* root)
{
if (root == NULL)
{
return;
}
cout << root->_data << " ";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}
//中序遍历：访问左子树->根节点->右子树
void _InOrder(Node* root)
{
if (root == NULL)
{
return;
}
_InOrder(root->_left);
cout << root->_data << " ";
_InOrder(root->_right);
}
//后序遍历：访问左子树->右子树->根节点
void _PostOrder(Node* root)
{
if (root == NULL)
{
return;
}
_PostOrder(root->_left);
_PostOrder(root->_right);
cout << root->_data << " ";
}
void _LevelOrder(Node* root)
{
queue<Node*> q;
if (root == NULL)
{
return;
}
q.push(root);
while (!q.empty())
{
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();
}
}
protected:
Node* _root;
};本文出自 “C语言100-200素数” 博客，请务必保留此出处http://10740184.blog.51cto.com/10730184/1765514
【数据结构】二叉树的实现（如：默认成员函数、（叶子）节点数、深度、四种遍历）
原文：http://10740184.blog.51cto.com/10730184/1765514