Java数据结构与算法（四）二叉树的遍历

本是古典何须时尚 2021-09-26 22:00 244阅读 0赞

# 一、前序遍历 #

先访问根节点，然后前序遍历左子树，然后前序遍历右子树：  
二叉树的定义、插入和查找见上篇博客：[二叉树的定义、插入和查找][Link 1]

class Tree{
        TreeNode root = null;
        public void QianXuBianLi(TreeNode treenode) {
            if( treenode != null ) {
                System.out.print(treenode.value+" ");
                QianXuBianLi(treenode.leftChild);
                QianXuBianLi(treenode.rightChild);
            }
        }

测试代码：

public class TreeDemo {
        public static void main(String[] args) {
            Tree tree = new Tree();
            TreeNode node1 = new TreeNode(6);
            TreeNode node2 = new TreeNode(4);
            TreeNode node3 = new TreeNode(3);
            TreeNode node4 = new TreeNode(1);
            TreeNode node5 = new TreeNode(5);
            TreeNode node6 = new TreeNode(9);
            TreeNode node7 = new TreeNode(10);
            TreeNode node8 = new TreeNode(8);
            tree.insert(node1);
            tree.insert(node2);
            tree.insert(node3);
            tree.insert(node4);
            tree.insert(node5);
            tree.insert(node6);
            tree.insert(node7);
            tree.insert(node8);
            tree.QianXuBianLi(node1);
        }
    }

分析：  
（1）插入完成之后的二叉树如下：  
![这里写图片描述][70]  
（2）分析前序遍历：  
![这里写图片描述][70 1]  
（3）运行结果：  
6 4 3 1 5 9 8 10

# 二、中序遍历 #

先前序遍历左子树，然后访问根节点，然后前序遍历右子树：

public void ZhongXuBianLi(TreeNode treenode) {
            if( treenode != null ) {    
                ZhongXuBianLi(treenode.leftChild);
                System.out.print(treenode.value+" ");
                ZhongXuBianLi(treenode.rightChild);
            }
    }

运行结果：  
1 3 4 5 6 8 9 10  
![这里写图片描述][70 2]

# 三、后序遍历 #

先前序遍历左子树，然后前序遍历右子树，然后访问根节点：

public void HouXuBianLi(TreeNode treenode) {
            if( treenode != null ) {    
                HouXuBianLi(treenode.leftChild);
                HouXuBianLi(treenode.rightChild);
                System.out.print(treenode.value+" ");
            }
        }

运行结果：  
1 3 5 4 8 10 9 6

[Link 1]: https://blog.csdn.net/weixin_41835916/article/details/80647764
[70]: /images/20210923/8ad0899a39cc414fb884af15f46b177e.png
[70 1]: /images/20210923/3971f49399f9405e8621d2fcaa7a68d2.png
[70 2]: /images/20210923/e5857af3a6f04a2a99b72cfaa4a22cb3.png