首页 > 代码库 > 二叉树的遍历
二叉树的遍历
二叉树的存储结构：
1 struct BinaryTreeNode {2 int val;3 BinaryTreeNode *left;4 BinaryTreeNode *right;5 6 BinaryTreeNode(int v = int(), BinaryTreeNode *l = NULL, BinaryTreeNode *r = NULL): 7 val(v), left(l), right(r){}8 };
前序遍历：
根节点->左子树->右子树
递归方法：
1 void PreOrder(BinaryTreeNode* root) {2 if (root != NULL) {3 std::cout<<root->val；4 PreOrder(root->left);5 PreOrder(root->right);6 }7 }
迭代方法：
1 void PreOrder(BinaryTreeNode* root) { 2 BinaryTreeNode* p = root; 3 std::stack<BinaryTreeNode*> s; 4 5 while (p!= NULL || !s.empty()) { 6 if (p != NULL) { 7 std::cout<<p->val; 8 s.push(p); 9 p = p->left;10 } else {11 p = s.top();12 s.pop();13 p = p->right;14 }15 }16 }
中序遍历：
左子树->根节点->右子树
递归方法：
1 void InOrder(BinaryTreeNode *root) {2 if (root != NULL) {3 InOrder(root->left);4 std::cout<<p->val;5 InOrder(root->right);6 7 }8 }
迭代方法：
1 void Inorder(BinaryTreeNode* root) { 2 BinaryTreeNode* p = root; 3 std::stack<BinaryTreeNode*> s; 4 5 while (p != NULL || !s.empty()) { 6 if (p != NULL) { 7 s.push(p); 8 p = p->left; 9 } else {10 p = s.top();11 std::cout<<p->val;12 s.pop();13 p=p->right;14 }15 }16 }
后序遍历：
左子树->根节点->右子树
递归方法：
1 void Postorder(BinaryTreeNode* root) {2 if (root != NULL) {3 PostorderRecur(root->left);4 PostorderRecur(root->right);5 std::cout<<root->val;6 }7 }
迭代方法：
因为后序非递归遍历二叉树的顺序是先访问左子树，再访问右子树，最后访问根节点。当用栈来保存节点，必须分清返回根节点时，是从左子树返回的，还是从右子树返回的。所以，使用辅助指针r，其指向最近访问过的节点。
1 void BinaryTree::Postorder() { 2 BinaryTreeNode* p = root; 3 BinaryTreeNode* r = NULL; 4 std::stack<BinaryTreeNode*> s; 5 6 while (p!= NULL && !s.empty()) { 7 if (p != NULL) { 8 s.push(p); 9 p = p->left;10 } else {11 p = s.top();12 if (p->right != NULL && p->right != r) {13 p = p->right;14 s.push(p);15 p = p->left;16 } else {17 s.pop();18 std::cout<<p->val<<" ";19 r = p;20 p = NULL;21 }22 }23 }24 }
层次遍历：
1 void Levelorder() { 2 BinaryTreeNode *p = root; 3 std::queue<BinaryTreeNode*> q; 4 5 if (p != NULL) { 6 q.push(p); 7 } 8 9 while (!q.empty()) {10 p = q.front();11 q.pop();12 std::cout<<p->val;13 14 if (p->left != NULL) {15 q.push(p->left);16 }17 if (p->right != NULL) {18 q.push(p->right);19 }20 }21 }
二叉树的遍历
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。