这篇“纯C++二叉树相关操作实例代码分析”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“纯C++二叉树相关操作实例代码分析”文章吧。
二叉树的概念
二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分 。
二叉树的相关术语
①节点：包含一个数据元素及若干指向子树分支的信息 。
②节点的度：一个节点拥有子树的数目称为节点的度 。
③叶子节点：也称为终端节点，没有子树的节点或者度为零的节点 。
④分支节点：也称为非终端节点，度不为零的节点称为非终端节点 。
⑤树的度：树中所有节点的度的最大值 。
⑥节点的层次：从根节点开始，假设根节点为第1层，根节点的子节点为第2层，依此类推，如果某一个节点位于第L层，则其子节点位于第L+1层 。
⑦树的深度：也称为树的高度，树中所有节点的层次最大值称为树的深度 。
相关操作菜单
//菜单void menu(){ cout << "\t\t\t******************************************************************" << endl; cout << "\t\t\t**************** 1.输入-1 退出程序 *******************" << endl; cout << "\t\t\t**************** 2.输入1 初始化二叉树 *******************" << endl; cout << "\t\t\t**************** 3.输入2 对二叉树先序遍历 *******************" << endl; cout << "\t\t\t**************** 4.输入3 对二叉树中序遍历 *******************" << endl; cout << "\t\t\t**************** 5.输入4 对二叉树后序遍历 *******************" << endl; cout << "\t\t\t**************** 6.输入5 对二叉树层次遍历 *******************" << endl; cout << "\t\t\t**************** 7.输入6 二叉树深度 *******************" << endl; cout << "\t\t\t**************** 8.输入7 二叉树叶子结点数 *******************" << endl; cout << "\t\t\t**************** 9.输入8 二叉树的结点数 *******************" << endl; cout << "\t\t\t******************************************************************" << endl;}二叉树的构造
//构造二叉树typedef struct Binode{ //数据域 char data; //定义左孩子和右孩子 struct Binode*lchid, *rchid;}Binode, *StrBinode;创建二叉树
//先序遍历创建二叉树void creatBinode(StrBinode&T){ cin >> ch; if (ch == '#') { //如果输入是#的话就说明根结点就是叶子结点 //就没必要再去进行开辟一个二叉树空间 T = NULL; } else { T = new Binode; T->data = ch; creatBinode(T->lchid); creatBinode(T->rchid); }}先序遍历二叉树
//先序遍历二叉树void visitBinode(StrBinode&T){ if (T!=NULL) { cout << T->data << " "; visitBinode(T->lchid); visitBinode(T->rchid); } if(T==NULL) { cout << "#" << " "; }}中序遍历二叉树
//中序遍历二叉树void MidvisitBinode(StrBinode&T){ if (T != NULL) { visitBinode(T->lchid); cout << T->data << " "; visitBinode(T->rchid); } if (T == NULL) { cout << "#" << " "; }}后序遍历二叉树
//后序遍历二叉树void BackvisitBinode(StrBinode&T){ if (T != NULL) { visitBinode(T->lchid); visitBinode(T->rchid); cout << T->data << " "; } if (T == NULL) { cout << "#" << " "; }}层次遍历二叉树
//二叉树的层次遍历void Levelorder(StrBinode&HT){ StrBinode T; T = new Binode; //创建一个队列qu queue<StrBinode> qu; //将根结点的指针压入队列 qu.push(HT); //当队列不为空的时候就继续进行循环 while (!qu.empty()) { //让T里面存放队列中第一个元素的值 T = qu.front(); //C++自带的队列出队的话是删除值不返回值 qu.pop(); //访问出队元素的值 cout << T->data << " "; //当该节点左孩子不为空的时候就让左孩子入队 if (T->lchid != NULL) { qu.push(T->lchid); } //当该节点右孩子不为空的时候就让左孩子入队 if (T->rchid != NULL) { qu.push(T->rchid); } } }二叉树的深度
//二叉树的深度int deep(StrBinode&T){ if (T == NULL) { return 0; } else { int m = deep(T->lchid); int n = deep(T->rchid); if (m > n) { return (m + 1); } else { return (n + 1); } }}二叉树的叶子结点数
//求二叉树的叶子结点int leaf(StrBinode&T){ //如果是空树 if (T == NULL) { //返回0 return 0; } //如果是叶子结点 if (T->lchid == NULL && T->rchid == NULL) { //返回1 return 1; } return leaf(T->lchid) + leaf(T->rchid);}二叉树的结点数
//求二叉树的结点数int Nodecount(StrBinode&T){ //如果是根结点没有数据 if (T == NULL) { return 0; } else { return Nodecount(T->lchid) + Nodecount(T->rchid) + 1; }}整体代码
#include<iostream>#include<queue>using namespace std;char ch = 0; //构造二叉树typedef struct Binode{ //数据域 char data; //定义左孩子和右孩子 struct Binode*lchid, *rchid;}Binode, *StrBinode; //先序遍历创建二叉树void creatBinode(StrBinode&T){ cin >> ch; if (ch == '#') { //如果输入是#的话就说明根结点就是叶子结点 //就没必要再去进行开辟一个二叉树空间 T = NULL; } else { T = new Binode; T->data = ch; creatBinode(T->lchid); creatBinode(T->rchid); }} //先序遍历二叉树void visitBinode(StrBinode&T){ if (T!=NULL) { cout << T->data << " "; visitBinode(T->lchid); visitBinode(T->rchid); } if(T==NULL) { cout << "#" << " "; }} //中序遍历二叉树void MidvisitBinode(StrBinode&T){ if (T != NULL) { visitBinode(T->lchid); cout << T->data << " "; visitBinode(T->rchid); } if (T == NULL) { cout << "#" << " "; }} //后序遍历二叉树void BackvisitBinode(StrBinode&T){ if (T != NULL) { visitBinode(T->lchid); visitBinode(T->rchid); cout << T->data << " "; } if (T == NULL) { cout << "#" << " "; }} //二叉树的层次遍历void Levelorder(StrBinode&HT){ StrBinode T; T = new Binode; //创建一个队列qu queue<StrBinode> qu; //将根结点的指针压入队列 qu.push(HT); //当队列不为空的时候就继续进行循环 while (!qu.empty()) { //让T里面存放队列中第一个元素的值 T = qu.front(); //C++自带的队列出队的话是删除值不返回值 qu.pop(); //访问出队元素的值 cout << T->data << " "; //当该节点左孩子不为空的时候就让左孩子入队 if (T->lchid != NULL) { qu.push(T->lchid); } //当该节点右孩子不为空的时候就让左孩子入队 if (T->rchid != NULL) { qu.push(T->rchid); } } } //二叉树的深度int deep(StrBinode&T){ if (T == NULL) { return 0; } else { int m = deep(T->lchid); int n = deep(T->rchid); if (m > n) { return (m + 1); } else { return (n + 1); } }} //求二叉树的叶子结点int leaf(StrBinode&T){ //如果是空树 if (T == NULL) { //返回0 return 0; } //如果是叶子结点 if (T->lchid == NULL && T->rchid == NULL) { //返回1 return 1; } return leaf(T->lchid) + leaf(T->rchid);} //求二叉树的结点数int Nodecount(StrBinode&T){ //如果是根结点没有数据 if (T == NULL) { return 0; } else { return Nodecount(T->lchid) + Nodecount(T->rchid) + 1; }} //菜单void menu(){ cout << "\t\t\t******************************************************************" << endl; cout << "\t\t\t**************** 1.输入-1 退出程序 *******************" << endl; cout << "\t\t\t**************** 2.输入1 初始化二叉树 *******************" << endl; cout << "\t\t\t**************** 3.输入2 对二叉树先序遍历 *******************" << endl; cout << "\t\t\t**************** 4.输入3 对二叉树中序遍历 *******************" << endl; cout << "\t\t\t**************** 5.输入4 对二叉树后序遍历 *******************" << endl; cout << "\t\t\t**************** 6.输入5 对二叉树层次遍历 *******************" << endl; cout << "\t\t\t**************** 7.输入6 二叉树深度 *******************" << endl; cout << "\t\t\t**************** 8.输入7 二叉树叶子结点数 *******************" << endl; cout << "\t\t\t**************** 9.输入8 二叉树的结点数 *******************" << endl; cout << "\t\t\t******************************************************************" << endl;} int main(){ int n = 0; StrBinode T; menu(); while (cin >> n) { if (n < 0) { break; } switch (n) { case 1: //初始化二叉树 cout << "请输入值对二叉树进行初始化" << endl; creatBinode(T); cout << "初始化完成" << endl; break; case 2: //先序遍历 cout << "先序遍历的结果为" << endl; visitBinode(T); cout << "先序遍历结束" << endl; break; case 3: //中序遍历 cout << "中序遍历的结果为" << endl; MidvisitBinode(T); cout << "中序遍历结束" << endl; break; case 4: //后序遍历 cout << "后序遍历的结果为" << endl; BackvisitBinode(T); cout << "后序遍历结束" << endl; break; case 5: //层次遍历 cout << "层次遍历的结果为" << endl; Levelorder(T); cout << "层次遍历结束" << endl; break; case 6: cout << "二叉树的深度为："; cout << deep(T) << endl; break; case 7: cout << "二叉树的叶子结点数为："; cout << leaf(T) << endl; break; case 8: cout << "二叉树的结点数为；"; cout << Nodecount(T) << endl; break; default: cout << "您的输入有误，请重新输入" << endl; break; } } return 0;}结果展示
以上就是关于“纯C++二叉树相关操作实例代码分析”这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注编程网行业资讯频道。
