遍历二叉树的各种操作（非递归遍历）

890阅读　0评论2013-11-26　double_lq
分类：C/C++

转载于博客：http://blog.csdn.net/hackbuteer1/article/details/6583988

 先使用先序的方法建立一棵二叉树，然后分别使用递归与非递归的方法实现前序、中序、后序遍历二叉树，并使用了两种方法来进行层次遍历二叉树，一种方法就是使用STL中的queue，另外一种方法就是定义了一个数组队列，分别使用了front和rear两个数组的下标来表示入队与出队，还有两个操作就是求二叉树的深度、结点数。。。


  1. #include<iostream>
  2. #include<queue>
  3. #include<stack>
  4. using namespace std;
  5.     
  6. //二叉树节点的描述
  7. typedef struct BiTNode
  8. {
  9.     char data;
  10.     struct BiTNode *lchild, *rchild;
  11. }BiTNode,*BiTree;
  12.     
  13. //按先序遍历创建二叉树
  14. //BiTree *CreateBiTree()
  15. //void CreateBiTree(BiTree &root)
  16. void CreateBiTree(BiTNode **root)
  17. {
  18.     char ch; //要插入的数据
  19.     scanf("%c", &ch);
  20.     //cin>>ch;
  21.     if(ch=='#')
  22.         *root = NULL;
  23.     else
  24.     {
  25.         *root = (BiTNode *)malloc(sizeof(BiTNode));
  26.         (*root)->data = ch;
  27.         printf("请输入%c的左孩子：",ch);
  28.         CreateBiTree(&((*root)->lchild));
  29.         printf("请输入%c的右孩子：",ch);
  30.         CreateBiTree(&((*root)->rchild));
  31.     }
  32. }
  33.     
  34. //前序遍历的算法
  35. void PreOrder(BiTNode *root)
  36. {
  37.     if(root==NULL)
  38.         return ;
  39.     printf("%c ", root->data); //输出数据
  40.     PreOrder(root->lchild); //递归调用，前序遍历左子树 
  41.     PreOrder(root->rchild); //递归调用，前序遍历右子树
  42. }
  43.     
  44. //前序遍历的算法
  45. void InOrder(BiTNode *root)
  46. {
  47.     if(root==NULL)
  48.         return ;
  49.     InOrder(root->lchild); //递归调用，前序遍历左子树
  50.     printf("%c ", root->data); //输出数据
  51.     InOrder(root->rchild); //递归调用，前序遍历右子树
  52. }
  53.     
  54. //后序遍历的算法 
  55. void PostOrder(BiTNode *root)
  56. {
  57.     if(root==NULL)
  58.         return ;
  59.     PostOrder(root->lchild); //递归调用，前序遍历左子树 
  60.     PostOrder(root->rchild); //递归调用，前序遍历右子树 
  61.     printf("%c ", root->data); //输出数据
  62. }
  63.     
  64. /*
  65. 二叉树的非递归前序遍历，前序遍历思想：先让根进栈，只要栈不为空，就可以做弹出操作，
  66. 每次弹出一个结点，记得把它的左右结点都进栈，记得右子树先进栈，这样可以保证右子树在栈中总处于左子树的下面。
  67. */
  68. void PreOrder_Nonrecursive(BiTree T) //先序遍历非递归
  69. {
  70.     if(!T)
  71.         return ;
  72.       
  73.     stack<BiTree> s;
  74.     s.push(T);
  75.     
  76.     while(!s.empty())
  77.     {
  78.         BiTree temp = s.top();
  79.         cout<<temp->data<<" ";
  80.         s.pop();
  81.         if(temp->rchild)
  82.             s.push(temp->rchild);
  83.         if(temp->lchild)
  84.             s.push(temp->lchild);
  85.     }
  86. }
  87.   
  88. void PreOrder_Nonrecursive1(BiTree T) //先序遍历非递归
  89. {
  90.     if(!T)
  91.         return ;
  92.     stack<BiTree> s;
  93.     BiTree curr = T;
  94.     while(curr != NULL || !s.empty())
  95.     {
  96.         while(curr != NULL)
  97.         {
  98.             cout<<curr->data<<" ";
  99.             s.push(curr);
  100.             curr = curr->lchild;
  101.         }
  102.         if(!s.empty())
  103.         {
  104.             curr = s.top();
  105.             s.pop();
  106.             curr = curr->rchild;
  107.         }
  108.     }
  109. }
  110.   
  111. void PreOrder_Nonrecursive2(BiTree T) //先序遍历非递归
  112. {
  113.     if(!T)
  114.         return ;
  115.     
  116.     stack<BiTree> s;
  117.     while(T)     //左子树上的节点全部压入栈中
  118.     {
  119.         s.push(T);
  120.         cout<<T->data<<" ";
  121.         T = T->lchild;
  122.     }
  123.         
  124.     while(!s.empty())
  125.     {
  126.         BiTree temp = s.top()->rchild;     //栈顶元素的右子树
  127.         s.pop();          //弹出栈顶元素
  128.         while(temp) //栈顶元素存在右子树，则对右子树同样遍历到最下方
  129.         {
  130.             cout<<temp->data<<" ";
  131.             s.push(temp);
  132.             temp = temp->lchild;
  133.         }
  134.     }
  135. }
  136.   
  137. void InOrderTraverse1(BiTree T) //中序遍历非递归
  138. {
  139.     if(!T)
  140.         return ;
  141.     BiTree curr = T; //指向当前要检查的节点
  142.     stack<BiTree> s;
  143.     while(curr != NULL || !s.empty())
  144.     {
  145.         while(curr != NULL)
  146.         {
  147.             s.push(curr);
  148.             curr = curr->lchild;
  149.         }//while
  150.         if(!s.empty())
  151.         {
  152.             curr = s.top();
  153.             s.pop();
  154.             cout<<curr->data<<" ";
  155.             curr = curr->rchild;
  156.         }
  157.     }
  158. }
  159.   
  160. void InOrderTraverse(BiTree T) //中序遍历非递归
  161. {
  162.     if(!T)
  163.         return ;
  164.     stack<BiTree> s;
  165.     BiTree curr = T->lchild; //指向当前要检查的节点
  166.     s.push(T);
  167.     while(curr != NULL || !s.empty())
  168.     {
  169.         while(curr != NULL) //一直左走 
  170.         {
  171.             s.push(curr);
  172.             curr = curr->lchild;
  173.         }
  174.         curr = s.top();
  175.         s.pop();
  176.         cout<<curr->data<<" ";
  177.         curr = curr->rchild;
  178.     }
  179. }
  180.   
  181. void PostOrder_Nonrecursive1(BiTree T) //后序遍历非递归
  182. {
  183.     stack<BiTree> S;
  184.     BiTree curr = T ; //指向当前要检查的节点
  185.     BiTree previsited = NULL; //指向前一个被访问的节点
  186.     while(curr != NULL || !S.empty()) //栈空时结束
  187.     {
  188.         while(curr != NULL) //一直左走直到为空 
  189.         {
  190.             S.push(curr);
  191.             curr = curr->lchild;
  192.         }
  193.         curr = S.top();
  194.         //当前节点的右孩子如果为空或者已经被访问，则访问当前节点
  195.         if(curr->rchild == NULL || curr->rchild == previsited)
  196.         {
  197.             cout<<curr->data<<" ";
  198.             previsited = curr;
  199.             S.pop();
  200.             curr = NULL;
  201.         }
  202.         else
  203.             curr = curr->rchild; //否则访问右孩子 
  204.     }
  205. }
  206.     
  207. void PostOrder_Nonrecursive(BiTree T) //后序遍历的非递归 双栈法 
  208. {
  209.     stack<BiTree> s1 , s2;
  210.     BiTree curr ; //指向当前要检查的节点
  211.     s1.push(T);
  212.     while(!s1.empty()) //栈空时结束 
  213.     {
  214.         curr = s1.top();
  215.         s1.pop();
  216.         s2.push(curr);
  217.         if(curr->lchild)
  218.             s1.push(curr->lchild);
  219.         if(curr->rchild)
  220.             s1.push(curr->rchild);
  221.     }
  222.     while(!s2.empty())
  223.     {
  224.         printf("%c ", s2.top()->data);
  225.         s2.pop();
  226.     }
  227. }
  228.     
  229.     
  230. int visit(BiTree T)
  231. {
  232.     if(T)
  233.     {
  234.         printf("%c ",T->data);
  235.         return 1;
  236.     }
  237.     else
  238.         return 0;
  239. }
  240.     
  241. void LeverTraverse(BiTree T) //方法一、非递归层次遍历二叉树 
  242. {
  243.     queue <BiTree> Q;
  244.     BiTree p;
  245.     p = T;
  246.     if(visit(p)==1)
  247.         Q.push(p);
  248.     while(!Q.empty())
  249.     {
  250.         p = Q.front();
  251.         Q.pop();
  252.         if(visit(p->lchild) == 1)
  253.             Q.push(p->lchild);
  254.         if(visit(p->rchild) == 1)
  255.             Q.push(p->rchild);
  256.     }
  257. }
  258. void LevelOrder(BiTree BT) //方法一、非递归层次遍历二叉树 
  259. {
  260.     BiTNode *queue[10];//定义队列有十个空间 
  261.     if (BT==NULL)
  262.         return;
  263.     int front,rear;
  264.     front=rear=0;
  265.     queue[rear++]=BT;
  266.     while(front!=rear)//如果队尾指针不等于队头指针时 
  267.     {
  268.         cout<<queue[front]->data<<" "; //输出遍历结果 
  269.         if(queue[front]->lchild!=NULL) //将对首节点的左孩子指针入队列 
  270.         {
  271.             queue[rear]=queue[front]->lchild;
  272.             rear++; //队尾指针后移一位 
  273.         }
  274.         if(queue[front]->rchild!=NULL)
  275.         {
  276.             queue[rear]=queue[front]->rchild; //将对首节点的右孩子指针入队列
  277.             rear++; //队尾指针后移一位
  278.         }
  279.         front++; //队头指针后移一位
  280.     }
  281. }
  282.     
  283. int depth(BiTNode *T) //树的深度
  284. {
  285.     if(!T)
  286.         return 0;
  287.     int d1,d2;
  288.     d1=depth(T->lchild);
  289.     d2=depth(T->rchild);
  290.     return (d1>d2?d1:d2)+1;
  291.     //return (depth(T->lchild)>depth(T->rchild)?depth(T->lchild):depth(T->rchild))+1;
  292. }
  293. int CountNode(BiTNode *T)
  294. {
  295.     if(T == NULL)
  296.         return 0;
  297.     return 1+CountNode(T->lchild)+CountNode(T->rchild);
  298. }
  299.     
  300. int main(void)
  301. {
  302.     BiTNode *root=NULL; //定义一个根结点
  303.     int flag=1,k;
  304.     printf(" 本程序实现二叉树的基本操作。\n");
  305.     printf("可以进行建立二叉树，递归先序、中序、后序遍历，非递归先序、中序遍历及非递归层序遍历等操作。\n");
  306.     
  307.     while(flag)
  308.     {
  309.         printf("\n");
  310.         printf("|--------------------------------------------------------------|\n");
  311.         printf("| 二叉树的基本操作如下: |\n");
  312.         printf("| 0.创建二叉树 |\n");
  313.         printf("| 1.递归先序遍历 |\n");
  314.         printf("| 2.递归中序遍历 |\n");
  315.         printf("| 3.递归后序遍历 |\n");
  316.         printf("| 4.非递归先序遍历 |\n");
  317.         printf("| 5.非递归中序遍历 |\n");
  318.         printf("| 6.非递归后序遍历 |\n");
  319.         printf("| 7.非递归层序遍历 |\n");
  320.         printf("| 8.二叉树的深度 |\n");
  321.         printf("| 9.二叉树的结点个数 |\n");
  322.         printf("| 10.退出程序 |\n");
  323.         printf("|--------------------------------------------------------------|\n");
  324.         printf(" 请选择功能：");
  325.         scanf("%d",&k);
  326.         switch(k)
  327.         {
  328.         case 0:
  329.             printf("请建立二叉树并输入二叉树的根节点：");
  330.             CreateBiTree(&root);
  331.             break;
  332.         case 1:
  333.             if(root)
  334.             {
  335.                 printf("递归先序遍历二叉树的结果为：");
  336.                 PreOrder(root);
  337.                 printf("\n");
  338.             }
  339.             else
  340.                 printf(" 二叉树为空！\n");
  341.             break;
  342.         case 2:
  343.             if(root)
  344.             {
  345.                 printf("递归中序遍历二叉树的结果为：");
  346.                 InOrder(root);
  347.                 printf("\n");
  348.             }
  349.             else
  350.                 printf(" 二叉树为空！\n");
  351.             break;
  352.         case 3:
  353.             if(root)
  354.             {
  355.                 printf("递归后序遍历二叉树的结果为：");
  356.                 PostOrder(root);
  357.                 printf("\n");
  358.             }
  359.             else
  360.                 printf(" 二叉树为空！\n");
  361.             break;
  362.         case 4:
  363.             if(root)
  364.             {
  365.                 printf("非递归先序遍历二叉树：");
  366.                 PreOrder_Nonrecursive1(root);
  367.                 printf("\n");
  368.             }
  369.             else
  370.                 printf(" 二叉树为空！\n");
  371.             break;
  372.         case 5:
  373.             if(root)
  374.             {
  375.                 printf("非递归中序遍历二叉树：");
  376.                 InOrderTraverse1(root);
  377.                 printf("\n");
  378.             }
  379.             else
  380.                 printf(" 二叉树为空！\n");
  381.             break;
  382.         case 6:
  383.             if(root)
  384.             {
  385.                 printf("非递归后序遍历二叉树：");
  386.                 PostOrder_Nonrecursive(root);
  387.                 printf("\n");
  388.             }
  389.             else
  390.                 printf(" 二叉树为空！\n");
  391.             break;
  392.         case 7:
  393.             if(root)
  394.             {
  395.                 printf("非递归层序遍历二叉树：");
  396.                 //LeverTraverse(root);
  397.                 LevelOrder(root);
  398.                 printf("\n");
  399.             }
  400.             else
  401.                 printf(" 二叉树为空！\n");
  402.             break;
  403.         case 8:
  404.             if(root)
  405.                 printf("这棵二叉树的深度为：%d\n",depth(root));
  406.             else
  407.                 printf(" 二叉树为空！\n");
  408.             break;
  409.         case 9:
  410.             if(root)
  411.                 printf("这棵二叉树的结点个数为：%d\n",CountNode(root));
  412.             else
  413.                 printf(" 二叉树为空！\n");
  414.             break;
  415.         default:
  416.             flag=0;
  417.             printf("程序运行结束，按任意键退出！\n");
  418.         }
  419.     }
  420.     system("pause");
  421.     return 0;
  422. }


后序遍历非递归的另外一种写法：

 
  1. /*
  2. 后序遍历由于遍历父节点是在遍历子节点之后，而且左节点和右节点遍历后的行为不一样，
  3. 所以需要用变量来记录前一次访问的节点，根据前一次节点和现在的节点的关系来确定具体执行什么操作
  4. */ 
  5. void Postorder(BiTree T)
  6. {
  7.     if(T == NULL)
  8.         return ;
  9.     stack<BiTree> s;
  10.     BiTree prev = NULL , curr = NULL;
  11.     s.push(T);
  12.     while(!s.empty())
  13.     {
  14.         curr = s.top();
  15.         if(prev == NULL || prev->lchild == curr || prev->rchild == curr)
  16.         {
  17.             if(curr->lchild != NULL)
  18.                 s.push(curr->lchild);
  19.             else if(curr->rchild != NULL)
  20.                 s.push(curr->rchild);
  21.         }
  22.         else if(curr->lchild == prev)
  23.         {
  24.             if(curr->rchild != NULL)
  25.                 s.push(curr->rchild);
  26.         }
  27.         else
  28.         {
  29.             cout<<curr->data;
  30.             s.pop();
  31.         }
  32.         prev = curr;
  33.     }
  34. }

输入二叉树中的两个节点，输出这两个结点在树中最低的共同父节点。
思路：遍历二叉树，找到一条从根节点开始到目的节点的路径，然后在两条路径上查找共同的父节点。
  
    
  1. //得到一条从根节点开始到目的地节点的路径
  2. bool GetNodePath(TreeNode *pRoot , TreeNode *pNode , vector<TreeNode *> &path)
  3. {
  4.     if(pRoot == NULL)
  5.         return false;
  6.     if(pRoot == pNode)
  7.         return true;
  8.     else if(GetNodePath(pRoot->lchild , pNode , path) )
  9.     {
  10.         path.push_back(pRoot->lchild);
  11.         return true;
  12.     }
  13.     else if(GetNodePath(pRoot->rchild , pNode , path) )
  14.     {
  15.         path.push_back(pRoot->rchild);
  16.         return true;
  17.     }
  18.     return false;
  19. }
  20. TreeNode *GetLastCommonNode(const vector<TreeNode *> &path1 , const vector<TreeNode *> &path2)
  21. {
  22.     vector<TreeNode *>::const_iterator iter1 = path1.begin();
  23.     vector<TreeNode *>::const_iterator iter2 = path2.begin();
  24.     TreeNode *pLast;
  25.     while(iter1 != path1.end() && iter2 != path2.end() )
  26.     {
  27.         if(*iter1 == *iter2)
  28.             pLast = *iter1;
  29.         else
  30.             break;
  31.         iter1++;
  32.         iter2++;
  33.     }
  34.     return pLast;
  35. }
  36. TreeNode *GetLastCommonParent(TreeNode *pRoot , TreeNode *pNode1 , TreeNode *pNode2)
  37. {
  38.     if(pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
  39.         return NULL;
  40.     vector<TreeNode *> path1;
  41.     GetNodePath(pRoot , pNode1 , path1);
  42.   
  43.     vector<TreeNode *> path2;
  44.     GetNodePath(pRoot , pNode2 , path2);
  45.     return GetLastCommonNode(path1 , path2);
  46. }



上一篇：类的大小——sizeof 的研究
下一篇：遍历二叉树的操作