中序遍历—–二叉查找树的遍历(迭代版,不使用栈或者队列)

企鹅博客
企鹅博客
企鹅博客
30163
文章
0
评论
2020年9月14日18:28:00 评论 7 views 2602字阅读8分40秒

二叉查找树(Binary Search Tree)的遍历的方法有很多,通常使用的是递归的遍历,其便于理解,但是使用递归的话会造成程序运行的空间浪费,效率并不高。为此可以使用一个栈来模拟递归的过程,实现迭代版的二叉查找树的遍历。但是会使用到额外的存储空间,虽说在运行效率上比递归版的有所提高,但是额外的存储空间还是一定的浪费。但是如何减少额外的存储空间呢?我们知道二叉查找树是可以转换为一个双向环形链表(二叉查找树与双向环形链表的转化),而链表的遍历是不需要额外的空间的,因此我们可以考虑通过充分利用树的节点的两个指针来优化遍历的过程。

二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉树先序中序非递归算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

轻松搞定面试中的二叉树题目 http://www.linuxidc.com/linux/2014-07/104857.htm

我们都知道在中序遍历的过程中,我们需要用一个栈来存储之前访问过的节点,主要是为了找到当前节点的后继节点,为此我们发现如下图所示的规律。

中序遍历-----二叉查找树的遍历(迭代版,不使用栈或者队列)

上图可以看出节点1的后继节点为2,节点2的后继节点为3,节点3的后继节点为4,节点4的后继节点为5,由上述描述可以发现当某个右节点没有右孩子时,其后继节点为其祖父,当其有右孩子时,其后继节点为其右孩子。当某个左节点没有右孩子时,其后继节点为其父亲,反之其后继节点为其右孩子。

从这段寻找后继节点的过程发现,其后继节点的位置与其是否存在右孩子有关,也即与其指向右侧的指针有关,因此我们是否可以使用右指针来指定其后继节点呢?答案是可以的。下图所示为使用右指针指向其后继节点后构成的新的图。

中序遍历-----二叉查找树的遍历(迭代版,不使用栈或者队列)

构造上图之后我们再一次遍历二叉查找树时,只需先向左找到第一个不存在左孩子的节点,然后依次打印其key值,打印完之后遍历其右孩子,则其遍历的路径如下图所示

中序遍历-----二叉查找树的遍历(迭代版,不使用栈或者队列)

从上图可以看出这样处理之后刚好实现了二叉查找树的中序遍历。下面为代码的具体实现。

构建一颗二叉查找树

node* create(const string& s)
{
 node* res = new node;
 res->left = nullptr;
 res->right = nullptr;
 res->s = s;
 return res;
}
node* insert(node* root, const string& s)
{
 if(root == nullptr)
 {
  root = create(s);
  return root;
 }
 node* temp = root;
 while(temp!=nullptr)
 {
  if(temp->s > s)
  {
   if(temp->left == nullptr)
   {
    temp->left = create(s);
    return root;
   }
   else
    temp = temp->left;
  }
  else
  {
   if(temp->right == nullptr)
   {
    temp->right = create(s);
    return root;
   }
   temp = temp->right;
  }
 }
}

遍历二叉查找树

void in_order_traverse_BST(node* root)
{
 node* cur = root;
 node* pre=nullptr;
 while(cur!=nullptr)
 {
  if(cur->left == nullptr)
  {
   cout<<cur->s<<" ";
   cur = cur->right;
  }
  else
  {
   pre = cur->left;
   while(pre->right != nullptr && pre->right != cur)
    pre = pre->right;
   if(pre->right == nullptr)
   {
    pre->right = cur;
    cur = cur->left;
   }
   else
   {
    cout<<cur->s<<" ";
    pre->right = nullptr;
    cur = cur->right;
   }
  }
 }
}

下面这段代码是创建右链接,以及恢复原来树的形状的代码,若有什么不明白的地方可以画一颗树来具体实现就行。

else
  {
   pre = cur->left;
   while(pre->right != nullptr && pre->right != cur)
    pre = pre->right;
   if(pre->right == nullptr)
   {
    pre->right = cur;
    cur = cur->left;
   }
   else
   {
    cout<<cur->s<<" ";
    pre->right = nullptr;
    cur = cur->right;
   }
  }

测试代码

#include <iostream>
#include <string>
#include <fstream>
using namespace std;
struct node
{
 string s;
 node* left;
 node* right;
};
node* insert(node* root, const string& s);
void in_order_traverse_BST(node* root);
void main()
{
 ifstream in("data.txt");
 if(!in.good())
 {
  cout<<"error"<<endl;
  exit(0);
 }
 node* root = nullptr;
 while (!in.eof())
 {
  string s;
  in>>s;
  root = insert(root,s);
 }
 in_order_traverse_BST(root);
}

继续阅读
weinxin
欢迎加入中国站长博客之家
本站的所有资源都会上传分享到博客之家,希望大家互相学习交流进步。
关于 Python 字符串 Linux编程

关于 Python 字符串

字符串 字符串的处理是编译语言中不可缺少的部分,特别是在输入输出的时候,Python字符串的处理比较多样,便捷。 一.字符串拼接 Python字符串的拼接结合了Java和C语言的形式,但是形式上多了很...
Java数组及其内存分配 Linux编程

Java数组及其内存分配

几乎所有的程序设计语言都支持数组。Java也不例外。当我们需要多个类型相同的变量的时候,就考虑定义一个数组。在Java中,数组变量是引用类型的变量,同时因为Java是典型的静态语言,因此它的数组也是静...
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: