首页 > 代码库 > 二叉树基本操作续一：二叉树建立、节点数统计
二叉树基本操作续一：二叉树建立、节点数统计
在上一篇：二叉树基本操作 中，我们描述了二叉树的递归遍历函数。在这里主要是给出这些函数的测试代码，为了测试更加方便，我们实现了三个新的函数：建立二叉树、统计二叉树叶子节点数量、统计二叉树总节点数量。（二叉树的定义用上篇文章中的定义）
二叉树建立：
1 tree_pointer create_bin_tree() 2 { 3 tree_pointer node; 4 int x; 5 scanf("%d", &x); 6 if (x == 0) { 7 node = NULL; 8 }else { 9 node = (tree_pointer) malloc (sizeof(struct node));10 node->data =http://www.mamicode.com/ x;11 printf("Enter %d left_child: ", node->data);12 node->left_child = create_bin_tree();13 printf("Enter %d right_child: ", node->data);14 node->right_child = create_bin_tree();15 }16 17 return node;18 }
从上篇的定义中我们知道二叉树节点里面存储的是整数，create函数为了便于处理，约定存储的数据不能为0，输入0时，表示这个节点为空。
仔细观察这个函数，就会发现这个函数和前序递归遍历函数很相像，最大的区别就是把遍历函数中的printf操作替换成了：当输入一个合法的需要插入的节点值时，就分配新的节点存储这个值，然后再分别用当前节点的左右儿子作为参数进行递归调用。
统计叶子节点数和总的节点数：
1 //注意这两个函数的返回值类型不是void，而是int 2 3 //统计叶子节点数量 4 int leaf_num(tree_pointer ptr) 5 { 6 if (ptr) { //当前节点不为空 7 if (!ptr->left_child && !ptr->right_child) { 8 //如果当前节点左右儿子都是空，则这个节点为叶子，返回 1 9 //如果当前节点为root，说明这颗二叉树只有一个根节点，叶子节点自然为110 return 1;11 } else {12 //否则，递归调用左右儿子，把返回值相加，即得到总叶子节点数量13 return leaf_num(ptr->left_child) + leaf_num(ptr->right_child);14 }15 }16 return 0;17 }18 19 //统计全部节点数量20 int node_num(tree_pointer ptr)21 {22 if (ptr) { //当前节点不为空23 //节点数+1 ，再加上递归调用左右儿子返回的节点数，即得到总节点数量24 return 1 + node_num(ptr->left_child) + node_num(ptr->right_child);25 }26 return 0;27 }
如果对递归概念不是很熟悉的话，看到这两个函数会稍微有一点糊涂。但是仔细观察一下，会发现这两个函数其实也是和之前的create函数类似的：同样都是是前序遍历的一个变种。
在叶子节点统计函数中：preorder中的printf函数现在变成了一个if判断，如果该节点左右儿子都为空，即当前节点为叶子节点，就返回 1，但如果存在左儿子或者右儿子的话，就说明当前节点不是叶子，就进入else流程，递归统计左右儿子，把统计到的数量相加，就得到叶子节点数。换种说法就是：对一颗二叉树进行前序遍历，每遇到一个节点就判断当前节点是否是叶子节点，是的话就返回 1，不是的话继续遍历，代码13行，就把这些递归遍历中返回的 1 相加在了一起，最后得到的就是叶子节点数量。(其实回顾上篇中描述的遍历函数的执行过程可以发现：在遍历函数中也可以在一个是否是叶子节点的if判断，如果是，就输出，然后直接return。因为如果节点是叶子节点，它的左右儿子都为空，所以无论什么遍历，以这个叶子节点为根节点的二叉树（回顾二叉树定义），遍历输出都一样。直接返回从系统层面看，少了两次函数调用，即少了两次入栈出栈和if判断)。
在总节点统计函数中：就是把前序遍历的三个步骤，printf ，preorder（ptr->lc）,preorder(ptr->rc)，的返回值直接相加。（有printf说明当前节点不为空，所以前序遍历中的printf在node_num函数中就变成了 +1）。
正如上一篇中说的：二叉树是一个递归定义的数据结构，所以它的大部分操作都非常适合用递归方式实现，而这些操作中最重要的就是三种递归遍历方式，其他很多操作都可以基于这三种递归遍历操作变形。
这些函数的完成测试代码如下：
（注意：代码中iter_开头的遍历函数，是三种遍历函数的迭代函数，本文中并没有给出实现,下篇文章中单独给出函数实现）
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 #define MAXSIZE 100 5 6 typedef struct node *tree_pointer; 7 typedef struct node { 8 int data; 9 tree_pointer left_child, right_child; 10 }; 11 12 tree_pointer create_bin_tree(); 13 void preorder(tree_pointer ptr); 14 void iter_preorder(tree_pointer ptr); 15 void inorder(tree_pointer ptr); 16 void iter_inorder(tree_pointer ptr); 17 void postorder(tree_pointer ptr); 18 void iter_postorder(tree_pointer ptr); 19 int leaf_num(tree_pointer ptr); 20 void show_tree(tree_pointer ptr); 21 int node_num(tree_pointer ptr); 22 23 int main(void) 24 { 25 tree_pointer root = NULL; 26 int choice = 0; 27 do { 28 printf("\n"); 29 printf(" BinaryTree \n"); 30 printf(" *******************\n"); 31 printf(" * *\n"); 32 printf(" * Main Menu *\n"); 33 printf(" * 1. create: *\n"); 34 printf(" * 2. preorder/iter_preorder: *\n"); 35 printf(" * 3. inorder/iter_inorder: *\n"); 36 printf(" * 4. postorder/iter_postorder: *\n"); 37 printf(" * 5. leaf_num: *\n"); 38 printf(" * 6. show_tree: *\n"); 39 printf(" * 7. node_num: *\n"); 40 printf(" * 8. quit!!! *\n"); 41 printf(" *******************\n"); 42 printf(" Enter your choice (1-8): "); 43 scanf("%d", &choice); 44 45 switch (choice) { 46 case 1: 47 printf("Begin create: enter root: \n"); 48 root = create_bin_tree(); 49 printf("Finished!!!\n"); 50 break; 51 case 2: 52 printf("\n preorder: \n"); 53 preorder(root); 54 printf("\n iter_preorder: \n"); 55 iter_preorder(root); 56 break; 57 case 3: 58 printf("\n inorder: \n"); 59 inorder(root); 60 printf("\n iter_inorder: \n"); 61 iter_inorder(root); 62 break; 63 case 4: 64 printf("\n postorder: \n"); 65 postorder(root); 66 printf("\n iter_postorder: \n"); 67 iter_postorder(root); 68 break; 69 case 5: 70 printf("\n leaf_num: \n"); 71 printf(" %d\n", leaf_num(root)); 72 break; 73 case 6: 74 printf("\n show_tree: \n"); 75 show_tree(root); 76 break; 77 case 7: 78 printf("\n node_num: \n %d\n", node_num(root)); 79 break; 80 case 8: 81 printf("\n quit.\n"); 82 exit(0); 83 break; 84 default: 85 break; 86 } 87 }while (choice <= 8); 88 89 return 0; 90 } 91 92 tree_pointer create_bin_tree() 93 { 94 tree_pointer node; 95 int x; 96 scanf("%d", &x); 97 if (x == 0) { 98 node = NULL; 99 }else {100 node = (tree_pointer) malloc (sizeof(struct node));101 node->data =http://www.mamicode.com/ x;102 printf("Enter %d left_child: ", node->data);103 node->left_child = create_bin_tree();104 printf("Enter %d right_child: ", node->data);105 node->right_child = create_bin_tree();106 }107 108 return node;109 }110 111 void preorder(tree_pointer ptr)112 {113 if (ptr) {114 printf("\t%d", ptr->data);115 preorder(ptr->left_child);116 preorder(ptr->right_child);117 }118 }119 void iter_preorder(tree_pointer ptr)120 {121 }122 123 void inorder(tree_pointer ptr)124 {125 if (ptr) {126 inorder(ptr->left_child);127 printf("\t%d", ptr->data);128 inorder(ptr->right_child);129 }130 }131 void iter_inorder(tree_pointer ptr)132 {133 134 }135 136 void postorder(tree_pointer ptr)137 {138 if (ptr) {139 postorder(ptr->left_child);140 postorder(ptr->right_child);141 printf("\t%d", ptr->data);142 }143 }144 void iter_postorder(tree_pointer ptr)145 {}146 147 int leaf_num(tree_pointer ptr)148 {149 if (ptr) {150 if (!ptr->left_child && !ptr->right_child) {151 return 1;152 } else {153 return leaf_num(ptr->left_child) + leaf_num(ptr->right_child);154 }155 }156 return 0;157 }158 159 void show_tree(tree_pointer ptr)160 {161 }162 163 int node_num(tree_pointer ptr)164 {165 if (ptr) {166 return 1 + node_num(ptr->left_child) + node_num(ptr->right_child);167 }168 return 0;169 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。