欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

二叉树的遍历

程序员文章站 2022-06-14 22:01:47
public class BinaryTree> { /** * 根结点 */ private TreeNode root; /** * 是否通过前序及中序遍历来初始化 */ private boolean initByPreInOrder; public BinaryTree(boolean initByPreInOrder) {...

遍历二叉树(Traversing binary tree)

概念:是指从根节点出发,按照某种次序依次访问二叉树中所有的结点,使得每个结点被访问一次且仅被访问一次。

遍历方式:

  • 前序遍历
  • 中序遍历
  • 后序遍历
  • 层序遍历

树结点:

public class TreeNode{
    
    public int data;
	public TreeNode lChlid;
	public TreeNode rChild;
    
    public TreeNode(int data) {
        this.data = data;
    }
}

1、前序遍历

规则是若树为空,则空操作返回,否则先访问根结点,然后前序遍历左子树,再前序遍历右子树
二叉树的遍历
遍历顺序:ABDHKECFIGJ

public void preOrderTraverse(TreeNode node) {
    if (node == null) 
        return;
    System.out.println(node.data + " ");
    preOrderTraverse(node.lChild);
    preOrderTraverse(node.rChild);
}

2、中序遍历

规则是若树为空,则空操作返回,否则从根结点开始(并不是先访问根结点),中序遍历根结点的左子树,然后是访问根结点,最后中序遍历右子树
二叉树的遍历
遍历顺序:HKDBEAIFCGJ

public void inOrderTraverse(TreeNode node) {
    if (node == null) 
        return;
    inOrderTraverse(node.lChild);
    System.out.println(node.data + " ");
    inOrderTraverse(node.rChild);
}

3、后序遍历

规则是若树为空,则空操作返回,否则从左到右先叶子后结点的方式遍历访问左右子树,最后是访问根结点
二叉树的遍历
遍历顺序:KHDEBIFJGCA

public void postOrderTraverse(TreeNode node) {
    if (node == null)
        return;
    
    postOrderTraverse(node.lChild);
    postOrderTraverse(node.rChild);
    System.out.println(node.data + " ");
}

4、层序遍历

规则是若树为空,则空操作返回,否则从树的第一层,也就是根结点开始访问,从上而下逐层遍历,在同一层中,按从左到右的顺序对结点逐个访问

本文地址:https://blog.csdn.net/weixin_44431550/article/details/107592212