数据结构-二叉树的遍历及相关应用

1、定义二叉树结点结构

2、编写主程序

3、三种方法遍历二叉树，并实现求树的深度，叶子数，某一层的结点数

4、实现代码（带交互界面）

#include<iostream>
using namespace std;
typedef struct BiTNode
{char data;struct BiTNode* lchild, * rchild;
}BiTNode, * BitTree;BitTree creatTree()
{BitTree T = NULL;char ch;cin >> ch;if (ch == '#'){T = NULL;return T;}else{T = new BiTNode;if (T == NULL)return NULL;T->data = ch;T->lchild = NULL;T->rchild = NULL;T->lchild = creatTree();T->rchild = creatTree();return T;}
}
void Zhongxu(BitTree T)
{if (T){Zhongxu(T->lchild);cout << T->data;Zhongxu(T->rchild);}
}
void Xianxu(BitTree T)
{if (T){cout << T->data;Xianxu(T->lchild);Xianxu(T->rchild);}
}
void Houxu(BitTree T)
{if (T){Houxu(T->lchild);Houxu(T->rchild);cout << T->data;}
}
void printmenu()
{cout << "欢迎使用二叉树遍历及相关应用工具\n";cout << "请输入功能选项（1-3）:\n";cout << "\t1.创建二叉树\n";cout << "\t2.遍历二叉树\n";cout << "\t3.打印二叉树深度\n";cout << "\t4.打印二叉树叶子个数\n";cout << "\t5.打印二叉树第n层结点个数\n";cout << "\t0.退出\n";
}
int TreeDepth(BitTree T)
{if (T == NULL)return 0;elsereturn (TreeDepth(T->lchild) > TreeDepth(T->rchild) ? TreeDepth(T->lchild) : TreeDepth(T->rchild)) + 1;   //选择左孩子和右孩子中较大的深度，然后加上一个根结点
}
int LeafCount(BitTree T)
{if (T == NULL)return 0;else{if (T->lchild == NULL && T->rchild == NULL)   //如果递归到叶子，计数+1return 1;elsereturn LeafCount(T->lchild) + LeafCount(T->rchild);   //递归到叶子}
}
int NodeCount(BitTree T,int n)
{if (T == NULL)return 0;if (n == 1)  //如果到第n层，返回1return 1;return NodeCount(T->lchild, n - 1) + NodeCount(T->rchild, n - 1); //递归到第n层}int main()
{BitTree T = NULL;int choose;int method;choose = -1;while (choose != 0) {printmenu();cin >> choose;switch (choose) {case 1:cout << "创建你的二叉树吧，用#表示空指针:\n";T = creatTree();cout << "二叉树创建成功\n";break;case 2: {method = -1;while (method != 0){cout << "\t1.先序遍历\n";cout << "\t2.中序遍历\n";cout << "\t3.后序遍历\n";cout << "\t0.返回上一级\n";cout << "请输入功能选项（0-3）";cin >> method;switch (method){case 1:Xianxu(T); break;case 2:Zhongxu(T); break;case 3:Houxu(T); break;case 0:method = 0; break;}}printmenu();break;}case 3:cout << "该二叉树的深度是:" << TreeDepth(T)<<"\n"; break;case 4:cout << "该二叉树的叶子数是:" << LeafCount(T)<<"\n"; break;case 5:int n;cout << "请输入你要查询的层数:";cin >> n;cout << "该层共有" << NodeCount(T, n) << "个结点\n";break;case 0:cout << "感谢使用，欢迎多提宝贵意见！\n" << endl;return 0;}}}