二叉树是数的一种特殊情况，每个节点只能有左右两个孩子节点，二叉树的好处就是方便表示。
这里主要写了二叉树的先序，中序，后序遍历（这里不会细讲这个是什么东西，不知道的请自行百度）。然后还有计算二叉树的深度，二叉树的节点个数。
下面的代码都是基于上面这个图形进行的遍历。
#include"pch.h"
#include <iostream>
using namespace std;
#define MAXSIZE 100
typedef struct BiTNode
{
//二叉树的存储结构
char data;
struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;
typedef struct
{
//结构体定义了三个变量
//一个是栈顶指针，一个是栈底指针
BiTree *base;
BiTree *top;
int stacksize;
}sqstack;
bool TreeInit(BiTree &T);
void InorderTraverse(BiTree T);
void FrontTraverse(BiTree T);
void BackTraverse(BiTree T);
bool InitStack(sqstack &s);
bool Push(sqstack &s, BiTree e);
bool Pop(sqstack &s, BiTree &e);
void StackInorderTraverse(BiTree T);
void CreateBitree(BiTree &T);
int Depth(BiTree T);
int NodeCount(BiTree T);
int main()
{
BiTree T = new BiTNode;
//TreeInit(T);
CreateBitree(T);
cout << "中序遍历：";
InorderTraverse(T);
cout<<endl << "先序遍历：";
FrontTraverse(T);
cout << endl << "后序遍历：";
BackTraverse(T);
cout << endl << "非递归中序遍历：";
StackInorderTraverse(T);
cout << endl << "树的深度为：" << Depth(T);
cout << endl << "节点个数为：" << NodeCount(T);
//system("pause");
return 0;
}
//计算节点个数
int NodeCount(BiTree T)
{
if (T == NULL) return 0;//如果是空树则返回空
else return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
//否则就直接返回左节点+右节点数+1（这个是遍历算法，遍历次数就等于节点个数）
}
//计算二叉树的深度
int Depth(BiTree T)
{
int m, n;
if (T == NULL) return 0;//如果是空树，那么记为0
else
{
m = Depth(T->lchild);//遍历计算右子树的深度
n = Depth(T->rchild);//遍历计算左子树的深度
if (m > n) return (m + 1);
else return (n + 1);//判断哪个大就返回哪个（+1就相当于深度+1）
}
}
//先序遍历建立二叉链表
void CreateBitree(BiTree &T)
{
//就是先给根节点赋值，然后在遍历创建左子树，最后再遍历创建右子树
char ch;
cin >> ch;
if (ch == '#') T = NULL;
else
{
T = new BiTNode;
T->data = ch;
CreateBitree(T->lchild);
CreateBitree(T->rchild);
}
}
//非递归实现中序遍历
void StackInorderTraverse(BiTree T)
{
sqstack *s = new sqstack;
InitStack(*s);
BiTree p = T;
BiTree q = new BiTNode;
while (p || s->top != s->base)
{
if (p)
{
//这里利用了两个BiTree指针，其核心思想就是先把最左子树进栈
//然后在把最左子树出栈并输出值，最后就是把右子树进栈
Push(*s, p);
p = p->lchild;
}
else
{
Pop(*s, q);
cout << q->data<<" ";
p = q->rchild;
}
}
}
//栈的初始化
bool InitStack(sqstack &s)
{
//初始化一个空栈，然后让栈顶指针指向栈底
s.base = new BiTree[MAXSIZE];
if (!s.base) return false;
s.top = s.base;
s.stacksize = MAXSIZE;
return true;
}
//入栈
bool Push(sqstack &s, BiTree e)
{
//判断栈是否满了
if (s.top - s.base == s.stacksize) return false;
//注意s.top其实不是存储的栈顶元素，它在栈顶元素的上面一个，所以是先赋值后加
*s.top++ = e;
return true;
}
//出栈
bool Pop(sqstack &s,BiTree &e)
{
if (s.top == s.base) return false;
//出栈就是把栈顶元素先减1然后在赋值
e = *--s.top;
return true;
}
bool TreeInit(BiTree &T)
{
//二叉树的初始化，我们这里直接赋值5个节点
T->data = 'a';
T->lchild = new BiTNode;
T->rchild = new BiTNode;
T->lchild->lchild = new BiTNode;
T->lchild->rchild = new BiTNode;
T->lchild->data = 'b';
T->rchild->data = 'c';
T->rchild->lchild = NULL;//这里记得把子节点的左右子树都置为空
T->rchild->rchild = NULL;
T->lchild->lchild->data = 'd';
T->lchild->lchild->lchild = NULL;
T->lchild->lchild->rchild = NULL;
T->lchild->rchild->data = 'e';
T->lchild->rchild->lchild = NULL;
T->lchild->rchild->rchild = NULL;
return true;
}
//中序遍历二叉树
void InorderTraverse(BiTree T)
{
if (T)
{
//中序遍历的核心思想就是先遍历左子树，然后在遍历中子树，最后遍历右子树
//这里利用的递归的思想巧妙的实现了这个效果，我这里也很难解释，
//如果你对中序遍历很熟悉的话，那么这个其实也很好理解
InorderTraverse(T->lchild);
cout << T->data << " ";
InorderTraverse(T->rchild);
}
}
//先序遍历
void FrontTraverse(BiTree T)
{
if (T)
{
//先序遍历其实和中序遍历的代码差别不大，就是改变一下顺序即可
cout << T->data << " ";
FrontTraverse(T->lchild);
FrontTraverse(T->rchild);
}
}
//后序遍历
void BackTraverse(BiTree T)
{
if (T)
{
//后序遍历就是先访问左子树，然后在访问右子树，最后访问根节点
BackTraverse(T->lchild);
BackTraverse(T->rchild);
cout << T->data << " ";
}
}
实际效果：
