题目&Main函数
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<assert.h> //二叉树节点结构体 typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right;// }BTNode; //手动建造一个二叉树 //放入数据，左右置为NULL BTNode* BuyNode(int x) { BTNode* tmp = (BTNode*)malloc(sizeof(BTNode)); assert(tmp); if (tmp == NULL) { perror("malloc fail"); return; } tmp->data = x; tmp->left = NULL; tmp->right = NULL; return tmp; } //放入数据链接成树 BTNode* CreatBinaryTree() { BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6); //BTNode* node7 = BuyNode(1); node1->left = node2; node1->right = node4; node2->left = node3; node4->left = node5; node4->right = node6; return node1; }
int main() { BTNode* node = CreatBinaryTree(); //计算二叉树的节点个数 //方法1 int treesize = TreeSize(node); printf("%d\n", treesize); //方法2——遍历+全局变量/局部变量怎么办？传地址 TreeSize(node); printf("%d\n", size); size = 0; TreeSize(node); printf("%d\n", size); //计算二叉树的叶子节点个数 int leafsize = TreeLeafSize(node); printf("%d\n", leafsize); //计算二叉树的高度 int Heightsize = TreeHeight(node); printf("%d\n", Heightsize); //计算第k层的节点个数 //int K = TreeLevelK(node); //printf("%d\n", K); }
二叉树节点个数计算实现代码
//计算二叉树的节点个数 //方法1 int TreeSize(BTNode* tree) { if (tree == NULL) { return 0; } return TreeSize(tree->left) + TreeSize(tree->right) + 1; } //方法2 int size = 0; void TreeSize(BTNode* root) { if (root == NULL) { return ; } size++; TreeSize(root->left); TreeSize(root->right); }
方法1&递归
- 整体思路：根+左子树的节点个数+右子树的节点个数 （包含了只有一个节点1）
- 返回条件：空树返回0
- 方法1：递归
int TreeSize(BTNode* tree) { if (tree == NULL) { return 0; } return TreeSize(tree->left) + TreeSize(tree->right) + 1; }
方法2&遍历
- 放法2：遍历+(size++)
- 全局变量，不能使用静态局部变量。
- 全局变量是可以在主函数里面修改，作用域是全部函数，生命周期是程序结束
- 使用全局变量，在主函数每次调用前都必须重新设置为0
- 静态局部变量是只能在某个函数里面使用，作用域某指定函数，生命周期是程序结束
int size = 0; void TreeSize(BTNode* root) { if (root == NULL) { return ; } size++; TreeSize(root->left); TreeSize(root->right); }
Q1
我们使用size局部变量来累计计算节点的个数？？
结果：并没有累加上，因为每次调用函数，size都会重新定义
int TreeSize(BTNode* root) { int size = 0; if (root == NULL) { return 0; } ++size; TreeSize(root->left); TreeSize(root->right); return size; } int main() { BTNode* root = CreatBinaryTree(); int size=TreeSize(root); printf("TreeSize:%d\n", size); return 0; }
Q2
❗那我们把size变为静态的局部变量呢？当然不可以，因为静态局部变量生命周期是程序结束，意味着如果我们重复调用多次TreeSize这个函数，那么节点个数会成倍增长。
❗有人提议在main函数把size重新设置为0。当然也是不可以，因为size是静态局部变量，作用域只能在TreeSize函数里面
❗可以使用静态局部变量，但是需要修改的静态局部变量只能把size的地址&size传到main函数之后才可以修改。
❗所以最好就是使用全局变量，并且每次调用完之后都重新设置为0
int TreeSize(BTNode* root) { static int size = 0; if (root == NULL) { return 0; } ++size; TreeSize(root->left); TreeSize(root->right); return size; } int main() { BTNode* root = CreatBinaryTree(); int size=TreeSize(root); printf("TreeSize:%d\n", size); size=TreeSize(root); printf("TreeSize:%d\n", size); size=TreeSize(root); printf("TreeSize:%d\n", size); /*size = 0; TreeSize(root); printf("TreeSize:%d\n", size); size = 0; TreeSize(root); printf("TreeSize:%d\n", size); size = 0; TreeSize(root); printf("TreeSize:%d\n", size);*/❌ return 0; }
二叉树叶子节点个数计算实现代码
//计算二叉树的叶子节点个数 int TreeLeafSize(BTNode* root) { if (root == NULL) { return 0; } if (root->right == NULL && root->left == NULL) { return 1; } return TreeLeafSize(root->left)+TreeLeafSize(root->right); }
递归分析
- 整体思路：左树的叶子节点+右树的叶子节点
- 返回条件：若为叶子节点则返回1，若为空树NULL返回0
- 叶子节点的特质就是左右子树都为NULL
二叉树高度个数计算实现代码
计算二叉树的高度 //写法1 int TreeHeight(BTNode* root) { if (root == NULL) { return 0; } int leftHeight= TreeHeight(root->left); int rightHeight=TreeHeight(root->right); if (leftHeight > rightHeight) { return leftHeight + 1; } else//<= { return rightHeight + 1; } } //写法2 #include<math.h> int TreeHeight(BTNode* root) { if (root == NULL) { return 0; } return fmax(TreeHeight(root->left), TreeHeight(root->right))+1; } //写法3❌ int TreeHeight(BTNode* root) { if (root == NULL) { return 0; } return TreeHeight(root->left) > TreeHeight(root->right) ? TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1; }
递归分析
- 整体思路：根+（左右子树高的子树）
- 返回条件：空树NULL返回0
写法1&2
//写法1 int TreeHeight(BTNode* root) { if (root == NULL) { return 0; } int leftHeight= TreeHeight(root->left); int rightHeight=TreeHeight(root->right); if (leftHeight > rightHeight) { return leftHeight + 1; } else//<= { return rightHeight + 1; } } //写法2 #include<math.h> int TreeHeight(BTNode* root) { if (root == NULL) { return 0; } return fmax(TreeHeight(root->left), TreeHeight(root->right))+1; }
写法3
写法3在我们OJ题当中是会报错的❗因为调用的次数太多了 ❗
//写法3❌ int TreeHeight(BTNode* root) { if (root == NULL) { return 0; } return TreeHeight(root->left) > TreeHeight(root->right) ? TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1; }
- 第K层的节点个数&递归
- 二叉树查找第x个节点
- 不要不要不要对比代码，学会调试。
- 注意返回条件NULL 和 0 的区别。
- 大家可以自己动手画出代码的全部图解。画图理解❗
- ❗重点在于，左右子树不会同时调用，一般都是先调用完左数，在调用右树
🙂感谢大家的阅读，若有错误和不足，欢迎指正
