2021-12-18

#include"stdio.h"

#include"stdlib.h"

#include"string.h"

#define _CRT_SECURE_NO_DEPRECATE

#define Max 20 //结点的最大个数

typedef struct node{

char data;

struct node *lchild, *rchild;

}BinTNode; //自定义二叉树的结点类型

typedef BinTNode *BinTree; //定义二叉树的指针

int NodeNum, leaf; //NodeNum 为结点数，leaf 为叶子数

// 基于先序遍历算法创建二叉树

//一要求输入先序序列，其中加入虚结点"#”以示空指针的位置

BinTree CreatBinTree(void)

{

BinTree T;

char ch;

if ((ch = getchar()) = '#')

return(NULL); //读入#, 返回空指针

else

{

T = (BinTNode *)malloc(sizeof(BinTNode)); //生成结点

T->data = ch;

T->lchild = CreatBinTree(); //构造左子树

T->rchild = CreatBinTree(); //构造右子树

return(T);

}

}

//———— —NLR先序遍历 :

void Preorder(BinTree T)

{

if (T){

printf("%c",T->data); //访问结点

Preorder(T->lchild); //先序遍历左子树

Preorder(T->rchild); //先序遍历右子树

}

}

// LNR中序遍历=

void Inorder(BinTree T)

{

if (T) {

Inorder(T->lchild);

printf("%c ", T->data);

Inorder(T->rchild);

}

}

// LRN后序遍历-

void Postorder(BinTree T) //中序遍历左子树

//访问结点

//中序遍历右子树

{

if (T) {

Postorder(T->lchild); //后序遍历左子树

Postorder(T->rchild); //后序遍历右子树

printf("%c", T->data);  //访问结点

}

}

//=======采用后序遍历求二叉树的深度、节点数及叶子数的递归算法=======

int TreeDepth(BinTree T)

{

int hl, hr, max;

if(T){

hl=TreeDepth(T->lchild); //求左深度

hr=TreeDepth(T->rchild); //求右深度

max=hl>hr?hl:hr; //取左右深度的最大值

NodeNum=NodeNum+1; //求结点数

if(hl==0&&hr == 0)leaf = leaf + 1; //若左右深度为 0,即为叶子。

return(max + 1);

}

else return(0);

}

// = 利用”先进先出"(FIFO)队列，按层次遍历二叉树

void Levelorder(BinTree T)

{

int front = 0, rear = 1;

BinTNode*cq[Max], *p; //定义结点的指针数组cq

cq[1] = T; //根入队

while (front != rear)

{

front = (front + 1) % NodeNum;

p = cq[front]; //出队

printf("%c", p->data); //出队，输出结点的值

if (p->lchild != NULL){

rear = (rear + 1) % NodeNum;

cq[rear] = p->lchild; //左子树入队

}

if (p->rchild != NULL) {

rear = (rear + 1) % NodeNum;

cq[rear] = p->rchild; //右子树入队

}

}

}

//一数叶子节点个数一

int countleaf(BinTree T)

{

int hl, hr;

if (T){

hl = countleaf(T->lchild);

hr = countleaf(T->rchild);

if (hl == 0 && hr == 0) //若左右深度为0, 即为叶子。

return(1);

else return hl + hr;

}

else return 0;

}

//=——=± 函 数:

int main()

{

BinTree root;

char i;

int depth;

printf("\n");

printf("Creat Bin_Tree; Input preorder:"); //输入完全二叉树的先序序列，

//用#代表虚结点，如ABD###CE##F##

root = CreatBinTree(); //创建二叉树，返回根结点

do{        //从菜单中选择遍历方式，输入序号。

printf("\t********** select ************\n");

printf("\t1: Preorder Traversal\n");

printf("\t2: lorder Traversal\n");

printf("\t3: Postorder traversal\n");

printf("\t4: PostTreeDepth, Node number, Leaf number\n");

printf("\t5: Level Depth\n"); //按层次遍历之前，先选铉4,求出该树的结 点数。

printf("\tO: Exit\n");

printf("\t*******************************\n");

fflush(stdin); //刷新标准输入缓冲区，把输入缓冲区里的东西丢弃

scanf_s ("%c", &i); //输入菜单序号(0 - 5)

switch (i - '0'){

case 1:

printf("Print Bin_tree Preorder:");

Preorder(root); //先序遍历

break;

case 2:

printf("Print Bin Tree Inorder:");

Inorder(root); //中序遍历

break;

case 3:

printf("Print Bin Tree Postorder:");

Postorder(root); //后序遍历

break;

case 4:

depth = TreeDepth(root); //求树的深度及叶子数

printf("BinTree Depth=%d BinTree Node number=%d", depth, NodeNum);

printf(" BinTree Leaf number=%d", countleaf(root));

break;

case 5: printf("LevePrint Bin_Tree");

Levelorder(root); //按层次遍历

break;

default: exit(1);

}

printf("\n");

} while (i!=0);

system("pause");

return (0);

}

数据结构实验关于二叉树的问题

C语言数据结构的问题还

关于图片提取文字就是一定要注意断行，对代码的审核，

函数未声明

原因一：是对函数在int函数后面未声明

出现必须是可改变的左值可能是对函数进行for循环判断时的等号的输入

要注意代码的准确性，先用笨办法进行检查，养成良好的输入习惯

作为一个初学者对基本的问题理解

————————————————

版权声明：本文为CSDN博主「B_planzp」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/B_planzp/article/details/121877955