【算法与数据结构】二叉树（前中后）序遍历1:https://developer.aliyun.com/article/1474432
🌠后序遍历
后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
后序遍历是先遍历一个结点的左右子树,最后再访问这个结点。
void PostOrder(BTNode* root) { if (root == NULL) { printf("N "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->val); }
后序运行图：
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
🌠二叉树节点个数
这里分别实现前序、中序和后序遍历方式统计二叉树节点个数:
前序遍历:
int PreOrderCount(BTNode* root) { if(root == NULL) return 0; count++; PreOrderCount(root->left); PreOrderCount(root->right); return count; } int TreeSize(BTNode* root) { if(root == NULL) return 0; count = 0; PreOrderCount(root); return count; }
中序遍历:
inint InOrderCount(BTNode* root) { if(root == NULL) return 0; InOrderCount(root->left); count++; InOrderCount(root->right); return count; } int TreeSize(BTNode* root) { if(root == NULL) return 0; count = 0; InOrderCount(root); return count; }
后序遍历:
int PostOrderCount(BTNode* root) { if(root == NULL) return 0; PostOrderCount(root->left); PostOrderCount(root->right); count++; return count; } int TreeSize(BTNode* root) { if(root == NULL) return 0; count = 0; PostOrderCount(root); return count; }
三种遍历方式都是通过递归遍历每个节点,并在遍历每个节点时将统计变量count加1,最终count的值即为树的节点总数。
🌉二叉树节点个数注意点
注意当我们TreeSize函数使用了static变量size来统计节点个数,static变量的值会在函数调用之间保留,所以第二次调用TreeSize时,size的值会继续增加,导致统计结果叠加。
int TreeSize(BTNode* root) { static int size = 0; if (root == NULL) return 0; else ++size; TreeSize(root->left); TreeSize(root->right); return size; } int main() { printf("TreeSize : %d\n", TreeSize(root)); printf("TreeSize : %d\n", TreeSize(root)); }
代码运行：
改进
为了解决使用static变量导致的结果叠加问题，可以考虑使用以下方法:
- 每次调用TreeSize前重置size为0:
int TreeSize(BTNode* root) { static int size = 0; size = 0; // reset size if (root == NULL) return 0; else ++size; TreeSize(root->left); TreeSize(root->right); return size; }
- 不使用static变量,直接返回递归调用的结果:
int TreeSize(BTNode* root) { if (root == NULL) return 0; else return 1 + TreeSize(root->left) + TreeSize(root->right); } int
如果当前节点为NULL,直接返回0否则，返回:当前节点本身为1，加上左子树的节点数(TreeSize(root->left)返回值)，加上右子树的节点数(TreeSize(root->right)返回值)
- 将size定义为函数参数,每次递归传递:
intint TreeSize(BTNode* root, int* size) { if (root == NULL) return 0; *size += 1; TreeSize(root->left, size); TreeSize(root->right, size); return *size; } int main() { // 调用 int size = 0; TreeSize(root, &size); }
