Question

C语言数据结构题

创建二叉树并求二叉树叶子结点个数与打印出叶子结点的值，拜托各位大神了！

Answer 1

基础定义

创建一颗树

先序遍历

构建的数函数的示例： AB#C### 构建的数为如下：    

如果需要PPT讲解，私信我

Answer 2

我这里有一个二叉树的各种操作的例子，你拿去改一改就行了。
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX_DEP ( 10 ) /* 二叉树深度 */
#define RAND_NUM ( 100 ) /* 最大随机数 */
typedef struct Tree *tree;
struct Tree {
int value;
tree left;
tree right;
};
static tree create_tree(int value);
static tree insert_tree(tree node, int value);
static tree delete_tree(tree node, int value);
static tree search_tree(tree node, int value);
static void update_tree(tree node, int old_value, int new_value);
static void free_tree(tree node);
static void pre_order_tree(tree node);
static void in_order_tree(tree node);
static void pos_order_tree(tree node);
int main(void) {
int i;
tree root = NULL;
tree node;
srand(time(NULL));
for ( i = 0; i < MAX_DEP; i++ ) {
root = insert_tree(root, rand() % RAND_NUM );
}
root = insert_tree(root, 300);
for ( i = 0; i < MAX_DEP; i++ ) {
root = insert_tree(root, rand() % RAND_NUM );
}
// node = root;
printf("先序遍历\n");
pre_order_tree(root);
printf("\n中序遍历\n");
in_order_tree(root);
printf("\n后序遍历\n");
pos_order_tree(root);
printf("\n");
node = search_tree(root, 40);
printf("查找节点: %d\n", node == NULL ? -1 : node->value);
printf("更新节点\n");
update_tree(root, 300, 200);
pos_order_tree(root);
printf("\n");
root = insert_tree(root, 20);
pos_order_tree(root);
printf("\n");
printf("删除节点\n");
root = delete_tree(root, 20);
pos_order_tree(root);
printf("\n");
free_tree(root);
return 0;
}
/*
* 创建二叉树节点
*/
static tree create_tree(int value) {
tree node;
node = (tree)malloc(sizeof(struct Tree));
node->value = value;
node->left = NULL;
node->right = NULL;
return node;
}
/*
* 将数据插入到二叉树的节点上
*/
static tree insert_tree(tree node, int value) {
if ( node == NULL ) {
return create_tree(value);
}
if ( node->value <= value ) {
node->right = insert_tree(node->right, value);
} else {
node->left = insert_tree(node->left, value);
}
return node;
}
/*
* 删除二叉树中指定的值。
* 如果该节点下面还有子节点也会一并删除。
*/
static tree delete_tree(tree node, int value) {
if ( node == NULL ) return NULL;
/*
* 如果这个值在跟节点的右边
*/
if ( node->value < value ) {
node->right = delete_tree(node->right, value);
}
/*
* 如果这个值在跟节点的左边
*/
else if ( node->value > value ) {
node->left = delete_tree(node->left, value);
}
/*
* 否则这个值只能在跟节点上或者树上没有这个值
*/
else {
printf("删除这个节点之后的所有节点: %d\n", node->value);
free_tree(node);
printf("------------\n");
node = NULL;
}
return node;
}
/*
* 查询特定值
*/
static tree search_tree(tree node, int value) {
if ( node == NULL ) return NULL;
if ( node->value == value ) return node;
if ( node->value <= value ) {
node = search_tree(node->right, value);
} else {
node = search_tree(node->left, value);
}
return node;
}
/*
* 更新树上特定值
*/
static void update_tree(tree node, int old_value, int new_value) {
node = search_tree(node, old_value);
node->value = new_value;
}
/*
* 程序的最后应该调用该函数，释放二叉树
* 目前能想到的释放方法只有后序遍历这种方式。
*/
static void free_tree(tree node) {
if ( node == NULL ) return;
free_tree( node->left );
free_tree( node->right );
printf("释放该节点: %d\n", node->value);
free(node);
}
/*
* 先序遍历
*/
static void pre_order_tree(tree node) {
if ( node == NULL ) return;
printf("%d ", node->value);
pre_order_tree(node->left);
pre_order_tree(node->right);
}
/*
* 中序遍历
*/
static void in_order_tree(tree node) {
if ( node == NULL ) return;
in_order_tree(node->left);
printf("%d ", node->value);
in_order_tree(node->right);
}
/*
* 后序遍历
*/
static void pos_order_tree(tree node) {
if ( node == NULL ) return;
pos_order_tree(node->left);
pos_order_tree(node->right);
printf("%d ", node->value);
}