avatar

二叉树的遍历

二叉树的遍历方式有很多,今天就来一一列举并且实现一下。
二叉树基本遍历分别用递归和非递归的方式进行实现,层序遍历我们需要使用一下栈和队列,所有的代码使用Java实现

前期工作

  • 我们需要创建一个二叉树类
public class TreeNode {
public int value;
public TreeNode left;
public TreeNode right;
public TreeNode(int value)
{
this.value = value;
}
}
  • 准备一个二叉树的插入算法,方便进行遍历的检验,插入的时候构建一个二叉查找树(至于啥是二叉查找树,请自行百度)
public class TreeNodeTool {
//传入参数为二叉树的根节点,要插入的值,这里创建的是一个二叉查找树,
public static TreeNode InsertTreeNode(TreeNode root,int value)
{
if(root==null)//如果根节点是空的那么创建一个;
{
root = new TreeNode(value);
}
else
{
TreeNode p = root;
TreeNode parent = null;
while (p!=null)
{
if(value < p.value)
{
parent = p;
p=p.left;
}
else if(value>p.value)
{
parent = p;
p = p.right;
}
else
{
return root;
}
}
if (value < parent.value)
{
parent.left = new TreeNode(value);
}
else
{
parent.right = new TreeNode(value);
}
}
return root;
}
}

前序遍历(DLR)

前序遍历就是先遍历根节点,然后前序遍历右子树,前序遍历左子树
定义里面就包含着递归的思想,但是任何递归都可以写成迭代的方式,所以以下提供两种方式进行前序遍历的编写

递归形式

public  static void PreorderRecur(TreeNode root)
{
if(root==null) return;
else
{
System.out.print(root.value+ " ");//先遍历根节点
PreorderRecur(root.left);//前序遍历左子树
PreorderRecur(root.right);//前序遍历右子树
}
}

非递归形式

利用栈来实现循环,首先跟节点入栈,进入while循环,循环条件是栈不为空,循环内,

  • 根节点出栈输出
  • 右子树入栈
  • 左子树入栈
  • 这样输出的时候就能够实现前序遍历
public  static void PreorderRecur(TreeNode root)
{
if(root!=null)
{
Stack<TreeNode> s = new Stack<>();
s.push(root);
while (!s.empty())
{
TreeNode node = s.peek();//取栈顶元素但是不出栈
System.out.print(s.pop().value + " ");//输出栈顶元素
if(node.right!=null)
{
s.push(node.right);//右子树根节点入栈
}
if(node.left!=null)
{
s.push(node.left);//左子树根节点入栈
}
}
}
}

中序遍历 (LDR)

前序遍历就是中遍历左子树,然后根节点,中序遍历右子树

递归方式

public  static void InorderRecur(TreeNode root)
{
if(root==null) return;
else
{
InorderRecur(root.left);//中序遍历左子树
System.out.print(root.value+ " ");//中遍历根节点
InorderRecur(root.right);//中序遍历右子树
}
}

非递归方式

循环条件(栈不空||根节点不空){ 如果(根不空) 根入栈 根节点指向左子树 否则 根节点指向栈顶 出栈输出 根节点指向右子树}
所谓中序遍历,就是先遍历左子树,然后根节点,最后中序遍历右子树,所以我们应该先去让跟节点入栈,然后遍历左子树,当左子树的左边是空的了,那我们可以让右边入栈,并且输出根节点

public  static void InorderRecur(TreeNode root)
{
if(root!=null)
{
Stack<TreeNode> s = new Stack<>();
while (!s.empty()||root!=null)
{
if(root!=null)
{
s.push(root);
root = root.left;
}
else
{
root = s.pop();
System.out.print(root.value+" ");
root = root.right;

}
}
}
}

后序遍历(LRD)

后序遍历就是后序遍历左子树,后序遍历右子树,随后遍历根节点

递归方式

public  static void PostorderRecur(TreeNode root)
{
if(root==null) return;
else
{
PostorderRecur(root.left);//后序遍历左子树
PostorderRecur(root.right);//后序遍历右子树
System.out.print(root.value+ " ");//后遍历根节点
}
}

非递归形式

后序遍历比较麻烦 这里提供两种方式实现 分别使用两个栈和一个栈来实现

第一种两个栈实现

根入栈1 循环条件(栈1不空){ 根节点指向栈1顶 出栈 根入栈2 (左子树)先(右子树)入栈1} 循环条件(栈2不空){ 栈2出栈输出}
例如{1,2,3,4,5,6,7}这个树,我们一步一步看看是实现的

s1 s2 操作 root
1 null s1根节点入栈,s2没有,初始化后进入循环 1
1 null s1根节点入栈,s2没有,初始化后进入循环 1
null 1 s1弹出根节点,s2保存, 1
2,3 1 s1压入根节点左右两个子节点 1
2 1,3 s1弹出栈顶3,s2压入3 3
2,6,7 1,3 s1压入root左右子节点,s2不动 3
2,6 1,3,7 s1弹出7,s2压入7 7
2 1,3,7,6 7左右都没有,所以s1弹出6,s2压入6 6
null 1,3,7,6,2 6也是叶子节点,所以s1弹出2,s2压入2 2
4,5 1,3,7,6,2 2下面有4,5所以s1压入4,5 2
4 1,3,7,6,2,5 s1弹出5,s2压入5 5
null 1,3,7,6,2,5,4 因为4,5是叶子节点,所以都压入s2

依次弹出s2:4,5,2,6,7,3,1.至此分析完毕
这里我真的想知道一件事,想出这种方法的人的脑子怎么长得,真的厉害啊

public  static void PostorderRecur(TreeNode root)
{
if(root!=null)
{
Stack<TreeNode> s1 = new Stack<>();
Stack<TreeNode> s2 = new Stack<>();
s1.push(root);
while (!s1.empty())
{
root = s1.pop();
s2.push(root);
if(root.left!=null) s1.push(root.left);
if(root.right!=null) s1.push(root.right);
}
while(!s2.empty())
{
System.out.print(s2.pop().value);
}
}
}

利用一个栈实现后序遍历

根入栈 新建节点指针cur等于NULL 循环条件(栈不空){ cur=栈顶 如果(cur左子树非空&&根不为cur左子树&&根不为cur右子树) cur左子树入栈 如果(cur右子树非空&&根不为cur右子树) cur右子树入栈 否则 出栈输出 根节点等于cur}

  • 这里的root更像一个标记值
  • root所指的位置意味着其本身包括其子节点都已被访问
  • 当root为某个节点的左节点时 表示这个节点的左节点已被访问
  • 当root为某个节点的右节点时 表示这个节点的左节点和右节点都已被访问
    这种方法也是牛逼的不行啊。
public  static void PostorderRecur(TreeNode root)
{
if(root!=null)
{
Stack<TreeNode> s = new Stack<>();
s.push(root);
TreeNode cur = null;
while (!s.empty())
{
cur = s.peek();
if(cur.left!=null && root!=cur.left && root !=cur.right)
{
s.push(cur.left);
}
else if(cur.right!=null && cur.right!=root)
{
s.push(cur.right);
}
else
{
System.out.print(s.pop().value+" ");
root = cur;
}
}
}
}

层序遍历(BFS)–广度优先遍历

广度优先遍历是利用队列实现的
这个直接看代码理解去来还是比较快的

public  static void Sequence(TreeNode root)
{
if(root!=null)
{
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.offer(root);
while (!q.isEmpty())
{
root = q.poll();
System.out.print(root.value+" ");
if(root.left!=null)
{
q.offer(root.left);
}
if(root.right!=null)
{
q.offer(root.right);
}
}
}
}

神级遍历 Morris算法

当树的节点数为N时 遍历的时间复杂度O(N) 额外空间复杂度O(1),空间复杂度是1,一听就够牛逼的
这种方法没有使用函数栈(递归)和栈(非递归) 降低了空间复杂度 主要是利用了叶子节点的right为NULL 利用两个指针 让某个节点的左子树的最右边的结点的right指向自己本身 进行遍历后 又会将right赋NULL 不会改变树的结构.
前序节点:给定某个节点,在中序遍历中,直接排在它前面的节点,我们称之为该节点的前序节点

前序遍历

  • 如果当前节点的左子节点为空时,输出当前节点,并将当前节点置为该节点的右子节点;
  • 如果当前节点的左子节点不为空,找到当前节点左子树的最右节点(该节点为当前节点中序遍历的前驱节点);
  • 1、如果最右节点的右指针为空(right=null),将最右节点的右指针指向当前节点,并输出当前节点(在此处输出),当前节点置为其左子节点;
  • 2、如果最右节点的右指针不为空,将最右节点右指针重新置为空(恢复树的原状),并将当前节点置为其右节点;
  • 重复1~2,直到当前节点为空。
public  static void MorrisPre(TreeNode root)
{
if(root!=null)
{
TreeNode cur1 = root;
TreeNode cur2 = null;
while (cur1!=null)
{
cur2 = cur1.left;
if(cur2!=null)
{
while (cur2.right!=null && cur2.right!=cur1)
{
cur2 = cur2.right;//这里就是找到了当前节点的前序节点,即当前节点的左孩子的右孩子
}
if(cur2.right == null)
{
cur2.right = cur1;//如果前序节点的右孩子为空,那么把前序节点的右孩子指向当前节点
System.out.print(cur1.value+" ");
cur1 = cur1.left;
continue;
}
else
{
cur2.right = null;
}
}
else
{
System.out.print(cur1.value+" ");
cur1 = cur1.right;
}
}
}
}

中序遍历

  • 如果当前节点的左子节点为空时,输出当前节点,并将当前节点置为该节点的右子节点;
  • 如果当前节点的左子节点不为空,找到当前节点左子树的最右节点(该节点为当前节点中序遍历的前驱节点);
  • 1、如果最右节点的右指针为空(right=null),将最右节点的右指针指向当前节点,当前节点置为其左子节点;
  • 2、如果最右节点的右指针不为空,将最右节点右指针重新置为空(恢复树的原状),输出当前节点,并将当前节点置为其右节点;
  • 重复1~2,直到当前节点为空。
public  static void MorrisIn(TreeNode root)
{
if(root!=null)
{
TreeNode cur1 = root;
TreeNode cur2 = null;
while (cur1!=null)
{
cur2 = cur1.left;
if(cur2!=null)
{
while (cur2.right!=null && cur2.right!=cur1)
{
cur2 = cur2.right;
}
if(cur2.right==null)
{
cur2.right = cur1;
cur1 = cur1.left;
continue;
}
else
{
cur2.right = null;
}
}
System.out.print(cur1.value+" ");
cur1 =cur1.right;
}
}
}

后序遍历

后序遍历较前两者比较麻烦,需要建立一个临时节点,并令该节点的左子节点为root,并且需要一个子过程,倒序输出某两个节点之间路径上的各个节点。

  • 如果当前节点的左子节点为空时,则将其右子节点作为当前节点;
  • 如果当前节点的左子节点不为空,找到当前节点左子树的最右节点(该节点为当前节点中序遍历的前驱节点);
  • 1、如果最右节点的右指针为空(right=null),将最右节点的右指针指向当前节点,当前节点置为其左子节点;
  • 2、如果最右节点的右指针不为空,将最右节点右指针重新置为空(恢复树的原状),倒序输出从当前节点的左子节点到该最右节点路径上的所有节点,并将当前节点置为其右节点;
  • 重复1~2,直到当前节点为空。
//前面类似,没有什么区别
public static void MorrisPost(TreeNode root)
{
if(root!=null)
{
TreeNode cur1 = root;
TreeNode cur2 = null;
while (cur1!=null)
{
cur2 = cur1.left;
if(cur2!=null)
{
while (cur2.right!=null && cur2.right!=cur1)
{
cur2 = cur2.right;
}
if(cur2.right==null)
{
cur2.right = cur1;
cur1 = cur1.left;
continue;
}
else
{
cur2.right = null;
printEdge(cur1.left);
}
}
cur1 =cur1.right;
}
printEdge(root);
}
}
//倒序输出从当前节点的左子节点到该最右节点路径上的所有节点
static void printEdge(TreeNode root)
{
TreeNode tail = reverseEdge(root);
TreeNode cur = tail;
while (cur != null)
{
System.out.print(cur.value+" ");
cur = cur.right;
}
reverseEdge(tail);//再倒叙回去
}
//将form的右子树倒序排列,类似于反转链表
static TreeNode reverseEdge(TreeNode from)
{
TreeNode pre = null;
TreeNode next = null;
while (from != null)
{
next = from.right;//右子树赋给next
from.right = pre;//将pre给form的右子树
pre = from;//再将整个赋给pre,这样pre就有了包括上一次循环的pre加上form的根节点
from = next;
}
return pre;
}
文章作者: zenshin
文章链接: https://zlh.giserhub.com/2020/03/13/ckbbo2j5d004vpkwa3tbhba28/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 zenshin's blog
打赏
  • 微信
    微信
  • 支付宝
    支付宝

评论