25、数据结构/二叉树相关练习20240207

一、二叉树相关练习

请编程实现二叉树的操作

1.二叉树的创建

2.二叉树的先序遍历

3.二叉树的中序遍历

4.二叉树的后序遍历

5.二叉树各个节点度的个数

6.二叉树的深度

代码：

#include<stdlib.h>
#include<string.h>
#include<stdio.h>
typedef struct node//定义二叉树节点结构体
{int data;struct node *left;struct node *right;
}*binary;
binary create_node()//创建节点并初始化
{binary s=(binary)malloc(sizeof(struct node));if(NULL==s)return NULL;s->data=0;s->left=NULL;s->right=NULL;return s;
}
binary binary_tree()
{int element;printf("please enter element(end==0):");scanf("%d",&element);if(0==element)return NULL;binary tree=create_node();tree->data=element;tree->left=binary_tree();tree->right=binary_tree();return tree;
}
void first_output(binary tree)
{if(tree==NULL)return;printf("%d ",tree->data);first_output(tree->left);first_output(tree->right);
}
void mid_output(binary tree)
{if(NULL==tree)return;mid_output(tree->left);printf("%d ",tree->data);mid_output(tree->right);
}
void last_output(binary tree)
{if(NULL==tree)return;last_output(tree->left);last_output(tree->right);printf("%d ",tree->data);
}
void limit_tree(binary tree,int *n0,int *n1,int *n2)
{if(NULL==tree)return;if(tree->left&&tree->right)++*n2;else if(!tree->left && !tree->right)++*n0;else++*n1;limit_tree(tree->left,n0,n1,n2);limit_tree(tree->right,n0,n1,n2);
}
int high_tree(binary tree)
{if(NULL==tree)return 0;int left=1+high_tree(tree->left);int right=1+high_tree(tree->right);return left>right?left:right;
}
int main(int argc, const char *argv[])
{binary tree=binary_tree();//创建二叉树first_output(tree);//先序遍历puts("");mid_output(tree);//中序遍历puts("");last_output(tree);//后序遍历puts("");int n0=0,n1=0,n2=0;limit_tree(tree,&n0,&n1,&n2);//计算各个度的节点的个数；printf("n0=%d,n1=%d,n2=%d\n",n0,n1,n2);int high=high_tree(tree);//计算二叉树深度；printf("the high of the binary tree is:%d\n",high);return 0;
}

以下图二叉树为例运行结果：

二叉树图：

运行：