非递归实现树的遍历

方法1：使用指针

View Code

  1 #include <iostream>
  2 using namespace std;
  3 
  4 struct node
  5 {
  6 int key;
  7 node *left;
  8 node *right;
  9 node *parent;
 10 node(){}
 11 node(int x):key(x),left(NULL),right(NULL){}
 12 };
 13 
 14 struct tree
 15 {
 16 node *root;
 17 tree():root(NULL){}
 18 };
 19 
 20 void Tree_Print(tree *T)
 21 {
 22 node *t = T->root;
 23 while(t)
 24 {
 25 if(t->left)
 26 {
 27 t = t->left;
 28 continue;
 29 }
 30 else
 31 {
 32 cout<<t->key<<' ';
 33 if(t->right)
 34 {
 35 t = t->right;
 36 continue;
 37 }
 38 while(1)
 39 {
 40 
 41 if(t == t->parent->left && t->parent->right)
 42 {
 43 cout<<t->parent->key<<' ';
 44 t = t->parent->right;
 45 break;
 46 }
 47 
 48 if(t == t->parent->left && t->parent->right == NULL)
 49 cout<<t->parent->key<<' ';
 50 t = t->parent;
 51 if(t == T->root)
 52 {
 53 cout<<endl;
 54 return;
 55 }
 56 }
 57 }
 58 }
 59 }
 60 /*input:0=NIL
 61 12 7 3
 62 15 8 0
 63 4 10 0
 64 10 5 9
 65 2 0 0
 66 18 1 4
 67 7 0 0
 68 14 6 2
 69 21 0 0
 70 5 0 0
 71 */
 72 int main()
 73 {
 74 //    构造一棵树按照10.4-1
 75 int i;
 76 node A[11];//这个数组仅仅用于构造10.4-1中的树，在遍历时不使用
 77 for(i = 1; i <= 10; i++)
 78 {
 79 int key, left, right;
 80 cin>>key>>left>>right;
 81 A[i].key = key;
 82 if(left)
 83 {
 84 A[i].left = &A[left];
 85 A[left].parent = &A[i];
 86 }
 87 else 
 88 A[i].left = NULL;
 89 if(right)
 90 {
 91 A[i].right = &A[right];
 92 A[right].parent = &A[i];
 93 }
 94 else A[i].right = NULL;
 95 }
 96 //生成一棵树
 97 tree *T = new tree();
 98 T->root = &A[6];
 99 10.4-5
100 Tree_Print(T);
101 system("pause");
102 return 0;
103 }

方法2：使用栈实现

View Code

  1 #include<iostream>
  2 #include <malloc.h>
  3 
  4 typedef struct _Bin_Tree
  5 {
  6 _Bin_Tree *pLeft;
  7 _Bin_Tree *pRight;
  8 int nData;
  9 }Bin_Tree;
 10 
 11 typedef struct _STACK
 12 {
 13 Bin_Tree *pData;
 14 _STACK *pNext;
 15 } STACK;
 16 
 17 //将一个节点置0
 18 void ZeroNode(Bin_Tree *pNode)
 19 {
 20 pNode->nData = 0;
 21 pNode->pLeft = 0;
 22 pNode->pRight = 0;
 23 }
 24 
 25 
 26 void CreateATree(Bin_Tree *pNode,int n)
 27 {
 28 Bin_Tree *pLeft=0,*pRight=0;
 29 if ( pNode == 0 ) return;
 30 
 31 pLeft = (_Bin_Tree *)malloc( sizeof(Bin_Tree) );
 32 ZeroNode( pLeft );
 33 pLeft->nData = n;
 34 pRight = (_Bin_Tree *)malloc( sizeof(Bin_Tree) );
 35 ZeroNode( pRight );
 36 pRight->nData = n+1;
 37 
 38 pNode->pLeft = pLeft;
 39 pNode->pRight = pRight;
 40 }
 41 
 42 //释放一个二叉树所占的内存
 43 void ReleaseTree(Bin_Tree **pNode)
 44 {
 45 if ( (*pNode) == 0 ) return;
 46 ReleaseTree( &((*pNode)->pLeft) );
 47 ReleaseTree( &((*pNode)->pRight) );
 48 free( (*pNode) );
 49 (*pNode) = 0;
 50 }
 51 
 52 //压栈
 53 void push( STACK * pS,STACK **pTop )
 54 {
 55 if( (*pTop) == 0 )
 56 {
 57 (*pTop) = pS;
 58 }
 59 else
 60 {
 61 pS->pNext = *pTop;
 62 (*pTop) = pS;//将栈指针上移
 63 }
 64 }
 65 
 66 //出栈
 67 STACK * pop( STACK **pTop )
 68 {
 69 if ( (*pTop) == 0 ) return 0;
 70 (*pTop) = (*pTop)->pNext;//栈顶指针下移
 71 return (*pTop);
 72 }
 73 
 74 //栈遍历前序
 75 //最要思想:
 76 //第一步将树的左分支的左节点压入栈,最后栈顶将是树最左边节点
 77 //然后从底部将栈中的每个节点放弹出,遍历其右节点,如果右节点还有分支,重复第一步.
 78 void PreOrder_stack( Bin_Tree *pRoot )
 79 {
 80 STACK *pSTop=0,*pSTemp=0;
 81 Bin_Tree *pTemp = pRoot;
 82 if ( pRoot == 0) return;
 83 
 84 while ( pTemp || pSTop != 0 )
 85 {
 86 if( pTemp )
 87 {
 88 STACK *pStack = (STACK *)malloc( sizeof( STACK ) );
 89 pStack->pData = pTemp;
 90 pStack->pNext = 0;
 91 printf("%d,",pTemp->nData);
 92 push( pStack, &pSTop );
 93 pTemp = pTemp->pLeft;
 94 }
 95 else
 96 {
 97 Bin_Tree *pSubRight = pSTop->pData->pRight;
 98 pSTemp = pSTop;
 99 pSTop = pop( &pSTop );
100 pTemp = pSubRight;
101 free(pSTemp);
102 pSTemp = 0;
103 }
104 }
105 }
106 
107 //栈遍历中序
108 //主要思想是将按左边寻址的方式，进行寻址，将每个节点压入栈。
109 //当左子到头后，再出弹栈，这样必然是先左、后中，再右。
110 void InOrder_stack( Bin_Tree *pRoot )
111 {
112 STACK *pSTop=0,*pSTemp=0;
113 Bin_Tree *pTemp = pRoot;
114 if ( pRoot == 0) return;
115 
116 while ( pTemp || pSTop != 0 )
117 {
118 if( pTemp )
119 {
120 STACK *pStack = (STACK *)malloc( sizeof( STACK ) );
121 pStack->pData = pTemp;
122 pStack->pNext = 0;
123 push( pStack, &pSTop );
124 pTemp = pTemp->pLeft;
125 }
126 else
127 {
128 pSTemp = pSTop;
129 pSTop = pop( &pSTop );
130 printf("%d,",pSTemp->pData->nData);
131 pTemp = pSTemp->pData->pRight;
132 free(pSTemp);
133 pSTemp = 0;
134 }
135 }
136 }
137 
138 //栈遍历后序
139 //主要思想是先遍历左右两个子树，再遍历根节点。
140 //后序遍历有一个需要主意的地方，就是从右树遍历完后，
141 //开始弹栈的时候，需要加一个pPre标记，该无数已经访问过,否则无法遍历完成。
142 void PostOrder_stack( Bin_Tree *pRoot )
143 {
144 STACK *pSTop=0,*pSTemp=0;
145 Bin_Tree *pTemp = pRoot, *pPre=0;
146 if ( pRoot == 0) return;
147 
148 while ( pTemp || pSTop != 0 )
149 {
150 while( pTemp )
151 {//遍历左子树
152 STACK *pStack = (STACK *)malloc( sizeof( STACK ) );
153 pStack->pData = pTemp;
154 pStack->pNext = 0;
155 push( pStack, &pSTop );
156 pTemp = pTemp->pLeft;
157 }
158 if ( pSTop->pData->pRight == 0 || pPre == pSTop->pData->pRight )
159 {//没有右子树或该节点刚被访问过
160 printf("%d,", pSTop->pData->nData);
161 pSTemp = pSTop;
162 pPre = pSTop->pData;
163 pSTop = pop( &pSTop );
164 pSTemp = 0;
165 }
166 else
167 {
168 pTemp = pSTop->pData->pRight;
169 }
170 }
171 }
172 
173