遇到一个二叉树遍历的问题,使用递归实现,绕了好久没想明白,晚上回来,在纸上一通笔画,算是弄明白了,记录下。
#include <iostream>using namespace std;
struct point { int val; struct point * left; struct point * right;};
void ite_recurse_left(struct point * root){ //递归终止条件,左节点不存在 if (root->left == NULL) { cout << root->val << " "; return; } ite_recurse_left(root->left); //左节点遍历结束,输出父节点值 cout << root->val << " "; //将父节点的右节点作为一个新的节点,继续递归(当把右节点看成一个"节点"而非"右节点"时,就通了) ite_recurse_left(root->right);}
void ite_recurse_right(struct point * root){ if (root->right == NULL) { cout << root->val << " "; return; } ite_recurse_right(root->right); cout << root->val << " "; ite_recurse_right(root->left);}
void ite_recurse_mid(struct point * root){ if (root->right == NULL && root->left == NULL) { cout << root->val << " "; return; } cout << root->val << " "; ite_recurse_mid(root->left); ite_recurse_mid(root->right);}
int main() { struct point p1; struct point p2; struct point p3; struct point p4; struct point p5; struct point p6; struct point p7; struct point p8; struct point p9;
p1.val = 1; p1.left = &p2; p1.right = &p3;
p2.val = 2; p2.left = &p4; p2.right = &p5;
p3.val = 3; p3.left = &p6; p3.right = &p7;
p4.val = 4; p4.left = NULL; p4.right = NULL;
p5.val = 5; p5.left = &p8; p5.right = &p9;
p6.val = 6; p6.left = NULL; p6.right = NULL;
p7.val = 7; p7.left = NULL; p7.right = NULL;
p8.val = 8; p8.left = NULL; p8.right = NULL;
p9.val = 9; p9.left = NULL; p9.right = NULL;
// cout << p1.val << endl;// cout << p1.left->val << endl;// cout << p1.right->val << endl;
cout << "left : "; ite_recurse_left(&p1); cout << endl; cout << "right : "; ite_recurse_right(&p1); cout << endl; cout << "mid : "; ite_recurse_mid(&p1); cout << endl;}
20150729@前海花园
评论