用C++编写程序,实现以下功能:(1)用链式存储结构,建立一颗二叉树,可自行选择采用先序、中序和后序中的某一种遍历方式。(2)对二叉树进行遍历,输出该二叉树的先序、中序和后序遍历结果。要求先序遍历和后序遍历用递归方式实现,中序遍历用非递归方式实现。(3)用递归方式,实现二叉树深度计算。(4)用递归方式,实现二叉树结点总数计算。
时间: 2023-06-09 20:02:04 浏览: 107
探讨:C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)
好的,这是一个关于C语言编程的问题。我可以帮您解答。以下是代码实现(注释见代码内部):
```c
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
//定义二叉树结点类型
typedef struct node{
int data;
struct node *lchild, *rchild;
}TreeNode, *Tree;
//创建二叉树
void CreateTree(Tree *T){
int data;
printf("请输入一些整数建立二叉树,-1为结束符:\n");
scanf("%d", &data);
if (data == -1){
*T = NULL;
}
else{
*T = (Tree)malloc(sizeof(TreeNode)); //给节点分配内存
(*T)->data = data;
CreateTree(&(*T)->lchild);
CreateTree(&(*T)->rchild);
}
}
//先序遍历(递归实现)
void PreOrderTraversal(Tree T){
if (T != NULL){
printf("%d ", T->data); //先访问根节点
PreOrderTraversal(T->lchild); //再遍历左子树
PreOrderTraversal(T->rchild);//再遍历右子树
}
}
//中序遍历(非递归实现)
void InOrderTraversal(Tree T){
int top = -1;
Tree stack[MAXSIZE];
Tree p = T;
while (p || top != -1){
while (p){ //左子树不为空则将该结点压入栈中,继续往左子树遍历
stack[++top] = p;
p = p->lchild;
}
if (top != -1){ //栈非空
p = stack[top--]; //出栈栈顶结点
printf("%d ", p->data); //访问该结点
p = p->rchild; //遍历右子树
}
}
}
//后序遍历(递归实现)
void PostOrderTraversal(Tree T){
if (T != NULL){
PostOrderTraversal(T->lchild); //先遍历左子树
PostOrderTraversal(T->rchild); //再遍历右子树
printf("%d ", T->data); //最后访问根节点
}
}
//计算二叉树的深度(递归实现)
int TreeDepth(Tree T){
if (T == NULL){
return 0;
}
else{
int ldep = TreeDepth(T->lchild);
int rdep = TreeDepth(T->rchild);
return (ldep > rdep ? ldep : rdep) + 1; //返回左右子树中深度较大的那个,并加上1(即当前结点的深度)
}
}
//计算二叉树的结点总数(递归实现)
int NodeCount(Tree T){
if (T == NULL){
return 0;
}
else{
return NodeCount(T->lchild) + NodeCount(T->rchild) + 1; //左右子树节点数之和加上当前结点
}
}
//主函数
int main(){
Tree T = NULL;
CreateTree(&T);
printf("先序遍历结果为:");
PreOrderTraversal(T);
printf("\n");
printf("中序遍历结果为:");
InOrderTraversal(T);
printf("\n");
printf("后序遍历结果为:");
PostOrderTraversal(T);
printf("\n");
printf("二叉树的深度为:%d\n", TreeDepth(T));
printf("二叉树的结点总数为:%d\n", NodeCount(T));
return 0;
}
```
您可以自行选择先序、中序、后序遍历方式,程序支持对应的实现。
阅读全文