• 王道书P149 T3(二叉树链式存储实现)


    1. /**
    2. * 用二叉树链式存储实现 王道P149 T3
    3. *
    4. * ①算法思想
    5. *
    6. * ②算法设计
    7. */
    8. //10、二叉树的非递归遍历---后序遍历
    9. //void PostOrderN(BiTree T){
    10. // BiTree stack[MaxSize],p = T;
    11. // int top = -1;
    12. // while(p || top != -1){
    13. // if(p){
    14. // stack[++top] = p;//压栈
    15. // p = p -> lchild;
    16. // }else{
    17. // p = stack[top];//注意这边不能出栈,因为栈顶的元素还没有访问过
    18. // p = p -> rchild;
    19. //Visit(p);如果Visit直接在这边写的话那么是不对的,因为并不能保证此时p节点是“叶子节点”,
    20. // }
    21. // }
    22. //}
    23. /**
    24. * 原因是p虽然是父节点的右孩子,但是他自己有可能也有左右孩子,如果有的话p就是“根节点”,那么要最后访问,而不是现在访问。
    25. * 那么如何解决这个问题呢?问题的关键就是要搞明白p这个节点到底有没有左右孩子。
    26. * 分析一下过程:以此树为例:1 2 99999 4 99999 99999 3 99999 99999
    27. * 1 入栈... 然后 2 入栈
    28. * 然后 p = p -> lchild;因为 p 没有左孩子,所以 p 为空,所以访问栈顶元素的位置,然后执行p = p -> rchild;
    29. * 现在 p 就指向 4 了,然后 4 入栈,然后执行p = p -> lchild; 因为 4 没有左孩子,所以 p 为空,
    30. * ①然后 p 指向栈顶元素的位置,也就是自己 4 ,
    31. * 然后p = p -> rchild;p又变成了空,那么 p 下一步就会执行 p = stack[top];
    32. * ②也就是 p 又指向了4!
    33. * 那么我们就会发现当 4 自己没有左孩子的时候,p 会指向 4;
    34. * 然而当 4 自己没有右孩子的时候,p 也会指向 4;
    35. * 当第二种情况发生时,说明 p 是叶子节点,那么就应该 Visit(p);
    36. * 那么现在要做的就是要区分这两种情况!
    37. * 这两种情况有一个不同点,情况一是没有左孩子导致 p 指向 4 的,而情况二是没有右孩子导致 p 指向 4 的,
    38. * 那么就可以自就此区分两种情况。
    39. * 那么我们就 int 一个 tag,用来标记,如果是因为没有左孩子,就标记为 1,如果是因为没有右孩子,就标记为 2;
    40. * 只有当 tag 为 2 的时候,才能说明这个 p 是没有左右孩子的,也就是“叶子节点”,那么就可以进行visit(p)。
    41. * 以下为正确代码:
    42. */
    43. void PostOrderN(BiTree T){
    44. BiTree stack[MaxSize],p = T;
    45. int top = -1;
    46. while(p || top != -1){
    47. if(p){
    48. stack[++top] = p;//压栈
    49. p -> tag = 1;
    50. p = p -> lchild;
    51. }else{
    52. p = stack[top];//注意这边不能出栈,因为栈顶的元素还没有访问过
    53. if(p -> tag == 1){
    54. p -> tag = 2;
    55. p = p -> rchild;
    56. }else{
    57. Visit(p);
    58. top--;
    59. p = NULL;//让p为空后才能继续取栈顶新元素进行下一步
    60. }
    61. }
    62. }
    63. }
    64. //非递归后序遍历的另一种写法:
    65. void PostOrderNR(BiTree T){
    66. BiTree stack[MaxSize],p = T;
    67. int top = -1,tag[MaxSize] = {0};
    68. while(p || top != -1){
    69. if(p){
    70. stack[++top] = p;
    71. tag[top] = 1;
    72. p = p -> lchild;
    73. }else{
    74. if(tag[top] == 1){
    75. tag[top] = 2;
    76. p = stack[top];
    77. p = p -> rchild;
    78. }else{//说明是叶子节点了
    79. p = stack[top--];
    80. Visit(p);
    81. p = NULL;
    82. }
    83. }
    84. }
    85. }

  • 相关阅读:
    安防监控/视频汇聚/云存储/AI智能视频分析平台EasyCVR显示CPU过载,该如何解决?
    1100亩烟台深耕水稻 国稻种芯·中国水稻节:山东盐碱地水稻
    【虹科方案】虹科数字化仪——机械测量的最佳方案!(二)
    车载T-BOX
    【Python基础入门7】程序的组织结构、range函数及pass语句
    金融行业多活架构设计及容灾发展趋势
    ASPICE是汽车软件开发中的质量保证流程
    9.14--贪心算法列题
    Spring 控制反转和依赖注入
    SpringBoot:(六)YAML配置文件
  • 原文地址:https://blog.csdn.net/shengruyu/article/details/126573660