```c++
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR -1
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
using namespace std;
typedef const char ElemType;
typedef int Status;
typedef enum PointerTag { Link, Thread } PointerTag;
//Link=0:指针；Thread=1：线索
//带线索的二叉树链表结构
typedef struct BiTNode {
ElemType data;
struct BiTNode* lchild, * rchild; //左右指针
PointerTag LTag, RTag; //左右标志
}BiTNode, * BiTree;
BiTree pre=NULL; //全局变量
//1-创建二叉树
//按先序次序输入二叉树中结点的值（一个字符），#字符表示空树
Status CreateBiTree(BiTree& T);
//2-先序遍历二叉树(递归算法)
//先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit
Status PreOrderTraverse(BiTree T, Status(*Visit)(ElemType));
//3-中序遍历二叉树(递归算法)
//中序遍历二叉树T的递归算法，对每个数据元素调用函数Visit
Status InOrderTraverse(BiTree T, Status(*Visit)(ElemType));
//4-后序遍历二叉树(递归算法)
//后序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。
Status PostOrderTraverse(BiTree T, Status(*Visit)(ElemType));
//5-中序遍历二叉树(非递归算法)
//中序遍历二叉树T的递归算法，对每个数据元素调用函数Visit，非递归算法，
//采用栈作为辅助结构，注意栈中存储的数据类型是指向树结点的指针
//Status InOrderTraverse1(BiTree T, Status(*Visit)(ElemType));
//6-层次遍历二叉树
//层次遍历二叉树T的递归算法，对每个数据元素调用函数Visit，采用队列作为辅助结构
Status LevelOrderTraverse(BiTree T, Status(*Visit)(ElemType));
//7-统计树的叶子结点个数
Status CountLeafs(BiTree T, int& numofleafs);
//8-统计树的层次数
int CountLevels(BiTree T, int& numofleafs);
//9-中序线索化二叉树
void InThreadingWithHead(BiTree p);
Status InOrderThreading_Head(BiTree& Thrt, BiTree T);
//10-遍历中序线索二叉树
Status InOrderTraverse2(BiTree T, Status* (Visit)(ElemType));
Status CreateBiTree(BiTree& T) {
// 按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，
// 构造二叉链表表示的二叉树T。
char ch;
scanf_s("%c", &ch);
if (ch == '#') T = NULL;
else {
if (!(T = (BiTNode*)malloc(sizeof(BiTNode))))
return ERROR;
ch=T->data ; // 生成根结点
T->LTag = Link;
T->RTag = Link;
CreateBiTree(T->lchild); // 构造左子树
CreateBiTree(T->rchild); // 构造右子树
}
}
Status Visit(ElemType e) {
printf("%c", e);
return OK;
}
//先序遍历递归调用
Status PreOrderTraverse(BiTree T, Status(*Visit)(ElemType)) {
if (T != NULL) {
Visit(T->data);
PreOrderTraverse(T->lchild, Visit);
PreOrderTraverse(T->rchild, Visit);
return OK;
}
return ERROR;
}
//中序遍历递归调用
Status InOrderTraverse(BiTree T, Status(*Visit)(ElemType)) {
if (T != NULL) {
InOrderTraverse(T->lchild, Visit);
Visit(T->data);
InOrderTraverse(T->rchild, Visit);
return OK;
}
return ERROR;
}
//后序遍历递归调用
Status PostOrderTraverse(BiTree T, Status(*Visit)(ElemType)) {
if (T != NULL) {
PostOrderTraverse(T->lchild, Visit);
PostOrderTraverse(T->rchild, Visit);
Visit(T->data);
return OK;
}
return ERROR;
}
//中序遍历非递归调用
//Status InOrderTraverse1(BiTree T, Status(*Visit)(ElemType)) {
// // 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。
// // 中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。
// BiTNode* Stack[100];
// int top = 0;
// BiTNode* p = T;
// while (p ||top!=0) {
// if (p) {
// Stack[top++]=p;
// p = p->lchild;
// }
// else {
// p = Stack[--top];
// Visit(p->data);
// p = p->rchild;
// }
// }
// return OK;
//
//}
//-统计树的叶子结点个数
Status CountLeafs(BiTree T, int& numofleafs) {
if (!T) return ERROR;
if (T->lchild == NULL && T->rchild == NULL) numofleafs++;
CountLeafs(T->lchild, numofleafs);
CountLeafs(T->rchild, numofleafs);
return OK;
}
//统计深度
Status CountLevels(BiTree T) {
int levelsoflchild = 0; int levelsofrchild = 0;
if (T) {
levelsoflchild = CountLevels(T->lchild);
levelsofrchild = CountLevels(T->rchild);
if (levelsoflchild > levelsofrchild) {
return 1 + levelsoflchild;
}
else
return 1 + levelsofrchild;
}
else {
return 0;
}
}
//层次遍历二叉树T的递归算法，对每个数据元素调用函数Visit，采用队列作为辅助结构
Status LevelOrderTraverse(BiTree T, Status(*Visit)(ElemType)) {
BiTNode* Queue[100], * p = T;
int f = 0, r = 0;
if (!T) return ERROR;
Queue[++r] = p;
while (f < r) {
p = Queue[++f];
Visit(p->data);
if (p->lchild != NULL) {
Queue[++r] = p->lchild;
}
if (p->rchild != NULL) {
Queue[++r] = p->rchild;
}
}
return OK;
}
//中序线索化二叉树
void InThreadingWithHead(BiTree p) { // 算法6.7
if (p) {
InThreadingWithHead(p->lchild); // 左子树线索化
if (!p->lchild) // 建前驱线索
{
p->LTag = Thread; p->lchild = pre;
}
if (!pre->rchild) // 建后继线索
{
pre->RTag = Thread; pre->rchild = p;
}
pre = p; // 保持pre指向p的前驱
InThreadingWithHead(p->rchild); // 右子树线索化
}
} // InThreading
Status InOrderThreading_Head(BiTree& Thrt, BiTree T) {
if (!(Thrt = (BiTree)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
Thrt->LTag = Link; Thrt->RTag = Thread; // 建头结点
Thrt->rchild = Thrt; // 右指针回指
if (!T) Thrt->lchild = Thrt; // 若二叉树空，则左指针回指
else {
Thrt->lchild = T; pre = Thrt;
InThreadingWithHead(T); // 算法6.7
pre->rchild = Thrt; pre->RTag = Thread; // 最后一个结点线索化
Thrt->rchild = pre;
}
return OK;
}// InOrderThreading
//遍历中序线索二叉树
Status InOrderTraverse2(BiTree T,Status*(Visit)(ElemType)) {
BiTNode *p = T->lchild;//从头结点进入到根结点；
while (p!=T)
{
while (p->LTag == Link)p = p->lchild;//先找到中序遍历起点
if (!Visit(p->data))return ERROR;//若起点值为空则出错
while (p->RTag == Thread && p->rchild != T)
p = p->rchild; Visit(p->data); // 访问后继结点
}
//若有后继标志，则直接提取p->rchild中线索并访问后继结点；
p = p->rchild; //当前结点右域不空或已经找好了后继，
//则一律从结点的右子树开始重复{ }的全部过程。
return OK;
}
int main() {
BiTree T = NULL;
BiTree Thrt = NULL;
int num = 0;
CreateBiTree(T);
InOrderThreading_Head(Thrt, T);
InOrderTraverse2(Thrt,Visit);
//PreOrderTraverse(T, Visit);
printf("\n");
InOrderTraverse(T, Visit);
printf("\n");
PostOrderTraverse(T, Visit);
printf("\n");
CountLeafs(T, num);
CountLevels(T);
printf("叶子结点个数为%d\n", num);
printf("树的层数为%d\n", num);
LevelOrderTraverse(T, Visit);
printf("\n");
InOrderTraverse1(T, Visit);//
}
