数据结构实验：树和二叉树（附c++源码：实现树有关算法）

目录

一、实验目的

二、问题分析及数据结构设计

三、算法设计（伪代码表示）

1. 输入字符序列 创建二叉链表

2. 递归前序遍历

3. 递归中序遍历

4. 递归后序遍历

5. 非递归前序遍历

6. 非递归中序遍历

7. 非递归后序遍历

8. 层次遍历

9. 求二叉树的高度

10. 求二叉树的结点数

11. 求二叉树的叶子数

12. 交换左右子树

四、功能模块程序流程图

1. 功能选择菜单

2. 输入字符序列 创建二叉链表

3. 先序遍历-递归法

4. 中序遍历-递归法

5. 后序遍历-递归法

6. 先序遍历-非递归法

7. 中序遍历-非递归法

8. 后序遍历-非递归法

9. 层次遍历

11. 求二叉树的结点数

12. 求二叉树的叶子数

13. 交换二叉树每个结点的左子树和右子树

五、实验结果

1. 菜单功能

2. 建立二叉链表：

3. 先序遍历-递归算法：

4. 先序遍历-非递归算法：

5. 中序遍历-递归算法：

6. 中序遍历-非递归算法：

7. 后序遍历-递归算法：

8. 后序遍历-非递归算法：

9. 层次遍历：

10. 求二叉树的高度：

11. 求二叉树的结点数：

12. 求二叉树的叶子数：

13. 交换二叉树每个结点的左右子树：

六、算法分析

七、操作说明

八、源码

实验内容

1.编写函数，输入字符序列，建立二叉树的二叉链表。

2.编写函数，实现二叉树的中序递归遍历算法。(最好也能实现前缀和后缀遍历算法)

3.编写函数，实现二叉树的中序非递归遍历算法。

4.编写函数，借助队列实现二叉树的层次遍历算法。

5.编写函数，求二叉树的高度。

6.编写函数，求二叉树的结点个数。

7.编写函数，求二叉树的叶子个数。

8.编写函数，交换二叉树每个结点的左子树和右子树。

9.编写一个主函数，在主函数中设计一个简单的菜单，分别调试上述算法。

一、实验目的

掌握二叉树的基础知识，掌握二叉树的链表存储，遍历的递归与非递归算法，层次遍历、计算结点数、叶子数等二叉树有关算法的代码实现。理解递归算法的执行步骤，学会字符类型数据在输入时的处理，理解如何利用栈结构实现非递归算法。

二、问题分析及数据结构设计

  1. 问题分析：需要输入字符序列，建立二叉树的二叉链表。实现二叉树的中序递归及非递归遍历算法。借助队列实现二叉树的层次遍历算法。求二叉树的高度、结点个数、叶子个数。交换二叉树每个结点的左子树和右子树。需要我们思考如何用字符序列来表示一棵树，理解二叉树遍历的递归及非递归思想，判断是叶子还是结点，如有孩子的是结点，左右都无孩子的就是叶子。需要我们知道队列的相关知识，实现用队列的方法进行层次遍历。
  2. 数据结构设计：二叉链表结点类型-char字符型。树的定义：树-BiTNode，数据data-char字符型，左子树-指针BiTNode * lchild，右子树-指针BiTNode * rchild。队列的定义：队列-Quene，头指针front-int整型，尾指针rear-int整型。树的高度Hight-int整型，左子树的高度hL-int整型，右子树的高度hR-int整型。叶子数count-int整型，结点数count-int整型。用户输入选择要进行的算法序号num-int整型。

三、算法设计（伪代码表示）

1. 输入字符序列 创建二叉链表

Function createNode(BiTree & T)

Begin

输入字符

IF 字符 = ’#’

树为空

ELSE

分配BiTree大小的内存空间给T

T->data = e

递归createNode(T的左子树)

递归createNode(T的右子树)

End

2. 递归前序遍历

Function preOrder(BiTree root)

Begin

IF 树的根!=空

打印根的data

递归preOrder(根的左子树)

递归preOrder(根的右子树)

End

3. 递归中序遍历

Function midOrder(BiTree root)

Begin

IF 树的根!=空

递归midOrder(根的左子树)

打印根的data

递归midOrder(根的右子树)

End

4. 递归后序遍历

Function lastOrder(BiTree root)

Begin

IF 树的根!=空

递归preOrder(根的左子树)

递归preOrder(根的右子树)

打印根的data

End

5. 非递归前序遍历

Function lastOrderByStack(BiTree root)

Begin

IF 树的根==空

retutn

ELSE

定义栈stack

栈顶标记stackTop = -1

移动指针pMove = 树的根

WHILE 树根 != NULL || 栈顶 != -1

WHILE 树根 != NULL

打印当前结点pMove

栈顶标志++

pMove结点入栈

结点 = 结点->左子树

IF 栈顶 != -1

pMove = 栈顶

栈顶标志--

结点 = 结点->右子树

End

6. 非递归中序遍历

Function midOrderByStack(BiTree root)

Begin

IF 根 == NULL

return

建立栈stack

初始化结点指针pMove = 根root

WHILE 结点 != NULL || 栈顶 != -1

WHILE 结点 != NULL

栈顶标志++

结点入栈

结点 = 结点->左子树

IF 栈顶 != -1

结点 = 栈顶元素

栈顶标志--

打印结点

结点 = 结点->右子树

End

7. 非递归后序遍历

Function lastOrderByStack(BiTree root)

Begin

IF 根 == NULL

return

建立栈stack

初始化结点指针pMove = 根root

WHILE 结点 != NULL

栈顶标志++

结点入栈

结点 = 结点->左子树

WHILE 栈顶 != -1

结点 = 栈顶元素

栈顶标志--

IF 结点->左子树 == NULL || 结点->右子树 被访问过

打印结点

标记结点被访问

ELSE

栈顶标志++

栈顶 = 根结点

结点 = 结点->右子树

WHILE 结点 != NULL

栈顶标志++

结点入栈

结点 = 结点->左子树

End

8. 层次遍历

Function levelOrder(BiTree T)

Begin

定义队列q

初始化队列

IF 根!=NULL

结点入队列

WHILE 队!=NULL

节点出队

cout结点->data

IF 节点->左子树!=NULL

节点->左子树入队

IF 节点->右子树!=NULL

节点->右子树入队

End

9. 求二叉树的高度

Function int treeHeight(BiTree T)

Begin

IF 树根 == NULL

retutn 0

ELSE

左子树高度 = treeHeight(结点->左子树)

右子树高度 = treeHeight(结点->左右子树)

IF 左子树高度 > 右子树高度

return 左子树高度 + 1

ELSE

return 右子树高度 + 1

End

10. 求二叉树的结点数

Function int nodeCount(BiTree T)

Begin

IF 树根 == NULL

return 0

ELSE IF 结点->左子树 != NULL || 结点->右子树 != NULL

结点数++

nodeCount(结点->左子树)

nodeCount(结点->右子树)

return 结点数

End

11. 求二叉树的叶子数

Function int leafCount(BiTree T)

Begin

IF 树根 == NULL

return 0

ELSE IF 结点->左子树 == NULL && 结点->右子树 == NULL

结点数++

leafCount(结点->左子树)

leafCount(结点->右子树)

return 叶子数

End

12. 交换左右子树

Function swap(BiTree T)

Begin

IF 树根 != NULL

temp = 结点->左子树

结点->左子树 = 结点->右子树

结点->右子树 = temp

swap（结点->左子树）

swap（结点->右子树）

End

四、功能模块程序流程图

1. 功能选择菜单

   

说明：菜单功能首先提示用户输入数字。输入数字1，提示用户输入二叉树的每个结点值，以此建立二叉链表；输入数字2，提示输出的结果为“先序遍历二叉树-递归”；输入数字3，提示输出的结果为“先序遍历二叉树-非递归”；输入数字4，提示输出的结果为“中序遍历二叉树-递归”；输入数字5，提示输出的结果为“中序遍历二叉树-非递归”；输入数字6，提示输出的结果为“后序遍历二叉树-递归”；输入数字7，提示输出的结果为“后序遍历二叉树-非递归”；输入数字8，提示输出的结果为“层次遍历”；输入数字9，提示输出的结果为“二叉树的高度”；输入数字10，提示输出的结果为“二叉树的结点数”；输入数字11，提示输出的结果为“二叉树的叶子数”；输入数字12，完成交换二叉树的每个结点的左子树和右子树，提示用户“交换成功！可以通过选择遍历方法来查看交换后的遍历结果”；输入数字13，系统退出，提示用户“退出成功！”；

2. 输入字符序列 创建二叉链表

说明：该函数目的为建立二叉链表，提醒用户输入二叉树的每个结点的序列，如“AB#D##C##”，即可生成一个以链表为存储结构的二叉树，之后可以通过遍历方法来查看二叉树的构造结果。

3. 先序遍历-递归法

说明：该函数为实现二叉树的递归法的先序遍历功能，返回值为二叉树的前序遍历结果，传入根节点开始调用即可输出二叉树的先序遍历结果。

4. 中序遍历-递归法

说明：该函数为实现二叉树的递归法的中序遍历功能，返回值为二叉树的中序遍历结果，传入根节点开始调用即可输出二叉树的中序遍历结果。

5. 后序遍历-递归法

说明：该函数为实现二叉树的递归法的后序遍历功能，返回值为二叉树的后序遍历结果，传入根节点开始调用即可输出二叉树的后序遍历结果。

6. 先序遍历-非递归法

说明：该函数为实现二叉树的非递归法的先序遍历功能，返回值为二叉树的前序遍历结果，传入根节点开始调用即可输出二叉树的先序遍历结果，与递归法的先序遍历结果一样。

7. 中序遍历-非递归法

说明：该函数为实现二叉树的非递归法的中序遍历功能，返回值为二叉树的中序遍历结果，传入根节点开始调用即可输出二叉树的中序遍历结果，与递归法的中序遍历结果一样。

8. 后序遍历-非递归法

说明：该函数为实现二叉树的非递归法的后序遍历功能，返回值为二叉树的后序遍历结果，传入根节点开始调用即可输出二叉树的后序遍历结果，与递归法的后序遍历结果一样。

9. 层次遍历

说明：该函数为实现二叉树的层次遍历功能，返回值为二叉树的层次遍历结果，传入根节点开始调用即可输出二叉树的层次遍历结果。

10. 求二叉树的高度

说明：该函数为实现求二叉树的高度功能，返回值为二叉树的高度，传入根节点开始调用即可输出二叉树的高度。

11. 求二叉树的结点数

说明：该函数为实现求二叉树的结点数功能，返回值为二叉树的结点数，传入根节点开始调用即可输出二叉树的结点数。

12. 求二叉树的叶子数

说明：该函数为实现求二叉树的叶子数功能，返回值为二叉树的叶子数，传入根节点开始调用即可输出二叉树的叶子数。

13. 交换二叉树每个结点的左子树和右子树

说明：该函数为实现交换二叉树的每个结点的左子树与右子树的功能，传入已有的二叉链表的二叉树的根节点开始调用，即可交换二叉树的每个结点的左子树和右子树，交换成功后，用户通过调用遍历方法即可查看交换完成后的二叉树的遍历结果。

14. 退出

说明：该功能为退出系统功能，调用后即可退出系统，并得到提示“退出成功！”。

五、实验结果

1. 菜单功能

分析：该菜单通过序号1-13来实现不同的有关二叉树的功能，通过提示用户“请输入您要选择的计算”，来引导用户输入1-13的数字来获取想要的结果。

2. 建立二叉链表：

分析：输入数字1后进入该输入字符序列，建立二叉链表的功能。首先提示用户输入二叉树各结点的值，例如AB#D##C##，来建立二叉树，接着继续提示用户选择想要的计算。用户可以通过选择遍历算法来查看二叉树的建立结果。

3. 先序遍历-递归算法：

分析：输入数字2后进入该先序遍历-递归算法的功能，提示先序遍历二叉树-递归的结果为什么，接着提示用户继续选择想要实现的运算。该结果应该与先序遍历-非递归算法的输出结果一致。

4. 先序遍历-非递归算法：

分析：输入数字3后进入该先序遍历-非递归算法的功能，提示先序遍历二叉树-非递归的结果为什么，接着提示用户继续选择想要实现的运算。经结果检验，该结果确实与先序遍历-递归算法的输出结果一致。

5. 中序遍历-递归算法：

分析：输入数字4后进入该中序遍历-递归算法的功能，提示中序遍历二叉树-递归的结果为什么，接着提示用户继续选择想要实现的运算。该结果应该与中序遍历-非递归算法的输出结果一致。

6. 中序遍历-非递归算法：

分析：输入数字5后进入该中序遍历-非递归算法的功能，提示中序遍历二叉树-非递归的结果为什么，接着提示用户继续选择想要实现的运算。经结果检验，该结果确实与中序遍历-非递归算法的输出结果一致。

7. 后序遍历-递归算法：

分析：输入数字6后进入该后序遍历-递归算法的功能，提示后序遍历二叉树-递归的结果为什么，接着提示用户继续选择想要实现的运算。该结果应该与后序遍历-非递归算法的输出结果一致。

8. 后序遍历-非递归算法：

分析：输入数字7后进入该后序遍历-非递归算法的功能，提示后序遍历二叉树-非递归的结果为什么，接着提示用户继续选择想要实现的运算。经结果检验，该结果确实与后序遍历-递归算法的输出结果一致。

9. 层次遍历：

分析：输入数字8后进入该通过队列实现层次遍历的功能，提示层次遍历二叉树的结果为什么，接着提示用户继续选择想要实现的运算。

10. 求二叉树的高度：

分析：输入数字9后进入该通过队列实现求二叉树的高度的功能，提示二叉树的高度的结果为什么，接着提示用户继续选择想要实现的运算。

11. 求二叉树的结点数：

分析：输入数字10后进入该通过队列实现求二叉树的结点数的功能，提示二叉树的结点数的结果为什么，接着提示用户继续选择想要实现的运算。

12. 求二叉树的叶子数：

分析：输入数字11后进入该通过队列实现求二叉树的叶子数的功能，提示二叉树的叶子数的结果为什么，接着提示用户继续选择想要实现的运算。

13. 交换二叉树每个结点的左右子树：

分析：输入数字12后进入该交换二叉树的每个结点的左右子树的功能，提示用户交换成功，接着提示用户可以继续选择遍历算法来查看二叉树交换左右子树后的遍历结果。

分析：交换成功后，通过调用先序，中序，后序遍历的结果来看，遍历结果已经改变，结果正是原子树AB#D##C##将各结点左右子树交换后所得到的遍历结果。

14. 退出：

分析：输入数字13后进入该退出系统的功能，提示用户退出成功。退出成功后，不会再出现提示用户继续输入想要选择的运算。

六、算法分析

1. 遍历的递归算法：前序，中序，后序的算法都是通过递归调用传入左子树及右子树调用自身来实现，根据前、中、后来决定打印根结点的时机。

2. 遍历的非递归算法：核心是通过栈的运用来实现。前序思想是从根结点开始找到最左下角的结点，若结点不为空，则将这期间走过的结点入栈，将当前指针变为当前结点的左子树，重复上述操作，以此找到最左下角的结点。当左边的结点都找完则开始找右边，若栈顶不为空，则结点为栈顶元素，栈顶元素出栈，将当前指针变为当前结点的右子树，重复上述操作。

中序思想与前序思想大致相同，差别在于前序是在每次找最左结点时即打印根结点的元素，而中序是在找右结点时打印根结点的元素。

后序核心是要设立一个结点是否已经被访问过的标志。首先找到最左边的结点，不断将结点入栈，再将指针变为当前结点的左子树，重复上述操作。找到最左下角的结点后即开始回退，遇到根就判断根的左右是否被访问过或为空，若右子树已经被访问了或为空，则打印该右结点。若右结点存在且未被访问过，则重复找到最左边的结点的操作。继续进入循环。

3. 层次遍历：思想是把结点依次入队列再出列，输出该节点。判断该节点是否有孩子，若有，先将左孩子递归调用层次遍历的函数，重复入队出队、判断是否有孩子的操作。再将右孩子递归调用层次遍历的函数，重复入队出队、判断是否有孩子的操作。

4. 求二叉树的高度：思想是传入树的根结点，用该结点的左子树和右子树递归调用求高度的方法，从最下面开始依次向上输出左子树和右子树的高度，并返回左高与右高之间的较大者，将最后返回的结果再加1（即加上根结点的高度），即得到树的真正高度。

5. 求二叉树的结点数及叶子数：求结点数的思想是判断结点是否有左孩子或有右孩子，若满足其实一个，则令结点数++。求叶子数则是判断结点是否无左孩子且无右孩子，若满足则令叶子数++。

6. 交换左右子树：思想是通过临时变量temp来交换节点的左右子树，再利用结点的左右子树，递归调用该交换方法。

七、操作说明

编译后先出现一个菜单，1-13有文字信息描述二叉树的相关算法，提示用户输入1-13之间的数字。

输入数字1，提示用户输入二叉树的每个结点值，以此建立二叉链表；

输入数字2，提示输出的结果为“先序遍历二叉树-递归”；

输入数字3，提示输出的结果为“先序遍历二叉树-非递归”；

输入数字4，提示输出的结果为“中序遍历二叉树-递归”；

输入数字5，提示输出的结果为“中序遍历二叉树-非递归”；

输入数字6，提示输出的结果为“后序遍历二叉树-递归”；

输入数字7，提示输出的结果为“后序遍历二叉树-非递归”；

输入数字8，提示输出的结果为“层次遍历”；

输入数字9，提示输出的结果为“二叉树的高度”；

输入数字10，提示输出的结果为“二叉树的结点数”；

输入数字11，提示输出的结果为“二叉树的叶子数”；

输入数字12，完成交换二叉树的每个结点的左子树和右子树，提示用户“交换成功！可以通过选择遍历方法来查看交换后的遍历结果”；

输入数字13，系统退出，提示用户“退出成功！”；

八、源码

#include <iostream>
#include <string>
#include <stack>
using namespace std;#define ElemType char // 二叉链表结点类型#define MAX_SIZE 128// 定义树
typedef  struct  BiTNode {ElemType  data;struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;// 建立二叉链表
void createNode(BiTree& T)
{ElemType e;cin >> e;if (e == '#') {T = NULL;}else {T = (BiTree)malloc(sizeof(BiTNode));T->data = e;createNode(T->lchild);createNode(T->rchild);}
}// 打印节点中的数据
void printNodeData(BiTree Node) {cout << Node->data;
}// 递归法遍历// 1. 前序
void preOrder(BiTree root) {if (root != NULL) {printNodeData(root);    // 打印根preOrder(root->lchild); // 递归左子树preOrder(root->rchild); // 递归右子树}
}// 2. 中序
void midOrder(BiTree root) {if (root != NULL) {midOrder(root->lchild); // 递归左子树printNodeData(root);    // 打印根midOrder(root->rchild); // 递归右子树}
}// 3. 后序
void lastOrder(BiTree root) {if (root != NULL) {lastOrder(root->lchild); // 递归左子树lastOrder(root->rchild); // 递归右子树printNodeData(root);    // 打印根}
}// 非递归法// 1. 前序
void preOrderByStack(BiTree root) {if (root == NULL) {return;}// 定义栈BiTree stack[10]; // 存储每次打印节点的位置int stackTop = -1; // 栈顶标记BiTree pMove = root; // 移动指针代表当前节点 从root开始while (stackTop != -1 || pMove != NULL) { // 栈不为空或当前节点不为空// 从根开始找到最左边while (pMove) { // 如果当前节点不为空printNodeData(pMove); // 打印当前节点stackTop++;stack[stackTop] = pMove; // 走过的节点入栈pMove = pMove->lchild; // 当前指针变为左子节点 继续上述操作}// 上面的左边操作找完 找右边if (stackTop != -1) {pMove = stack[stackTop]; // 获取栈顶元素stackTop--; // 栈顶元素出栈pMove = pMove->rchild; // 当前指针变为右子节点 继续上述操作}}
}// 2. 中序
void midOrderByStack(BiTree root) {if (root == NULL) {return;}BiTree stack[10];int stackTop = -1;BiTree pMove = root;while (stackTop != -1 || pMove != NULL) {// 找到最左边while (pMove) {stackTop++;stack[stackTop] = pMove;pMove = pMove->lchild;}// 左边找完if (stackTop != -1) {pMove = stack[stackTop];stackTop--;printNodeData(pMove);pMove = pMove->rchild;}}
}// 3. 后序
void lastOrderByStack(BiTree root) {if (root == NULL) {return;}BiTree stack[10];int stackTop = -1;BiTree pMove = root;BiTree isVist = NULL; // 判断是否被访问过的标志// 找到最左边while (pMove) {stackTop++;stack[stackTop] = pMove;pMove = pMove->lchild;}// 回退 遇到根先判断根的左右是否被访问过或为空while (stackTop != -1) {pMove = stack[stackTop];stackTop--;// 已经走到最左边 所以不可能再有左边 只用判断右边// 右节点为空或已经被访问if (pMove->rchild == NULL || pMove->rchild == isVist) {printNodeData(pMove); // 打印当前节点isVist = pMove; // 改变标志位置}else { //右节点没被访问过stackTop++;stack[stackTop] = pMove; // 回退的当前节点的根节点pMove = pMove->rchild; // 找到根节点的右节点while (pMove) { // 重复找到最左边的操作stack[++stackTop] = pMove;pMove = pMove->lchild;}}}
}// 定义顺序队
typedef struct Quene {      int front;          // 队头指针int rear;           // 队尾指针BiTree data[MAX_SIZE]; // 存放队中元素
}SqQueue;// 初始化队列
void initQueue(SqQueue** q) {if (!((*q) = (SqQueue*)malloc(sizeof(SqQueue)))) {cout << ("内存分配失败！");exit(-1);}(*q)->front = (*q)->rear = -1; // 置 -1
}// 判断队列是否为空
bool emptyQueue(SqQueue* q) {// 首指针和尾指针相等 为空 返回真if (q->front == q->rear) {return true;}// 不为空 返回假return false;
}// 进队列
bool enQueue(SqQueue* q, BiTree node) {// 队列满了 插入失败 返回假，if (q->rear == MAX_SIZE - 1) {return false;}// 队列没满 插入成功 返回真q->rear++;               // 头指针加 1q->data[q->rear] = node; // 传值return true;
}// 出队列
bool deQueue(SqQueue* q, BiTree* node) {// 队列为空 取出失败 返回假if (q->front == q->rear) {return false;}// 队列不为空 取出成功 返回真q->front++;                // 尾指针+ 1*node = q->data[q->front]; // 取值return true;
}// 层次遍历
void levelOrder(BiTree T) {SqQueue* q;       // 定义队列initQueue(&q);    // 初始化队列if (T != NULL) { // 根节点指针进队列enQueue(q, T);}// 一层一层的把节点存入队列，当没有孩子节点时就不再循环while (!emptyQueue(q)) {      // 队不为空deQueue(q, &T);          // 出队时的节点cout << (T->data);   // 输出节点存储的值if (T->lchild != NULL) { // 有左孩子时将该节点进队列enQueue(q, T->lchild);}if (T->rchild != NULL) { // 有右孩子时将该节点进队列enQueue(q, T->rchild);}}
}// 求二叉树的高度
int treeHeight(BiTree T)
{int hL, hR, Height;if (T == NULL){  // 空树 高度为0return 0;}else{hL = treeHeight(T->lchild);  // 求左子树的高度hR = treeHeight(T->rchild);  // 求右子树的高度Height = ((hL > hR) ? hL : hR) + 1;  // 取高度较大者 加上根结点的高度return Height;}
}// 求二叉树的结点数
int nodeCount(BiTree T)
{static int count = 0; // 叶子数if (T == NULL) { // 空树return (0);}else if (T->lchild != NULL || T->rchild != NULL) { // 有左孩子或有右孩子count++;}nodeCount(T->lchild);nodeCount(T->rchild);return count;
}// 求二叉树的叶子数
int leafcount(BiTree T)
{static int count = 0; // 叶子数if (T == NULL) { // 空树return (0);}else if (T->lchild == NULL && T->rchild == NULL) { // 无左孩子且无右孩子count++;  }leafcount(T->lchild);leafcount(T->rchild);return count;
}// 交换左右子树
void swap(BiTree T) {BiTree temp = 0;if (T != NULL) {temp = T->lchild;T->lchild = T->rchild;T->rchild = temp;swap(T->lchild);swap(T->rchild);        }}int main() {BiTree T = 0;int num;cout << "1．  输入字符序列，建立二叉链表"         << endl;cout << "2．  先序遍历二叉树：递归算法"           << endl;cout << "3．  先序遍历二叉树：非递归算法"         << endl;cout << "4．  中序遍历二叉树：递归算法"           << endl;cout << "5．  中序遍历二叉树：非递归算法"         << endl;cout << "6．  后序遍历二叉树：递归算法"           << endl;cout << "7．  后序遍历二叉树：非递归算法"         << endl;cout << "8．  借助队列实现二叉树的层次遍历"       << endl;cout << "9．  求二叉树的高度"                     << endl;cout << "10． 求二叉树的结点数"                   << endl;cout << "11． 求二叉树的叶子数"                   << endl;cout << "12.  交换二叉树每个结点的左子树和右子树" << endl;cout << "13.  退出";cout << endl;while (true){cout << "请输入您要选择的计算: " << endl;cin >> num;switch (num){case 1: //调用递归建立二叉树算法{cout << "请输入二叉树各结点值, 例如：AB#D##C##" << endl;createNode(T);cout << endl;}break;case 2:{cout << "先序遍历二叉树-递归:";preOrder(T);cout << endl;}break;case 3:{cout << "先序遍历二叉树-非递归:";preOrderByStack(T);cout << endl;}break;case 4:{cout << "中序遍历二叉树-递归:";midOrder(T);cout << endl;}break;case 5:{cout << "中序遍历二叉树-非递归:";midOrderByStack(T);cout << endl;}break;case 6:{cout << "后序遍历二叉树-递归:";lastOrderByStack(T);cout << endl;}break;case 7:{cout << "后序遍历二叉树-非递归:";lastOrderByStack(T);cout << endl;}break;case 8:{cout << "层次遍历二叉树：";levelOrder(T);cout << endl;}break;case 9:{cout << "二叉树的高度为：";cout << treeHeight(T);cout << endl;}break;case 10:{cout << "二叉树的结点数为：";cout << nodeCount(T);cout << endl;}break;case 11:{cout << "二叉树的叶子数为：";cout << leafcount(T);cout << endl;}break;case 12:{cout << "交换二叉树每个结点的左子树和右子树:" << endl;swap(T);cout << "交换成功！您可继续输入选择查看交换后的遍历结果" << endl;}break;case 13:{cout << "退出成功！" << endl;system("pause");return 0;}break;default:{cout << "输入错误！请重新输入！" << endl;}}}system("pause");return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/393811.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【AI】关于AI和手机

【AI】关于AI和手机

2011 年至2015 年期间&#xff0c;全球智能手机出货量年增长率均超过两位数&#xff0c;显示出强劲的市场需 求和快速扩张趋势。然而&#xff0c;自2016 年起&#xff0c;全球智能手机用户数量趋于饱和&#xff0c;换机周期也逐 渐变长&#xff0c;市场进入存量替换阶段&#x…
阅读更多...
Qt/C++最新地图组件发布/历时半年重构/同时支持各种地图内核/包括百度高德腾讯天地图

Qt/C++最新地图组件发布/历时半年重构/同时支持各种地图内核/包括百度高德腾讯天地图

一、前言说明 最近花了半年时间&#xff0c;专门重构了整个地图组件&#xff0c;之前写的比较粗糙&#xff0c;有点为了完成功能而做的&#xff0c;没有考虑太多拓展性和易用性。这套地图自检这几年大量的实际项目和用户使用下来&#xff0c;反馈了不少很好的建议和意见&#…
阅读更多...
PXE 批量安装Linux系统

PXE 批量安装Linux系统

目录 一、 实验环境准备 1、一台红帽版本7的主机 2、开启主机图形 3、配置网络可用 4、关闭VMware dhcp 功能 ​编辑​编辑 5、配置好本地仓库&#xff0c;方便后续下载 二、配置kickstart自动安装脚本的工具 1、 安装图形化生成kickstart自动安装脚本的工具 2、启动图…
阅读更多...
2.MySQL库的操作

2.MySQL库的操作

创建数据库 创建数据库的代码&#xff1a; CREATE DATABASE [IF NOT EXISTS] db_name [create_specification [,create_specification] ...];​create_specification:[DEFAULT] CHARACTER SET charset_name[DEFAULT] COLLATE collation_name 说明&#xff1a; 大写的表示关键…
阅读更多...
【隐私保护】无证书签名方案（CLS）

【隐私保护】无证书签名方案（CLS）

一、CLS方案提出的背景 无证书签名方案&#xff08;Certificateless Signature Scheme, CLS&#xff09;是一种旨在结合公钥基础设施&#xff08;PKI&#xff09;和基于身份的加密&#xff08;IBE&#xff09;的优点&#xff0c;同时避免它们缺点的加密技术。 CLS方案的主要目标…
阅读更多...
【网络安全渗透测试零基础入门必知必会】之什么是文件包含漏洞分类（非常详细）零基础入门到精通，收藏这一篇就够了

【网络安全渗透测试零基础入门必知必会】之什么是文件包含漏洞分类（非常详细）零基础入门到精通，收藏这一篇就够了

一、前言 这是大白给粉丝盆友们整理的网络安全渗透测试入门阶段文件包含渗透与防御第1篇。 本文主要讲解什么是文件包含漏洞、本地文件包含漏洞 喜欢的朋友们&#xff0c;记得给大白点赞支持和收藏一下&#xff0c;关注我&#xff0c;学习黑客技术。 一、什么是文件包含漏洞…
阅读更多...
【HarmonyOS NEXT星河版开发学习】小型测试案例07-弹性布局小练习

【HarmonyOS NEXT星河版开发学习】小型测试案例07-弹性布局小练习

个人主页→VON 收录专栏→鸿蒙开发小型案例总结​​​​​ 基础语法部分会发布于github 和 gitee上面&#xff08;暂未发布&#xff09; 前言 在鸿蒙&#xff08;HarmonyOS&#xff09;开发中&#xff0c;Flex布局是一种非常有用的布局方式&#xff0c;它允许开发者创建灵活且响…
阅读更多...
Spring Boot实战：拦截器

Spring Boot实战：拦截器

一.拦截器快速入门 1.1了解拦截器 什么是拦截器&#xff1a; 概念 &#xff1a;拦截器是Spring框架提供的核⼼功能之⼀, 主要⽤来拦截⽤⼾的请求, 在指定⽅法前后, 根据业务需要执⾏预先设定的代码。 也就是说, 允许开发⼈员提前预定义⼀些逻辑, 在⽤⼾的请求响应前后执⾏. 也…
阅读更多...
ThinkPHP6与金仓数据库（Kingbase）集成：模型查询的解决方案

ThinkPHP6与金仓数据库（Kingbase）集成：模型查询的解决方案

摘要&#xff1a; ThinkPHP6是一款流行的PHP框架&#xff0c;支持多种数据库。然而&#xff0c;对于金仓数据库&#xff08;Kingbase&#xff09;这种相对小众的数据库系统&#xff0c;开发者在使用ThinkPHP6进行模型查询时可能会遇到一些兼容性问题。本文将提供一种解决方案&a…
阅读更多...
仿推特社区源码修复版，含pc端和H5端，可以封装成app

仿推特社区源码修复版，含pc端和H5端，可以封装成app

简介&#xff1a; 新鲜出炉的仿推特社区源码修复版&#xff0c;含pc端和H5端&#xff0c;可以封装成app。这玩意绝对可以算是精品代码了。 手机h5端可以封装成软件也不错的。 推特的风格还是不错的&#xff0c;不然世界首富马斯克也不会花费440亿美金收购它了。 阅览&#…
阅读更多...
nginx 405错误是什么意思

nginx 405错误是什么意思

405错误&#xff1a;方法不被允许 当Web服务器收到一个它不支持的HTTP请求方法时&#xff0c;就会返回405错误。 原因 405错误通常是由于客户端发出了不兼容或不支持的HTTP请求方法。例如&#xff0c;客户端可能请求一个只能通过GET方法访问的资源&#xff0c;但使用了POST方…
阅读更多...
图片转文字怎么操作？教你几招图片转文字小妙招

图片转文字怎么操作？教你几招图片转文字小妙招

在日常的工作学习中&#xff0c;我们每天可能会接触到大量的图片资料&#xff0c;无论是会议纪要、书籍扫描页、还是网络上的有用信息截图&#xff0c;如果能快速将这些图片中的文字提取出来&#xff0c;无疑将极大提升我们的工作效率。下面给大家分享几种能够将图片转换成文字…
阅读更多...
简单中间件模型

简单中间件模型

中间件是软件开发过程中架构的一个通用概念&#xff0c;其目的在于为运行的主程序提供一个供外部自定义拓展的能力。比如&#xff1a;wen服务的controller层中间件针对request请求处理的前后进行通用的扩展处理、redux中间件针对store数据获取前后的扩展处理。。。   本文简单…
阅读更多...
OrangePi AIpro学习3 —— vscode开发昇腾DVPP程序

OrangePi AIpro学习3 —— vscode开发昇腾DVPP程序

目录 一、VScode配置 1.1 下载和安装 1.2 安装和配置需要的插件 二、构建项目 2.1 项目架构 2.2 解决代码高亮显示 2.3 测试编译 2.4 总结出最简单的代码 2.5 vscode报错找不到头文件解决方法 三、代码简单讲解 3.1 初始化部分 3.2 拷贝数据到NPU显存中 3.3 准备裁…
阅读更多...
python-报数（赛氪OJ）

python-报数（赛氪OJ）

[题目描述] 有 n 人围成一圈&#xff0c;顺序排号。 从第 1 个人开始报数&#xff08;从 1 到 3 报数&#xff09;&#xff0c;凡是报到 3 的人退出圈子&#xff0c;问最后留下的是原来的第几号的那位。输入格式&#xff1a; 初始人数 n 。输出格式&#xff1a; 最后一人的初始…
阅读更多...
python游戏开发之五子棋游戏制作

python游戏开发之五子棋游戏制作

五子棋是一种源自中国的传统棋类游戏&#xff0c;起源可以追溯到古代。它是一种两人对弈的游戏&#xff0c;使用棋盘和棋子进行。棋盘通常是一个 1515 的网格&#xff0c;棋子分为黑白两色&#xff0c;双方轮流在棋盘上落子。游戏的目标是通过在棋盘上落子&#xff0c;使自己的…
阅读更多...
【深度学习】基于YOLOV5模型的图像识别-目标检测的性能指标详解与计算方法

【深度学习】基于YOLOV5模型的图像识别-目标检测的性能指标详解与计算方法

目标检测是计算机视觉中的重要任务&#xff0c;主要目的是在图像中识别并定位特定的物体。YOLO&#xff08;You Only Look Once&#xff09;系列模型作为目标检测领域的代表性方法之一&#xff0c;凭借其高效和准确的特点&#xff0c;广泛应用于实际场景中。本文通过详细介绍目…
阅读更多...
C++之移动语义与左值右值深入学习：从入门到精通！

C++之移动语义与左值右值深入学习：从入门到精通！

简介 本文详细阐述了 C 中关于移动语义、左值右值等技术的基本概念和常用技巧。 问题的产生 每一项技术的诞生都是为了解决某一个问题&#xff0c;移动语义、左值右值也是一样&#xff0c;因此我们先来看看问题产生的背景。 先来看一段代码&#xff1a; #include <iost…
阅读更多...
JavaEE: Thread类

JavaEE: Thread类

Thread的常见构造方法 Thread的常见属性 ID 是线程的唯一标识,不同线程不会重复名称是在使用各种调试工具时会用到的状态表示线程当前所处的情况优先级高的线程理论上来说更容易被调度到关于后台线程,需要记住:JVM会在一个进程的所有非后台线程结束后,才会结束运行是否存活,即r…
阅读更多...
社交及时通讯平台完整版源码，uniapp技术，可打包成app

社交及时通讯平台完整版源码，uniapp技术，可打包成app

源码简介&#xff1a; 全原生&#xff0c;从底层开始结构就完全不一样&#xff0c;mongodb的库&#xff0c;uniapp混编手端&#xff0c;二开难度要比视酷或者酷信容易很多。全开源&#xff0c;带开发文档。前端用的是uniapp技术&#xff0c;所以是多端合一&#xff0c;可以做h…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023