Welcome 微信登录
编程资源 图片资源库 蚂蚁家优选 PDF转换器

首页 / 操作系统 / Linux / 二叉树的遍历

自娱自乐型二叉树的遍历。1 Tree.h  定义Tree相关的，使用了STL
  1. #ifndef __TREE_H__   
  2. #define __TREE_H__   
  3.   
  4. #include <iostream>   
  5. #include <stack>   
  6. #include <queue>   
  7. using std::iostream;  
  8. using std::cout;  
  9. using std::endl;  
  10. using std::stack;  
  11. using std::queue;  
  12.   
  13. struct BinaryTreeNode;  
  14.   
  15.   
  16. typedef void （*BTREENODE_VISIT）（BinaryTreeNode* pBTreeNode）;  
  17.   
  18. struct BinaryTreeNode  
  19. {  
  20.     int data;  
  21.     int flags; //0:not in stack, 1: in stack   
  22.     int height;  
  23.     BinaryTreeNode* pLeftChildren;  
  24.     BinaryTreeNode* pRightChildren;  
  25.     BinaryTreeNode（）  
  26.     {  
  27.         pLeftChildren = pRightChildren = NULL;  
  28.         flags = 0;  
  29.         height = 0;  
  30.     }  
  31.     BinaryTreeNode（int data）  
  32.     {  
  33.         pLeftChildren = pRightChildren = NULL;  
  34.         this->data = data;  
  35.         flags = 0;  
  36.         height  = 0;  
  37.     }  
  38.     void createTrees（BinaryTreeNode *pLeft,BinaryTreeNode* pRight）  
  39.     {  
  40.         pLeftChildren = pLeft;  
  41.         pRightChildren = pRight;  
  42.     }  
  43.     static void preOrderVisitRecurs（BinaryTreeNode* pBTree,BTREENODE_VISIT pBTNodeVisitFunc）  
  44.     {  
  45.         if（pBTree）  
  46.         {  
  47.             if（pBTNodeVisitFunc）  
  48.                 pBTNodeVisitFunc（pBTree）;  
  49.             if（pBTree->pLeftChildren）  
  50.                 preOrderVisitRecurs（pBTree->pLeftChildren,pBTNodeVisitFunc）;  
  51.             if（pBTree->pRightChildren）  
  52.                 preOrderVisitRecurs（pBTree->pRightChildren,pBTNodeVisitFunc）;  
  53.         }  
  54.         return;  
  55.     }  
  56.     static void preOrderVisit（BinaryTreeNode* pBTree, BTREENODE_VISIT pBTNodeVisitFunc）  
  57.     {  
  58.         if（pBTree == NULL）  
  59.             return;  
  60.         typedef stack<BinaryTreeNode*> CBTNodeStack;  
  61.         CBTNodeStack  btnStack;  
  62.         btnStack.push（pBTree）;  
  63.         while（btnStack.size（） > 0）  
  64.         {  
  65.             BinaryTreeNode* pCurrent = btnStack.top（）;  
  66.             if（pCurrent）  
  67.                 pBTNodeVisitFunc（pCurrent）;  
  68.             btnStack.pop（）;  
  69.             if（pCurrent->pRightChildren）  
  70.                 btnStack.push（pCurrent->pRightChildren）;  
  71.             if（pCurrent->pLeftChildren）  
  72.                 btnStack.push（pCurrent->pLeftChildren）;  
  73.         }  
  74.   
  75.     };  
  76.     static void inOrderVisitRecurs（BinaryTreeNode* pBTree,BTREENODE_VISIT pBTNodeVisitFunc）  
  77.     {  
  78.         if（pBTree）  
  79.         {  
  80.             if（pBTree->pLeftChildren）  
  81.                 inOrderVisitRecurs（pBTree->pLeftChildren,pBTNodeVisitFunc）;  
  82.             if（pBTNodeVisitFunc）  
  83.                 pBTNodeVisitFunc（pBTree）;  
  84.             if（pBTree->pRightChildren）  
  85.                 inOrderVisitRecurs（pBTree->pRightChildren,pBTNodeVisitFunc）;  
  86.         }  
  87.         return;  
  88.     }  
  89.     static void inOrderVisit（BinaryTreeNode* pBTree,BTREENODE_VISIT pBTNodeVisitFunc）  
  90.     {  
  91.         if（pBTree == NULL）  
  92.             return;  
  93.           
  94.         typedef stack<BinaryTreeNode*> CBTNodeStack;  
  95.         CBTNodeStack  btnStack;  
  96.         btnStack.push（pBTree）;  
  97.         pBTree->flags = 1;  
  98.         while（btnStack.size（） > 0）  
  99.         {  
  100.             pBTree = btnStack.top（）;  
  101.             while（pBTree->pLeftChildren ！= NULL && pBTree->pLeftChildren->flags == 0）  
  102.             {  
  103.                 btnStack.push（pBTree->pLeftChildren）;  
  104.                 pBTree->pLeftChildren->flags = 1;  
  105.                 pBTree = btnStack.top（）;  
  106.             }  
  107.   
  108.             pBTree = btnStack.top（）;  
  109.             if（pBTNodeVisitFunc）  
  110.                 pBTNodeVisitFunc（pBTree）; //visit the left leaf or leftest root   
  111.             btnStack.pop（）;  
  112.             if（pBTree->pRightChildren && pBTree->pRightChildren->flags == 0）  
  113.             {  
  114.                 btnStack.push（pBTree->pRightChildren）;  
  115.                 pBTree->pRightChildren->flags = 1;  
  116.                 continue;  
  117.             }  
  118.         }  
  119.         return;  
  120.     }  
  121.   
  122.     static void postOrderVisitRecurs（BinaryTreeNode* pBTree,BTREENODE_VISIT pBTNodeVisitFunc）  
  123.     {  
  124.         if（pBTree）  
  125.         {  
  126.             if（pBTree->pLeftChildren）  
  127.                 postOrderVisitRecurs（pBTree->pLeftChildren,pBTNodeVisitFunc）;  
  128.             if（pBTree->pRightChildren）  
  129.                 postOrderVisitRecurs（pBTree->pRightChildren,pBTNodeVisitFunc）;  
  130.             if（pBTNodeVisitFunc）  
  131.                 pBTNodeVisitFunc（pBTree）;  
  132.         }  
  133.         return;  
  134.     }  
  135.     static void postOrderVisit（BinaryTreeNode* pBTree,BTREENODE_VISIT pBTNodeVisitFunc）  
  136.     {  
  137.         if（pBTree == NULL）  
  138.             return;  
  139.         typedef stack<BinaryTreeNode*> CBTNodeStack;  
  140.         CBTNodeStack  btnStack;  
  141.         btnStack.push（pBTree）;  
  142.         pBTree->flags = 1;  
  143.         while（btnStack.size（） > 0）  
  144.         {  
  145.             pBTree = btnStack.top（）;  
  146.             while（pBTree->pLeftChildren ！= NULL && pBTree->pLeftChildren->flags == 0）  
  147.             {  
  148.                 btnStack.push（pBTree->pLeftChildren）;  
  149.                 pBTree->pLeftChildren->flags = 1;  
  150.                 pBTree = btnStack.top（）;  
  151.             }  
  152.   
  153.             pBTree = btnStack.top（）;  
  154.             if（pBTree->pRightChildren && pBTree->pRightChildren->flags == 0）  
  155.             {  
  156.                 btnStack.push（pBTree->pRightChildren）;  
  157.                 pBTree->pRightChildren->flags = 1;  
  158.                 continue;  
  159.             }  
  160.             if（pBTNodeVisitFunc）  
  161.                 pBTNodeVisitFunc（pBTree）;  
  162.               
  163.             btnStack.pop（）;  
  164.         }  
  165.         return;  
  166.     };  
  167.     static void levelVisit（BinaryTreeNode* pBTree,BTREENODE_VISIT pBTNodeVisitFunc）  
  168.     {  
  169.         typedef queue<BinaryTreeNode*> CBTNodeQueue;  
  170.         CBTNodeQueue btQueue;  
  171.         btQueue.push（pBTree）;  
  172.         while（btQueue.size（））  
  173.         {  
  174.             BinaryTreeNode* pCurrent = btQueue.front（）;  
  175.             if（pCurrent->pLeftChildren）  
  176.                 btQueue.push（pCurrent->pLeftChildren）;  
  177.             if（pCurrent->pRightChildren）  
  178.                 btQueue.push（pCurrent->pRightChildren）;  
  179.             if（pBTNodeVisitFunc）  
  180.                 pBTNodeVisitFunc（pCurrent）;  
  181.             btQueue.pop（）;  
  182.         }  
  183.     }  
  184.   
  185. };  
  186.   
  187.   
  188.   
  189.   
  190.   
  191. #endif  
2 测试：
  1. // DataStructTest.cpp : 定义控制台应用程序的入口点。   
  2. //   
  3.   
  4. #include "stdafx.h"   
  5.   
  6. #include "Tree.h"   
  7.   
  8.   
  9. void PRINT_BNVALUE（BinaryTreeNode* pBTreeNode）  
  10. {  
  11.     cout<<"TreeVale " << pBTreeNode->data << endl;  
  12. }  
  13. void RESET_FLAGS（BinaryTreeNode* pBTreeNode）  
  14. {  
  15.     pBTreeNode->flags = 0;  
  16. }  
  17. int _tmain（int argc, _TCHAR* argv[]）  
  18. {  
  19.     /* 
  20.         构造目标树 
  21.          1 
  22.         /   
  23.        2    3 
  24.       /    / 
  25.      4   5 6 
  26.         /    
  27.        7     8 
  28.      
  29.     */  
  30.       
  31.     BinaryTreeNode testBNTree8（8）;  
  32.     BinaryTreeNode testBNTree7（7）;  
  33.     BinaryTreeNode testBNTree6（6）;  
  34.     BinaryTreeNode testBNTree5（5）;  
  35.     BinaryTreeNode testBNTree4（4）;  
  36.     BinaryTreeNode testBNTree3（3）;  
  37.     BinaryTreeNode testBNTree2（2）;  
  38.     BinaryTreeNode testBNTree1（1）;  
  39.   
  40.   
  41.     testBNTree1.createTrees（&testBNTree2,&testBNTree3）;  
  42.     testBNTree2.createTrees（&testBNTree4,&testBNTree5）;  
  43.     testBNTree5.createTrees（&testBNTree7,NULL）;  
  44.   
  45.     testBNTree3.createTrees（&testBNTree6,NULL）;  
  46.     testBNTree6.createTrees（NULL,&testBNTree8）;  
  47.   
  48.     cout<<"travse pre order recurs"<<endl;  
  49.     BinaryTreeNode::preOrderVisitRecurs（&testBNTree1,PRINT_BNVALUE）;  
  50.     cout<<"travse pre order NOT recurs"<<endl;  
  51.     BinaryTreeNode::preOrderVisit（&testBNTree1,PRINT_BNVALUE）;  
  52.   
  53.     cout<<"travse in order recurs"<<endl;  
  54.     BinaryTreeNode::inOrderVisitRecurs（&testBNTree1,PRINT_BNVALUE）;  
  55.     cout<<"travse in order NOT recurs"<<endl;  
  56.     BinaryTreeNode::inOrderVisit（&testBNTree1,PRINT_BNVALUE）;  
  57.     //采用层级遍历清空flags标志   
  58.     BinaryTreeNode::levelVisit（&testBNTree1,RESET_FLAGS）;  
  59.   
  60.     cout<<"travse post order recurs"<<endl;  
  61.     BinaryTreeNode::postOrderVisitRecurs（&testBNTree1,PRINT_BNVALUE）;  
  62.     cout<<"travse post order NOT recurs"<<endl;  
  63.     BinaryTreeNode::postOrderVisit（&testBNTree1,PRINT_BNVALUE）;  
  64.   
  65.     cout<<"travse level"<<endl;  
  66.     BinaryTreeNode::levelVisit（&testBNTree1,PRINT_BNVALUE）;  
  67.   
  68.   
  69.     return 0;  
  70. }  
版权所有©石家庄振强科技有限公司2024 冀ICP备08103738号-5 网站地图