本节主要讲述二叉树中常见操作的 C++ 实现，重点是代码的实现，不拘泥于一种方法。
后续会根据做的一些题增加树的其他操作，并在个人的 github 持续更新中。
本部分基本涵盖了二叉树的基本操作，后续新增内容会在个人的 github 上持续更新。
此处对于二叉树的基本概念就不做赘述了，聚焦于代码上的实现。
二叉树的创建
首先，c++ 文件的基本结构走起来。
#include <bits/stdc++.h>
using namespace std;
int main(){
return 0;
}
之后，考虑二叉树的节点，为了泛用性，可以使用 typedef。
typedef string ElemType;
这里我们使用 string 类型作为节点类型，当然你也可以自定义其他类型。
然后定义树的节点，显然，根据树的定义，我们需要一个数据域 data 和两个节点类型的指针域 left 和 right，分别指向其左子树和右子树，使用 struct 类型即可。
完成这些后，我们在结构体里创建一个给节点数据域赋值的构造函数，其指针域都默认为空。
结构如下：
typedef string ElemType;
//定义树的节点
typedef struct BinaryNode{
//节点
ElemType data;
//左子树
BinaryNode* left;
//右子树
BinaryNode* right;
BinaryNode(ElemType value){
data = value;
left = NULL;
right = NULL;
}
}BinaryNode,*BiTree;
接下来，我们定义一个二叉树类，其私有成员部分有树根节点 mRoot ，节点总数(可有可无) size ，相关成员函数，共有成员部分也有相关成员函数。
二叉树的类如下：
//二叉树
class BinaryTree{
private:
//根节点
BiTree mRoot;
//节点总数
int size;
//按前序遍历方式递归创建二叉树
BiTree create();
//递归实现前序遍历
void preOrder(BiTree root);
//非递归实现前序遍历
void nonRec_preOrder(BiTree root);
//递归实现中序遍历
void inOrder(BiTree root);
//非递归实现中序遍历
void nonRec_inOrder(BiTree root);
//递归实现后序遍历
void postOrder(BiTree root);
//非递归实现后序遍历
void nonRec_postOrder(BiTree root);
//非递归实现层次遍历
void nonRec_levelOrder(BiTree root);
//递归实现摧毁树(前序遍历)
void destroy(BiTree root);
//递归得到树的节点数
int getSize(BiTree root);
//递归得到树的高度
int getHeight(BiTree root);
//得到叶子节点的个数
int getLeafs(BiTree root);
//得到度为1的节点个数
int getOneLeafs(BiTree root);
//得到满节点个数
int getFullLeafs(BiTree root);
//获取第 k 层的节点数
int getLevelSize(BiTree root,int level);
//查找指定值的节点
BiTree findNode(BiTree root,ElemType value);
public:
//按前序遍历方式递归创建二叉树
void createTree();
//递归实现前序遍历
void preOrder();
//非递归实现前序遍历
void nonRec_preOrder();
//递归实现中序遍历
void inOrder();
//非递归实现中序遍历
void nonRec_inOrder();
//递归实现后序遍历
void postOrder();
//非递归实现后序遍历
void nonRec_postOrder();
//递归实现层次遍历
void nonRec_levelOrder();
//递归实现摧毁树(前序遍历)
void destroy();
//递归得到树的节点数
int getSize();
//递归得到树的高度
int getHeight();
//得到叶子节点的个数
int getLeafs();
//得到度为1的节点个数
int getOneLeafs();
//得到满节点个数
int getFullLeafs();
//获取第 k 层的节点数
int getLevelSize(int level);
//判断是否为完全二叉树
bool isCompleteTree();
//查找指定值的节点
BiTree findNode(ElemType value);
};
后续继续增加一些功能，本系列的任务先实现上面给出所有的操作。
我们先来看按前序遍历方式递归创建二叉树，
私有函数部分：
void preOrder(BiTree root);
共有函数部分：
//按前序遍历方式递归创建二叉树
void createTree();
之后的操作基本上都分为相应的私有函数部分和共有函数部分，
同时一个功能的实现先给出私有函数部分，再给出其共有函数部分。
来看创建，我们使用的是前序遍历的方式，空节点使用 "#" (因为输入的是字符串类型)。
首先呢，我们创建型节点 newNode ，若输入的值为 "#" ，则返回为空，因为是空节点。
然后将输入的值 value 赋予新节点的数据域，最后递归创建该节点 newNode 的左子树和右子树。
代码如下：
//按前序遍历方式递归创建二叉树
BiTree BinaryTree::create(){
BiTree newNode = NULL;
ElemType value;
//此处 ElemType 应该是基本类型数据,若为自定义类型,请重载输入流
cin>>value;
//# 表示当前子树为空
if(value == "#"){
return NULL;
}else{
//递归创建左右子树,使用 size 记录下树的节点树
size++;
newNode = new BinaryNode(value);
newNode->left = create();
newNode->right = create();
return newNode;
}
}
void BinaryTree::createTree(){
size = 0;
mRoot = create();
}
这样一棵树就已经创建好了，当然树的创建方式有很多，这里只列举了一种，之后还会增加其他方式。
来测试下吧：
int main(){
BinaryTree tree;
cout<<"Please enter the tree in the previous order traversal mode.If the node is empty,use # instead:"<<endl;
//"A B D G # # H # # # C E # I # # F # #";
tree.createTree();
cout<<&tree<<endl;
return 0;
}
打印的结果为：
Please enter the tree in the previous order traversal mode.If the node is empty,use # instead:
A B D G # # H # # # C E # I # # F # #
0x62fe10
&tree 的内容可能有所不同，有结果，说明这棵树已经创建成功了！
树的遍历(递归 + 非递归)
在创建一棵树后，我们总想看看树里面有什么内容，那就遍历嘛。
树的遍历常见的有四种，前序遍历，中序遍历，后序遍历，层次遍历。
前三种既可以使用递归方法，也可以使用非递归。
层序遍历就是非递归了。
非递归过程中会用到 栈与队列 ，DFS 和 BFS 等概念。
前序遍历(递归 + 非递归)
先来看前序遍历的，前序遍历的顺序是根节点，左子树，右子树。
递归方法很简单，代码如下：
//递归实现前序遍历
void BinaryTree::preOrder(BiTree root){
if(root != NULL){
cout<<root->data<<" ";
preOrder(root->left);
preOrder(root->right);
}
}
void BinaryTree::preOrder(){
cout<<"The result of the preorder traversal is "<<endl;
preOrder(mRoot);
cout<<endl;
}
非递归需要用到 栈 的思想，和非递归遍历思想类似。我们还需要用栈保存节点，并访问数据域。
具体的代码如下：
//非递归实现前序遍历
void BinaryTree::nonRec_preOrder(BiTree root){
if(root == NULL){
return ;
}
stack<BiTree> s;
BiTree p = root;
s.push(p);
while(!s.empty()){
BiTree node = s.top();
cout<<node->data<<" ";
s.pop();
if(node->right){
s.push(node->right);
}
if(node->left){
s.push(node->left);
}
}
}
void BinaryTree::nonRec_preOrder(){
cout<<"The result of the non-recursive preorder traversal is "<<endl;
nonRec_preOrder(mRoot);
cout<<endl;
}
测试部分等四种遍历讲完后统一给出。
中序遍历(递归 + 非递归)
先来看中序遍历的，中序遍历的顺序是左子树，根节点，右子树。
递归方法很简单，代码如下：
//递归实现中序遍历
void BinaryTree::inOrder(BiTree root){
if(root != NULL){
inOrder(root->left);
cout<<root->data<<" ";
inOrder(root->right);
}
}
void BinaryTree::inOrder(){
cout<<"The result of the in-order traversal is "<<endl;
inOrder(mRoot);
cout<<endl;
}
在之前的非递归前序遍历的基础上，中序遍历也就不难了。
具体代码如下：
//非递归实现中序遍历
void BinaryTree::nonRec_inOrder(BiTree root){
if(root == NULL){
return ;
}
stack<BiTree> myStack;
BiTree rt = root;
while(rt != NULL || !myStack.empty()){
while(rt != NULL){
myStack.push(rt);
rt = rt->left;
}
rt = myStack.top();
myStack.pop();
cout<<rt->data<<" ";
rt = rt->right;
}
}
void BinaryTree::nonRec_inOrder(){
cout<<"The result of the non-recursive in-order traversal is "<<endl;
nonRec_inOrder(mRoot);
cout<<endl;
}
后序遍历(递归 + 非递归)
先来看后序遍历的，后序遍历的顺序是左子树，右子树，根节点。
递归方法很简单，代码如下：
//递归实现后序遍历
void BinaryTree::postOrder(BiTree root){
if(root != NULL){
postOrder(root->left);
postOrder(root->right);
cout<<root->data<<" ";
}
}
void BinaryTree::postOrder(){
cout<<"The result of the postorder traversal is "<<endl;
postOrder(mRoot);
cout<<endl;
}
仿照之前的非递归遍历，后序遍历的非递归的具体代码如下：
//非递归实现后序遍历,双栈法
/*
栈 s1 入栈顺序：根节点-> 左节点-> 右节点
栈 s2 入栈顺序：右节点-> 左节点-> 根节点
出栈顺序：根节点-> 左节点-> 右节点
*/
void BinaryTree::nonRec_postOrder(BiTree root){
if(root == NULL){
return ;
}
stack<BiTree> s1;
stack<BiTree> s2;
s1.push(root);
while(!s1.empty()){
BiTree p = s1.top();
s1.pop();
s2.push(p);
if(p->left){
s1.push(p->left);
}
if(p->right){
s1.push(p->right);
}
}
while(!s2.empty()){
cout<<s2.top()->data<<" ";
s2.pop();
}
}
void BinaryTree::nonRec_postOrder(){
cout<<"The result of the non-recursive postorder traversal is "<<endl;
nonRec_postOrder(mRoot);
cout<<endl;
}
层次遍历
层次遍历需要用到队列保存每一层的节点，一层层地访问，它不需要用到递归。
具体代码如下：
//非递归实现层次遍历
void BinaryTree::nonRec_levelOrder(BiTree root){
queue<BiTree> q;
q.push(root);
while(!q.empty()){
//每层的节点
int num_level = q.size();
while(num_level--){
BiTree node = q.front();
q.pop();
cout<<node->data<<" ";
if(node->left){
q.push(node->left);
}
if(node->right){
q.push(node->right);
}
}
}
}
void BinaryTree::nonRec_levelOrder(){
cout<<"The result of the non-recursive sequence traversal is "<<endl;
nonRec_levelOrder(mRoot);
cout<<endl;
}
汇总
我们来创建一棵树，并使用上面的方法分别遍历这棵树。
测试代码如下：
int main(){
BinaryTree tree;
cout<<"Please enter the tree in the previous order traversal mode.If the node is empty,use # instead:"<<endl;
//"A B D G # # H # # # C E # I # # F # #";
tree.createTree();
cout<<&tree<<endl;
//前序遍历
tree.preOrder();
//非递归前序遍历
tree.nonRec_preOrder();
//中序遍历
tree.inOrder();
//非递归中序遍历
tree.nonRec_inOrder();
//后序遍历
tree.postOrder();
//非递归后序遍历
tree.nonRec_postOrder();
//非递归层次遍历
tree.nonRec_levelOrder();
return 0;
}
打印的结果如下：
Please enter the tree in the previous order traversal mode.If the node is empty,use # instead:
A B D G # # H # # # C E # I # # F # #
0x62fe10
The result of the preorder traversal is
A B D G H C E I F
The result of the non-recursive preorder traversal is
A B D G H C E I F
The result of the in-order traversal is
G D H B A E I C F
The result of the non-recursive in-order traversal is
G D H B A E I C F
The result of the postorder traversal is
G H D B I E F C A
The result of the non-recursive postorder traversal is
G H D B I E F C A
The result of the non-recursive sequence traversal is
A B C D E F G H I
结果和我们画的树是一致的。
本节的内容就到这里了，之后继续实现其他的功能。
