编写一个程序，实现二叉树的先序遍历，中序遍历，后序遍历的各种递归和非递归算法，以及层次遍历的算法

Python023

编写一个程序，实现二叉树的先序遍历，中序遍历，后序遍历的各种递归和非递归算法，以及层次遍历的算法,第1张

文件 main.cpp 代码如下： #include<malloc.h>// malloc()等 #include<stdio.h>// 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等 #include<stdlib.h>// atoi()，exit() #include<math.h>// 数学函数头文件，包括floor()，ceil()，abs()等#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样typedef struct BiTNode { int data// 结点的值BiTNode *lchild,*rchild// 左右孩子指针 }BiTNode,*BiTreeint Nil=0// 设整型以0为空void visit(int e) { printf("%d ",e)// 以整型格式输出 } void InitBiTree(BiTree &T) { // 操作结果：构造空二叉树T T=NULL} void CreateBiTree(BiTree &T) { // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)， // 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改 int number scanf("%d",&number)// 输入结点的值 if(number==Nil) // 结点的值为空 T=NULL else // 结点的值不为空 { T=(BiTree)malloc(sizeof(BiTNode))// 生成根结点 if(!T) exit(OVERFLOW)T->data=number// 将值赋给T所指结点 CreateBiTree(T->lchild)// 递归构造左子树 CreateBiTree(T->rchild)// 递归构造右子树 } } void DestroyBiTree(BiTree &T) { // 初始条件：二叉树T存在。操作结果：销毁二叉树T if(T) // 非空树 { DestroyBiTree(T->lchild)// 递归销毁左子树，如无左子树，则不执行任何操作 DestroyBiTree(T->rchild)// 递归销毁右子树，如无右子树，则不执行任何操作 free(T)// 释放根结点 T=NULL// 空指针赋0 } } void PreOrderTraverse(BiTree T,void(*Visit)(int)) { // 初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法6.1 // 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次 if(T) // T不空 { Visit(T->data)// 先访问根结点 PreOrderTraverse(T->lchild,Visit)// 再先序遍历左子树 PreOrderTraverse(T->rchild,Visit)// 最后先序遍历右子树 } } void InOrderTraverse(BiTree T,void(*Visit)(int)) { // 初始条件：二叉树T存在，Visit是对结点操作的应用函数 // 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次 if(T) { InOrderTraverse(T->lchild,Visit)// 先中序遍历左子树 Visit(T->data)// 再访问根结点 InOrderTraverse(T->rchild,Visit)// 最后中序遍历右子树 } } void PostOrderTraverse(BiTree T,void(*Visit)(int)) { // 初始条件：二叉树T存在，Visit是对结点操作的应用函数 // 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次 if(T) // T不空 { PostOrderTraverse(T->lchild,Visit)// 先后序遍历左子树 PostOrderTraverse(T->rchild,Visit)// 再后序遍历右子树 Visit(T->data)// 最后访问根结点 } } void main() { BiTree T InitBiTree(T)// 初始化二叉树T printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0\n") CreateBiTree(T)// 建立二叉树T printf("先序递归遍历二叉树：\n") PreOrderTraverse(T,visit)// 先序递归遍历二叉树T printf("\n中序递归遍历二叉树：\n") InOrderTraverse(T,visit)// 中序递归遍历二叉树T printf("\n后序递归遍历二叉树：\n") PostOrderTraverse(T,visit)// 后序递归遍历二叉树T }这样可以么？

#include<iostream>using namespace stdtypedef struct BinaryTree{ char datastruct BinaryTree *lchild,*rchild}BinaryTree,*BiTreevoid CreateBiTree(BiTree &T){ char zif((z=getchar())==' ') T=NULLelse { T=(BinaryTree*)malloc(sizeof(BinaryTree)) T->data=z CreateBiTree(T->lchild) CreateBiTree(T->rchild)}}//先序遍历void preBiTree(BiTree T){ if(T!=NULL) { cout<<T->data preBiTree(T->lchild) preBiTree(T->rchild)}}//中序遍历void InBiTree(BiTree T){ if(T!=NULL) { InBiTree(T->lchild) cout<<T->data InBiTree(T->rchild)}}//后序遍历void PostBiTree(BiTree T){ if(T!=NULL) { PostBiTree(T->lchild) PostBiTree(T->rchild) cout<<T->data}}int Depth(BiTree T){ if(T==NULL) { return 0} else return 1+(Depth(T->lchild)>Depth(T->rchild)? Depth(T->lchild):Depth(T->rchild))}void main(){ BiTree Tcout<<"请输入相应二叉树:"<<endlCreateBiTree(T)cout<<"二叉树的先序遍历为:"<<endlpreBiTree(T)cout<<endlcout<<"二叉树的中序遍历为:"<<endlInBiTree(T)cout<<endlcout<<"二叉树的后序遍历为:"<<endlPostBiTree(T)cout<<endlcout<<"二叉树的深度为:"<<endlcout<<Depth(T)<<endl}