首页 > 代码库 > 二叉树的非递归遍历
二叉树的非递归遍历
二叉树的前序非递归遍历:
前序遍历的顺序：根结点——左孩子——右孩子“。
根据前序遍历访问结点的顺序可知：优先访问根结点，然后再分别访问左孩子和右孩子。
对于任意结点来说，都可将其视为根结点，因此可直接访问，访问完之后，若其左孩子不为空，则按照相同规则访问左子树；当访问了左子树之后，再访问它的右子树。
其处理过程如下：
对于任一结点 P：1）若P结点不为空，则将其入栈并且访问该结点，然后将其左孩子置为下个要访问的结点。执行步骤1);2）若P结点为空，则取出栈顶元素，并将其右孩子置为下个要访问的结点，然后循环执行1）。
3）直到P为空，并且栈也为空是，退出循环，即遍历结束。
代码如下：
1 void PreTraversal_Non_Recursive(pBTree T) // 前序非递归遍历 2 { 3 if( T == NULL) 4 return; 5 6 stack<pBTree> st; 7 8 pBTree p = T; 9 while( p!= NULL || !st.empty())10 {11 while( p != NULL) //p不为空时12 {13 cout << p->data_ <<" "; //访问p结点14 st.push(p); //压入栈中15 p = p->left_; //访问其左子树16 }17 18 if( !st.empty() )19 {20 p = st.top();21 st.pop(); //弹出22 p = p->right_;23 }24 }25 }
二叉树的中序非递归遍历:
中序遍历的顺序：”左孩子——根结点——右孩子“；
中序遍历过程和前序类似，其处理过程如下：
对于任一结点 P：1）若P结点不为空，则将其入栈，然后将其左孩子置为下个要访问的结点。执行步骤1);2）若P结点为空，则取出栈顶元素并且访问该结点，并将其右孩子置为下个要访问的结点，然后循环执行1）。3）直到P为空，并且栈也为空是，退出循环，即遍历结束。
代码如下：
1 void InOrder_Traversal_Non_Recursive(pBTree T) //终须遍历(非递归) 2 { 3 if( T == NULL) 4 return; 5 6 stack<pBTree> st; 7 pBTree p = T; 8 9 while( p != NULL || !st.empty())10 {11 while( p != NULL)12 {13 st.push(p);14 p = p->left_;15 }16 17 if( !st.empty())18 {19 p = st.top();20 cout << p->data_ << " ";21 st.pop();22 p = p->right_;23 }24 }25 }
二叉树的后序非递归遍历:
前序遍历的顺序：左孩子——右孩子——根结点“。
后续遍历较为麻烦，因为后续非递归遍历二叉树的顺序是先访问左子树，再访问右子树，最后访问其根结点，当用栈来存储结点是，必须分清返回根结点时，是从左子树返回的，还是从右子树返回的。
思路如下：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任意结点，先将其入栈。
1）如果P不存在左孩子和右孩子，则可以直接访问它；2）P存在左孩子或者右孩子，但是左孩子或者右孩子都已经被访问过了，则同样可以直接访问该结点。3）除此之外，即存在左孩子或者右孩子并且还都没有访问，这时，我们先将其右孩子入栈，然后将左孩子入栈，这样我们就保证了每次取出站定元素的时候，左孩子在右孩子前面 被访问。并且也能保证左孩子或者右孩子能在根结点之前访问。
代码如下：
1 void PostOrder_Traversal_Non_Recursive(pBTree T) //非递归后序遍历 2 { 3 if( T == NULL) 4 return; 5 6 pBTree cur; //当前访问的结点 7 pBTree pre = NULL; //前一次访问的结点 8 stack<pBTree> st; 9 st.push(T);10 11 while( !st.empty())12 {13 cur = st.top();14 15 //当前结点没有孩子结点 或者 当前结点的左孩子或者右孩子已经被访问过 16 if( (cur->left_ == NULL && cur->right_==NULL) || 17 ( pre!= NULL &&(pre ==cur->left_ || pre == cur->right_) ) )18 {19 cout << cur->data_ <<" ";20 st.pop();21 pre = cur;22 }23 else24 {25 if( cur->right_ != NULL)26 st.push(cur->right_);27 if( cur->left_ != NULL)28 st.push(cur->left_);29 }30 }31 }
全部实现代码如下：
1 #include <iostream> 2 #include <string> 3 #include <stack> 4 #include <assert.h> 5 #include <stdlib.h> 6 #include <time.h> 7 using namespace std; 8 const int N =10; 9 10 typedef struct node //二叉树的数据结构 11 { 12 int data_; 13 struct node* left_; 14 struct node* right_; 15 }BTree, *pBTree; 16 17 void Create_Btree_with_arr(pBTree &T, int *arr, int begin, int end)//len俄日数组的长度，也是树的结点数 18 { 19 if(begin > end) 20 return; 21 22 int mid = (begin + end)/2; 23 if( T == NULL) 24 { 25 T =new BTree; //申请空间 26 arr[mid] = rand()%100; 27 cout<< arr[mid] <<" "; 28 T->data_ = arr[mid]; //数值随机化 29 T->left_ = NULL; 30 T->right_ = NULL; 31 } 32 Create_Btree_with_arr(T->left_, arr, begin, mid-1);//左边(不包括T) 33 Create_Btree_with_arr(T->right_, arr, mid+1, end); //右边(不包括T) 34 } 35 36 void PreTraversal_Non_Recursive(pBTree T) // 前序非递归遍历 37 { 38 if( T == NULL) 39 return; 40 41 stack<pBTree> st; 42 43 pBTree p = T; 44 while( p!= NULL || !st.empty()) 45 { 46 while( p != NULL) //p不为空时 47 { 48 cout << p->data_ <<" "; //访问p结点 49 st.push(p); //压入栈中 50 p = p->left_; //访问其左子树 51 } 52 53 if( !st.empty() ) 54 { 55 p = st.top(); 56 st.pop(); //弹出 57 p = p->right_; 58 } 59 } 60 } 61 62 void InOrder_Traversal_Non_Recursive(pBTree T) //终须遍历(非递归) 63 { 64 if( T == NULL) 65 return; 66 67 stack<pBTree> st; 68 pBTree p = T; 69 70 while( p != NULL || !st.empty()) 71 { 72 while( p != NULL) 73 { 74 st.push(p); 75 p = p->left_; 76 } 77 78 if( !st.empty()) 79 { 80 p = st.top(); 81 cout << p->data_ << " "; 82 st.pop(); 83 p = p->right_; 84 } 85 } 86 } 87 88 void PostOrder_Traversal_Non_Recursive(pBTree T) //非递归后序遍历 89 { 90 if( T == NULL) 91 return; 92 93 pBTree cur; //当前访问的结点 94 pBTree pre = NULL; //前一次访问的结点 95 stack<pBTree> st; 96 st.push(T); 97 98 while( !st.empty()) 99 {100 cur = st.top();101 102 //当前结点没有孩子结点 或者 当前结点的左孩子或者右孩子已经被访问过 103 if( (cur->left_ == NULL && cur->right_==NULL) || 104 ( pre!= NULL &&(pre ==cur->left_ || pre == cur->right_) ) )105 {106 cout << cur->data_ <<" ";107 st.pop();108 pre = cur;109 }110 else111 {112 if( cur->right_ != NULL)113 st.push(cur->right_);114 if( cur->left_ != NULL)115 st.push(cur->left_);116 }117 }118 }119 120 void DestructBTree( pBTree &T) //二叉树的销毁121 {122 if( T == NULL)123 return;124 125 DestructBTree( T->left_);126 DestructBTree( T->right_);127 delete T; //free之后的指针成为了野指针，内容并不为空128 T = NULL;//置空129 }130 131 int main(int argc, char const *argv[])132 {133 srand(time(NULL));134 int arr[N]= {0};135 136 pBTree T =NULL;137 Create_Btree_with_arr(T, arr, 0,N-1);138 cout << endl;139 140 PreTraversal_Non_Recursive(T);141 cout << endl;142 143 InOrder_Traversal_Non_Recursive(T);144 cout << endl;145 146 PostOrder_Traversal_Non_Recursive(T);147 cout << endl;148 149 DestructBTree(T);150 cout <<"Free Over" << endl;151 assert( T == NULL); //验证 T 是否真的被释放152 return 0;153 }
完毕。
二叉树的非递归遍历
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。