【递归调用在二叉树中的应用】前序遍历、中序遍历、后序遍历、求二叉树叶子结点及复制二叉树的C语言实现

简介: 【递归调用在二叉树中的应用】前序遍历、中序遍历、后序遍历、求二叉树叶子结点及复制二叉树的C语言实现

二叉树结点的结构体

包含指向左右子树的指针,和一个数据

1. typedef struct MyTreeNode
2. {
3.  struct MyTreeNode* left; //左孩子
4.  struct MyTreeNode* right; //右孩子
5.  int data;
6. }MyTreeNode;

创建一棵二叉树

创建一颗二叉树,其节点关系以及每个结点的数据如图所示

代码如下

1. {
2.     MyTreeNode t[15];
3. 
4.  for (i = 0; i < 15; i++)
5.  {
6.    memset(&t[i], 0, sizeof(MyTreeNode)); //没有孩子的应指向NULL
7.    t[i].data = i + 1;
8.  }
9. 
10.   //建立关系
11.   t[0].left = &t[1];
12.   t[0].right = &t[7];
13.   t[1].left = &t[2];
14.   t[2].left = &t[3];
15.   t[2].right = &t[4];
16.   t[4].left = &t[5];
17.   t[5].right = &t[6];
18.   t[7].right = &t[8];
19.   t[8].right = &t[14];
20.   t[8].left = &t[9];
21.   t[9].left = &t[10];
22.   t[9].right = &t[11];
23.   t[11].left = &t[12];
24.   t[11].right = &t[13];
25. }

二叉树的前序遍历

前序遍历是指,先访问根结点,然后访问左子树根节点,然后访问右子树根结点(根-左-右)。通过递归调用实现前序遍历算法的C语言代码如下:

1. void preorder_traversal(MyTreeNode* tree)
2. {
3.  if (tree == NULL)
4.  {
5.    //叶子结点指向NULL则返回
6.    return;
7.  }
8.  printf("%d ", tree->data);
9.  preorder_traversal(tree->left);
10.   preorder_traversal(tree->right);
11. }

前序遍历算法的测试结果:

中序遍历

先访问左子树根结点,然后访问根结点,最后访问右子树根结点(左-根-右)。通过递归调用实现中序遍历算法的C语言代码如下:

1. void inorder_traversal(MyTreeNode* tree)
2. {
3.  if (tree == NULL)
4.  {
5.    return;
6.  }
7.  inorder_traversal(tree->left);
8.  printf("%d ", tree->data);
9.  inorder_traversal(tree->right);
10. }

中序遍历算法的测试结果:

后序遍历

先访问左子树根结点,然后访问右子树根结点,最后访问根结点(左-右-根)。通过递归调用实现后序遍历算法的C语言代码如下:

1. void postorder_traversal(MyTreeNode* tree)
2. {
3.  if (tree == NULL)
4.  {
5.    return;
6.  }
7.  postorder_traversal(tree->left);
8.  postorder_traversal(tree->right);
9.  printf("%d ", tree->data);
10. }

后序遍历算法的测试结果:

三种遍历的关系

通过对比三种递归遍历算法的代码可以看到,三种遍历的区别就在于printf函数的位置不同,其他语句的顺序都是相同的,实际上,在遍历树的时候,不管是前序遍历、中序遍历、还是后序遍历,每个结点都会被访问三次,如下图所示,三种遍历的区别就在于获取节点数据的时机不同,前序遍历是在第一次访问就获取结点数据,中序遍历是在第二次访问的时候获取结点数据,后序遍历是在第三次访问的时候获取结点数据。

求二叉树的叶子结点数

代码如下

1. void get_leaf_num(MyTreeNode* tree, int* count) //指针做函数参数,间接修改实参的值
2. {
3.  if ((tree->left == NULL) && (tree->right == NULL))
4.  {
5.    (*count)++;
6.  }
7.  if (tree->left != NULL)
8.  {
9.    get_leaf_num(tree->left, count);
10.   }
11.   if (tree->right != NULL)
12.   {
13.     get_leaf_num(tree->right, count);
14.   }
15. }

求二叉树叶子结点算法测试:

复制一棵树

通过递归实现复制树,代码如下

1. MyTreeNode* copy_tree(MyTreeNode* tree)
2. {
3.  MyTreeNode* root = NULL;// *left = NULL, * right = NULL;
4.  root = (MyTreeNode*)malloc(sizeof(MyTreeNode));
5.  memset(root, 0, sizeof(MyTreeNode));
6.  root->data = tree->data;
7.  if (tree->left != NULL)
8.  {
9.    //如果有左子树则复制左子树
10.     root->left = copy_tree(tree->left);
11.   }
12.   else
13.   {
14.     //没有左子树则置为NULL
15.     root->left = NULL;
16.   }
17.   if (tree->right != NULL)
18.   {
19.     root->right = copy_tree(tree->right);
20.   }
21.   else
22.   {
23.     root->right = NULL;
24.   }
25.   return root;
26. }

复制树的时候,要通过malloc动态为复制好的树的结点分配内存,最后返回树的根结点地址。算法测试结果如下:


相关文章
|
4月前
|
通义灵码在考研C语言和数据结构中的应用实践 1-5
通义灵码在考研C语言和数据结构中的应用实践,体验通义灵码的强大思路。《趣学C语言和数据结构100例》精选了五个经典问题及其解决方案,包括求最大公约数和最小公倍数、统计字符类型、求特殊数列和、计算阶乘和双阶乘、以及求斐波那契数列的前20项和。通过这些实例,帮助读者掌握C语言的基本语法和常用算法,提升编程能力。
132 4
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
100 5
C语言中常见的字符串处理技巧,包括字符串的定义、初始化、输入输出、长度计算、比较、查找与替换、拼接、截取、转换、遍历及注意事项
本文深入探讨了C语言中常见的字符串处理技巧,包括字符串的定义、初始化、输入输出、长度计算、比较、查找与替换、拼接、截取、转换、遍历及注意事项,并通过案例分析展示了实际应用,旨在帮助读者提高编程效率和代码质量。
188 4
C 语言数组与指针的深度剖析与应用
在C语言中,数组与指针是核心概念,二者既独立又紧密相连。数组是在连续内存中存储相同类型数据的结构,而指针则存储内存地址,二者结合可在数据处理、函数传参等方面发挥巨大作用。掌握它们的特性和关系,对于优化程序性能、灵活处理数据结构至关重要。
C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出
本文探讨了C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出。文章还介绍了C语言在知名机器学习库中的作用,以及与Python等语言结合使用的案例,展望了其未来发展的挑战与机遇。
81 1
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
99 1
C语言在网络通信程序实现中的应用,介绍了网络通信的基本概念、C语言的特点及其在网络通信中的优势
本文探讨了C语言在网络通信程序实现中的应用,介绍了网络通信的基本概念、C语言的特点及其在网络通信中的优势。文章详细讲解了使用C语言实现网络通信程序的基本步骤,包括TCP和UDP通信程序的实现,并讨论了关键技术、优化方法及未来发展趋势,旨在帮助读者掌握C语言在网络通信中的应用技巧。
82 2
在C语言中指针数组和数组指针在动态内存分配中的应用
在C语言中,指针数组和数组指针均可用于动态内存分配。指针数组是数组的每个元素都是指针,可用于指向多个动态分配的内存块;数组指针则指向一个数组,可动态分配和管理大型数据结构。两者结合使用,灵活高效地管理内存。
C 语言中指针数组与数组指针的辨析与应用
在C语言中,指针数组和数组指针是两个容易混淆但用途不同的概念。指针数组是一个数组,其元素是指针类型;而数组指针是指向数组的指针。两者在声明、使用及内存布局上各有特点,正确理解它们有助于更高效地编程。
|
3月前
|
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
219 8

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等