Chinaunix

标题: 二叉树的递归与非递归遍历 [打印本页]
作者: ypxing    时间: 2007-11-16 10:58
标题: 二叉树的递归与非递归遍历
看了版主converse写的二叉树的递归与非递归遍历

http://www.cppblog.com/converse/archive/2006/07/08/9577.html

其中, 版主写到:
"感觉其中后序遍历的非递归算法比较困难,想了很久最后的实现还是不够优雅"

俺也写了一个玩玩, 功能一样, 但是思路不一样, 呵呵


  2. #include <iostream>
  3. #include <stack>
  4. #include <cassert>
  5. using namespace std;

  7. struct node
  8. {
  9.   node* lchild;
  10.   node* rchild;
  11.   int key;
  12.   node(int data=0, node* left=NULL, node* right=NULL)
  13.   {
  14.     key = data;
  15.     lchild = left;
  16.     rchild = right;
  17.   }
  18. };

  20. class Tree
  21. {
  22.   
  23. public:
  24.   Tree()
  25.   {
  26.     root = NULL;
  27.   }
  28.   Tree(int array[], int size);
  29.   ~Tree();
  30.   void traverse();
  31.   void postTraverse();
  32.   void recur_postTraverse(node* cur);
  33.   void preTraverse();
  34.   void recur_preTraverse(node* cur);
  35.   void inTraverse();
  36.   void recur_inTraverse(node* cur);

  38. private:
  39.   Tree(const Tree& t);
  40.   Tree& operator=(const Tree& t);
  41.   node* createTree(int array[], int size);
  42.   void destroyTree(node* cur);
  43. private:
  44.   node* root;
  45.   
  46. };

  48. Tree::Tree(int array[], int size)
  49. {
  50.   if ((array==NULL)||(size<=0))
  51.     root = NULL;
  52.   else
  53.     root = createTree(array, size);
  54. }

  56. node* Tree::createTree(int array[], int size)
  57. {
  58.   if ((array==NULL)||(size<=0))
  59.     return NULL;
  60.   int mid=size/2;
  61.   node* cur=new node(array[mid]);
  62.   cur->lchild = createTree(array, mid);
  63.   cur->rchild = createTree(array+mid+1, size-mid-1);
  64.   return cur;
  65. }

  67. Tree::~Tree()
  68. {
  69.   destroyTree(root);
  70. }

  72. void Tree::destroyTree(node* cur)
  73. {
  74.   if (cur != NULL)
  75.   {
  76.     destroyTree(cur->lchild);
  77.     destroyTree(cur->rchild);
  78.     delete cur;
  79.   }
  80.   
  81. }


  84. //后序递归遍历
  85. void Tree::recur_postTraverse(node* cur)
  86. {
  87.   if (cur!=NULL)
  88.   {
  89.     recur_postTraverse(cur->lchild);
  90.     recur_postTraverse(cur->rchild);
  91.     cout << cur->key << " ";
  92.   }
  93. }

  95. //先序递归遍历
  96. void Tree::recur_preTraverse(node* cur)
  97. {
  98.   if (cur!=NULL)
  99.   {
  100.     cout << cur->key << " ";
  101.     recur_preTraverse(cur->lchild);
  102.     recur_preTraverse(cur->rchild);
  103.   }
  104. }

  106. //中序递归遍历
  107. void Tree::recur_inTraverse(node* cur)
  108. {
  109.   if (cur!=NULL)
  110.   {
  111.     recur_inTraverse(cur->lchild);
  112.     cout << cur->key << " ";
  113.     recur_inTraverse(cur->rchild);
  114.   }
  115. }

  117. //后序非递归遍历
  118. void Tree::postTraverse()
  119. {
  120.   stack<node*> treeStack;
  121.   node *pre, *cur;
  122.   cur = root;
  123.   pre = NULL;
  124.   
  125.   if (cur!=NULL)
  126.     treeStack.push(cur);
  127.   
  128.   while(!treeStack.empty())
  129.   {
  130.     cur = treeStack.top();
  131.     if (((cur->lchild==NULL)&&(cur->rchild==NULL))||             //没有孩子结点或者
  132.         ((pre!=NULL)&&((pre==cur->lchild)||(pre==cur->rchild)))) //孩子遍历过了
  133.     {
  134.       treeStack.pop();
  135.       cout << cur->key << " ";
  136.       pre = cur;
  137.     }
  138.     else
  139.     {
  140.       if (cur->rchild!=NULL)
  141.         treeStack.push(cur->rchild);
  142.       if (cur->lchild!=NULL)
  143.         treeStack.push(cur->lchild);
  144.     }
  145.    
  146.   }
  147.   
  148. }

  150. //中序非递归遍历
  151. void Tree::inTraverse()
  152. {
  153.   stack<node*> treeStack;
  154.   node *pre, *cur;
  155.   cur = root;
  156.   
  157.   if (cur!=NULL)
  158.     treeStack.push(cur);
  159.   
  160.   while(!treeStack.empty())
  161.   {
  162.     cur = treeStack.top();
  163.     treeStack.pop();
  164.     if (cur == NULL)
  165.       continue;
  166.     if ((cur->lchild==NULL)||                                   //没有左孩子或者
  167.         ((!treeStack.empty())&&(treeStack.top()==cur->rchild))) //右孩子已经入过栈
  168.       cout << cur->key << " ";
  169.     else
  170.     {
  171.       treeStack.push(cur->rchild);
  172.       treeStack.push(cur);
  173.       if (cur->lchild!=NULL)
  174.         treeStack.push(cur->lchild);
  175.     }
  176.    
  177.   }
  178. }

  180. //先序非递归遍历
  181. void Tree::preTraverse()
  182. {
  183.   stack<node*> treeStack;
  184.   node *pre, *cur;
  185.   cur = root;
  186.   
  187.   if (cur!=NULL)
  188.     treeStack.push(cur);
  189.   
  190.   while(!treeStack.empty())
  191.   {
  192.     cur = treeStack.top();
  193.     treeStack.pop();
  194.     cout << cur->key << " ";
  195.     if (cur->rchild!=NULL)
  196.       treeStack.push(cur->rchild);
  197.     if (cur->lchild!=NULL)
  198.       treeStack.push(cur->lchild);
  199.   }
  200. }


  203. void Tree::traverse()
  204. {
  205.   recur_preTraverse(root);
  206.   cout << endl;
  207.   preTraverse();
  208.   cout << endl << endl;

  210.   recur_inTraverse(root);
  211.   cout << endl;
  212.   inTraverse();
  213.   cout << endl << endl;
  214.   
  215.   recur_postTraverse(root);
  216.   cout << endl;
  217.   postTraverse();
  218.   cout << endl << endl;
  219. }

  221. int main(int argc, char* argv[])
  222. {
  223.   int array[] = {2, 4, 5, 6, 8, 10, 11, 13, 15, 17, 20};
  224.   Tree tr(array, sizeof(array)/sizeof(array[0]));
  225.   tr.traverse();
  226. }
复制代码

[ 本帖最后由 ypxing 于 2007-11-16 11:22 编辑 ]
作者: converse    时间: 2007-11-16 15:37
没时间好好看看了,做个标记先~~




欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2