一.前言
我们需要先构建个二叉树，方便后续对函数的测试；
还有我们在实现二叉树的这些函数时，尽量少用遍历，这里用的比较多的就是递归和分治思想。
1. typedef int Tdatatype; 2. 3. typedef struct Tree 4. { 5. Tdatatype data; 6. struct Tree* left; 7. struct Tree* right; 8. }Tree; 9. 10. Tree* BuyTree(Tdatatype x) 11. { 12. Tree* node = (Tree*)malloc(sizeof(Tree)); 13. if (node == NULL) 14. { 15. perror("malloc fail"); 16. return NULL; 17. } 18. node->data = x; 19. node->left = NULL; 20. node->right = NULL; 21. 22. return node; 23. } 24. 25. Tree* CreateTree() //这里可以自由操控二叉树的构建 26. { 27. Tree* node1 = BuyTree(1); 28. Tree* node2 = BuyTree(2); 29. Tree* node3 = BuyTree(3); 30. Tree* node4 = BuyTree(4); 31. Tree* node5 = BuyTree(5); 32. Tree* node6 = BuyTree(6); 33. Tree* node7 = BuyTree(7); 34. node1->left = node2; 35. node1->right = node4; 36. node2->left = node3; 37. node2->right = node7; 38. node4->left = node5; 39. node4->right = node6; 40. 41. return node1; 42. 43. }
二.二叉树的节点数
二叉树的节点数=左子树的节点数+右子树的节点数；
1.如果root==NULL，则返回0；
2.否则递归调用它的左子树和右子树；
3.然后+1；
详细请看递归调用图：
1. int TreeSize(Tree* root) 2. { 3. return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; 4. }
二.二叉树的深度
还是利用分治的思想；
1.分别算出左子树和右子树的深度；
2.然后比较二者的大小，大的返回；
3.不要忘了+1,因为根节点也算是一个深度。
1. int TreeHeight(Tree* root) 2. { 3. if (root == NULL) //为空则返回0 4. return 0; 5. int left = TreeHeight(root->left); //要用left记录下其返回值，防止多次重复调用，right同 6. int right = TreeHeight(root->right); 7. 8. return left > right ? left + 1 : right + 1; 9. }
三.二叉树第k层的节点数
二叉树第k层的节点数=左子树的第k-1层的节点数+右子树第k-1层的节点数。
因为二叉树没有第0层，是从第一层开始的，所以k==1时，返回1。
1. int TreeLevel(Tree* root, int k) 2. { 3. if (root == NULL) //为空则返回0 4. return 0; 5. if (k == 1) 6. return 1; 7. 8. int left = TreeLevel(root->left, k - 1); //左子树第k-1层节点数 9. int right = TreeLevel(root->right, k - 1); //右子树第k-1层节点数 10. 11. return left + right; 12. 13. }
四.二叉树的遍历
1.前序遍历
前序遍历：
1.先访问根节点；
2.然后访问左节点；
3.最后访问右节点；
4.如果节点为空，则结束此次递归调用。
1. void PreOrder(Tree* root) 2. { 3. if (root == NULL) 4. return; 5. printf("%d ", root->data); 6. PreOrder(root->left); //访问左节点 7. PreOrder(root->right); //访问右节点 8. }
2.中序遍历
中序遍历：
1.先访问左节点；
2.然后访问根节点；
3.最后访问右节点；
4.如果节点为空，则结束此次递归调用。
1. void InOrder(Tree* root) 2. { 3. if (root == NULL) 4. return; 5. 6. InOrder(root->left); 7. printf("%d ", root->data); 8. InOrder(root->right); 9. }
3.后序遍历
后序遍历：
1.先访问左节点；
2.然后访问右节点；
3.最后访问根节点；
4.如果节点为空，则结束此次递归调用。
1. void PostOrder(Tree* root) 2. { 3. if (root == NULL) 4. return; 5. 6. PostOrder(root->left); 7. 8. PostOrder(root->right); 9. printf("%d ", root->data); 10. }
总结
通过以上代码我们发现：
1.假设前序，中序，后序分别为1，2，3；
2.是哪个序遍历，就按照那个顺序访问根节点，左节点永远在右节点前面；
3.递归也是按照这个顺序。
4.层序遍历
层序遍历就需要用到队列了。
1.先入一个节点进队列，此时队列不为空；
2。然后出一个节点，然后删除队列里的一个元素，如果左节点和右节点不为空的话，入它的左节点和右节点；
3.队列为空时跳出循环。
1. void LevelOrder(Tree* root) 2. { 3. //创建一个队列，并初始化 4. Queue q; 5. Queueinit(&q); 6. 7. if (root) 8. Queuepush(&q, root); 9. while (!Queueempty(&q)) 10. { 11. Tree* front = Queuefront(&q); //出一个数据 12. Queuepop(&q); 13. printf("%d ", front->data); 14. 15. if (front->left) 16. Queuepush(&q,front->left); //入它的左节点 17. if (front->right) 18. Queuepush(&q, front->right); //入它的右节点 19. } 20. 21. Queuedestroy(&q); //不要忘记销毁队列 22. }
五.二叉树叶节点的个数
叶节点就是没有子节点的节点，我们可以分别记录下当前节点的左节点和右节点，如果都为空，那么叶节点的个数+1。
1. int BinaryTreeLeafSize(Tree* root) 2. { 3. Tree* left = root->left; 4. Tree* right = root->right; 5. if (left == NULL && right == NULL) 6. { 7. return 1; 8. } 9. else 10. { 11. BinaryTreeLeafSize(root->left); 12. BinaryTreeLeafSize(root->right); 13. } 14. }
🐬🤖本篇文章到此就结束了，若有错误或是建议的话，欢迎小伙伴们指出；🕊️👻
😄😆希望小伙伴们能支持支持博主啊，你们的支持对我很重要哦；🥰🤩
😍😁谢谢你的阅读。😸😼
