数据结构与算法 - 二叉树的遍历
二叉树的节点
二叉树的节点定义
template <class T> class BTNode{ public: T value; // 关键字 (键值) BSTNode *left; // 左孩子 BSTNode *right; // 右孩子 BSTNode(T v, BTNode *l = nullptr, BTNode *r = nullptr): value(v),left(l),right(r) {} };
二叉树的遍历
二叉树的遍历,有三种方法:
- 递归法
- 栈迭代法
- MORRIS 迭代法
下面我们分别分析下三种方法:
递归法
三种方式中,递归法最好理解,具体实现如下:
前序遍历(递归法)
template <class T> void BSTree<T>::BTPreOrder(BSTNode<T>& node) const { if(node == nullptr) return; cout << node->value << " " ; BTPreOrder(node->left); BTPreOrder(node->right); }
中序遍历(递归法)
template <class T> void BSTree<T>::BTPMidOrder(BSTNode<T>& node) const { if(node == nullptr) return; BTPMidOrder(node->left); cout << node->value << " " ; BTPMidOrder(node->right); }
后序遍历(递归法)
template <class T> void BSTree<T>::BTPostOrder(BSTNode<T>& node) const { if(node == nullptr) return; BTPostOrder(node->left); BTPostOrder(node->right); cout << node->value << " " ; }
栈迭代法
前序遍历(栈迭代法)
template <class T> void BSTree<T>::BTPreOrder(BSTNode<T>& node) { stack<TreeNode*> nodeStack; BSTNode<T>* node = root; while (node || !nodeStack.empty()) { if (node) { nodeStack.push(node); cout << node->value << " " ; node = node->left; } else { node = nodeStack.top(); nodeStack.pop(); node = node->right; } } }
中序遍历(栈迭代法)
template <class T> void BSTree<T>::BTMidOrder(BSTNode<T>& node) { stack<TreeNode*> nodeStack; BSTNode<T>* node = root; while (node || !nodeStack.empty()) { if (node) { nodeStack.push(node); node = node->left; } else { node = nodeStack.top(); cout << node->value << " " ; nodeStack.pop(); node = node->right; } } }
MORRIS 迭代法
#ifdef PRO_ORDER BSTree<T>* BSTree<T>::rightReverse(BSTree<T>* root) { BSTree<T>* head = nullptr; while (root) { BSTree<T>* next = root->right; root->right = head; head = root; root = next; } return head; } void BSTree<T>::printEdge (BSTree<T>* root) { root = rightReverse(root); BSTree<T>* head = root; while (head != NULL) { result.push_back(head->val); head = head->right; } root = rightReverse(root); } #endif void BSTree<T>::BSTOrder() { if (node == nullptr) return; BSTNode<T>* node = root; while (node) { if (node->left) { /* 如果存在左子树,则需要设置索引 */ BSTNode<T>* index = node->left; while(index->right && index->right != node) { index = index->right; } if (!index->right) { /* 首次寻找到索引,设置索引,继续遍历左子树 */ #ifdef PRE_ORDER cout <<node->value << " " ; #endif index->right = node; node = node->left; } else { /* 非首次寻找到索引,说明左子树遍历完成,根据索引去遍历右子树 */ #ifdef MID_ORDER cout <<node->value << " " ; #endif node = node->right; /* 恢复索引 */ index->right = nullptr; #ifdef PRO_ORDER printEdge(root); #endif } } else { /* 没有左子树 遍历右子树 */ #ifndef PRO_ORDER cout <<node->value << " " ; #endif node = node->right; } #ifdef PRO_ORDER printEdge(root); #endif } }