二叉树的三种遍历

二叉树的三种遍历：前序、中序、后序。包括递归和非递归的

前序遍历：root节点在最前。root节点、左子节点，右子节点

递归：

1 //前序递归 2 void preOrder1(TreeNode* root) 3 { 4 if (root == NULL) return; 5 cout << root->val << " "; //root的输出在最前面 6 preOrder1(root->left); 7 preOrder1(root->right); 8 }

非递归：

1 //前序非递归 2 void preOrder2(TreeNode* root) 3 { 4 if (root == NULL) return; 5 stack<TreeNode*> stk; 6 while (root != NULL || !stk.empty()) 7 { 8 while (root != NULL) 9 { 10 stk.push(root); 11 cout << root->val << " "; // root的输出在前面 12 root = root->left; 13 } 14 if (!stk.empty()) 15 { 16 root = stk.top(); 17 stk.pop(); 18 root = root->right; 19 } 20 } 21 }

 

中序遍历：root在中间。左子节点、root节点、右子节点

递归：

1 //中序递归 2 void midOrder1(TreeNode* root) 3 { 4 if (root == NULL) return; 5 midOrder1(root->left); 6 cout << root->val << " "; //root的输出在中间 7 midOrder1(root->right); 8 }

非递归：

1 //中序非递归 2 void midOrder2(TreeNode* root) 3 { 4 if (root == NULL) return; 5 stack<TreeNode*> stk; 6 while (root != NULL || !stk.empty()) 7 { 8 while (root != NULL) 9 { 10 stk.push(root); 11 root = root->left; 12 } 13 if (!stk.empty()) 14 { 15 root = stk.top(); 16 cout << root->val << " "; //root输出在中间，无左子节点后 17 stk.pop(); 18 root = root->right; 19 } 20 } 21 }

 

后序遍历：root在最后。左子节点、右子节点、root节点。

递归：

1 //后序递归 2 void postOrder1(TreeNode* root) 3 { 4 if (root == NULL) return; 5 postOrder1(root->left); 6 postOrder1(root->right); 7 cout << root->val << " "; //root的输出在最后 8 }

非递归：

1 //后序非递归 2 void postOrder2(TreeNode* root) 3 { 4 if (root == NULL) return; 5 stack<TreeNode*> stk; 6 stk.push(root); 7 TreeNode* pre = NULL; 8 TreeNode* cur = NULL; 9 while (!stk.empty()) //root!=NULL??最后一步时，root!=NULL但是程序已结束，变的的cur 不是root 10 { 11 cur = stk.top(); 12 if ((cur->left == NULL && cur->right == NULL) || (pre != NULL && (pre == cur->left || pre == cur->right))) ////如果当前结点没有孩子结点或者孩子节点都已被访问过 13 { 14 cout << cur->val << " "; 15 pre = cur; 16 stk.pop(); 17 } 18 else 19 { 20 if (cur->right) 21 stk.push(cur->right); 22 if (cur->left) 23 stk.push(cur->left); 24 } 25 } 26 }

　　观察可以发现，对于递归的解法，三种遍历很相似，唯一的不同点就是，输出节点的位置。

　　　　前序遍历：输出节点在最前面。中序遍历：输出节点在中间。后序遍历：输出节点在最后。

　　对于非递归则是用栈来实现。首先判断节点是否为空。最终要的是判断循环条件。如果条件不正确，事倍功半

转载于:https://www.cnblogs.com/zhuzhu2016/p/5852416.html

相关资源：二叉树三种遍历动画演示