C++ | 二叉树前序、中序、后序遍历的递归和非递归实现 +层序遍历+深度优先遍历
程序员文章站
2022-05-16 14:21:39
...
二叉树的遍历是学习二叉树最基本却极为重要的一环。当你熟练掌握二叉树的遍历之后,你会发现很多题目都是建立在遍历的基础上来解决的。本文章就是为了盘点一下各种遍历算法的原理和实现。
前序遍历
前序遍历也叫先序遍历(preorder),整个操作过程比较简单,先访问根结点,在访问左子树,左子树访问完之后访问右子树。
- 若二叉树为空,则什么也不做
- 否则:
2.1 访问根结点
2.2. 先序遍历左子树
2.3. 先序遍历右子树
递归实现
void preOrder(BinTree* BT){
if(BT){
printf("%d ", BT->data);
preOrder(BT->left);
preOrder(BT->right);
}
}
非递归实现
void preOrder(TreeNode* root){
if(root == NULL) return;
stack<TreeNode*> S; // 初始化栈
TreeNode* node = root; // 声明遍历指针
while(node || !S.empty()){
if(node != NULL)}{ // 不断访问树的根节点,并且存储左子树(若存在的话)
cout << node->val << " ";
S.push(node);
node = node->left;
}
else{ // 遇到空指针,访问栈顶指针指向的右子树结点
node = S.top()->right;
S.pop();
}
}
}
中序遍历
中序遍历(inorder),整个操作过程也比较简单。
- 若二叉树为空,则什么也不做
- 否则:
2.1 中序遍历左子树
2.2. 访问根结点
2.3. 中序遍历右子树
递归实现
void preOrder(TreeNode* root){
if(root != NULL){
preOrder(root->left);
cout << root->val << " ";
preOrder(root->right);
}
}
非递归实现
void preOrder(TreeNode* root){
if(root == NULL) return;
stack<TreeNode*> S;
TreeNode* node = root;
while(node!=NULL || !S.empty()){
if(node != NULL)}{
// cout << node->val << " "; 先序遍历:在push时访问结点值
S.push(node);
node = node->left;
}
else{
cout << node->val << " "; // 中序遍历:在弹出栈顶指针时访问
node = S.top()->right;
S.pop();
}
}
}
后序遍历
后序遍历(postorder),整个操作过程也比较简单。
- 若二叉树为空,则什么也不做
- 否则:
2.1 后序遍历左子树
2.2. 后序遍历右子树
2.3 访问根结点
后序遍历的递归实现比较容易,而非递归实现则比较难。
递归实现
void preOrder(TreeNode* root){
if(root != NULL){
preOrder(root->left);
preOrder(root->right);
cout << root->val << " ";
}
}
非递归实现
非递归实现比较难,同样的可以使用栈来存储临时值,但是我们需要区分返回根结点时,是从左子树返回还是右子树返回的。
// 先访问左子树,然后访问右子树,再访问根节点
// 使用堆栈来存储结点指针,需要分清返回根结点时是左子树或者右子树
// 我们使用一个辅助指针r来指向最近访问的结点,借助这个指针来区分根节点是从左子树还是右子树返回的。
void postOrder(BiTree* root){
// 初始化一个栈 S
initStack(S);
// 声明一个遍历指针 p
BiTree* p = root;
// 声明一个空的辅助指针
BiTree* r = NULL;
while(p ||! S.empty()){
if(p){ // 非空结点,压栈
push(S, p); // 压栈,走左子树
p = p->left;
}
else{ // 空结点
getTop(S, p); // 取出栈顶结点赋值给p
if(p->right && p->right != r){ // 存在右子树,并且未访问过
p = p->right; // 取右子树根结点,入栈
push(S, p);
p = p->left;
}
else{ // 不存在右子树或者 已经访问完右子树
pop(S, p); // 弹出栈顶指针并赋值给p
visit(p->val); // 访问结点值
r = p; // 记录最近访问的结点
p = NULL; // 将p置为空
}
}
}
}
层序遍历
层序遍历的思路也比较简单易懂,属于广度优先的一种方法,在访问结点之后,我们使用队列来存储一些左右结点指针。
void levelOrder(TreeNode* root){
if(root == NULL) return;
queue<TreeNode*> Q;
Q.push(root);
while(!Q.empty()){
TreeNpde* node = Q.front();
Q.pop();
cout << node->val << " ";
if(node->left != NULL)
Q.push(node->left);
if(node->right != NULL)
Q.push(node->right);
}
}
深度优先遍历
深度优先的思路也不难,思路类似层序遍历,但不同的是使用了栈来存储临时指针。
void depthOrder(TreeNode* root){
if(root == NULL) return;
stack<int> S;
S.push(root);
while(!S.empty()){
TreeNode* node = S.pop();
cout << node->val << " ";
if(node->left != NULL)
S.push(node->left);
if(node->right != NULL)
S.push(node->right);
}
}
上一篇: 二叉树前序,中序,后序遍历的非递归实现
下一篇: 公交车系统的mysql数据库设计