二叉树遍历（先序，中序，后续）图解 java实现

- 日理万妓 2023-05-31 03:00 16阅读 0赞

### 先序遍历 ###

###### 规则： 树根 -> 左侧树 -> 右侧树5 ######

### 中序遍历 ###

###### 规则： 左侧树 -> 树根 -> 右侧树 ######

### 后序遍历 ###

###### 规则： 左侧树 -> 右侧树 -> 树根 ######

![image][]

先序遍历
    8,3,1,6,4,7,10,14,13, 
    中序遍历
    1,3,4,6,7,8,10,13,14,
    后序遍历
    1,4,7,6,3,13,14,10,8,

### 图解 ###

#### 先序 ####

![image][image 1]

#### 中序 ####

![image][image 2]

#### 后序 ####

![image][image 3]

### 说明 ###

#### 先序 ####

1.  由树根“8”开始。找到“8”
2.  ”8“的左侧树，找到“3”。
3.  “3”的左侧树，找到“1”。“1”没有左侧也没有右侧。
4.  “3”的右侧树，找到“6”。
5.  “6”的左侧树，找到“4”。“4”没有左侧也没有右侧。
6.  “6”的右侧树，找到“7”。”7“没有左侧也没有右侧。
7.  ”8“的右侧树，找到”10“
8.  “10”的左侧树没有，右侧，找到“14”
9.  “14“的左侧树，找到”13“，没有右侧

#### 中序 ####

1.  由“8”开始，左侧“3”，“3”的左侧“1”,"1"没有左侧，然后根据（左侧，根，右侧原则），找到根“1”，然后“1”没有右侧节点。
2.  “1”的根节点“3”，找到“3”
3.  “3”右侧“6”，“6”的左侧“4”，“4没有左侧”，找到“4”，“4”没有右侧
4.  “4”的根节点“6”，找到“6”
5.  “6”的右侧“7”，“7”没有左侧，找到“7”。“7”没有右侧
6.  “3”的根节点“8”，找到“8”
7.  “8”的右侧“10”，“10”没有左侧，找到“10”
8.  “10”的右侧“14”，“14”有左侧“13”。“13”没有左侧，找到“13”。“13”没有右侧
9.  “13”的根节点“14”，找到“14”。“14”没有右侧

#### 后序 ####

1.  由“8”开始，左侧“3”，“3”的左侧“1”,"1"没有左侧也没有右侧，找到根“1”
2.  “1”的右侧兄弟节点“6”，“6”有左侧节点“4”，“4”没有左侧也没有右侧，找到“4”
3.  “4”的右侧兄弟节点“7”，“7”没有左侧也没有右侧。找到“7”
4.  然后根据（左右根）的原则。找到“4”和“7”的根“6”。找到“6”
5.  然后根据（左右根）的原则。找到“1”和“6”的根“3”。找到“3”
6.  “3”的右侧兄弟节点“10”，“10没有左侧”，右侧“14”，“14”有左侧“13”。13没有子节点。找到“13”
7.  “13”没有右侧兄弟节点，找到“13”的根节点“14”。找到“14”
8.  “14”的根节点“10”，找到“10”
9.  “3”和“10”的根节点“8”，找到“8”

![image][image 4]

先序遍历
    A,B,C,D,E,F,G,H,K,
    中序遍历
    B,D,C,A,E,H,G,K,F,
    后序遍历
    D,C,B,H,K,G,F,E,A,

### java 实现 ###

#### 二叉树节点实体 ####

package com.liuzhiqiang.domain;
    
    public class NodeTree { 
    
        /** * 根节点值 */
        private String value;
    
        /** * 左节点 */
        private NodeTree leftNodeTree;
    
        /** * 右节点 */
        private NodeTree rightNodeTree;
    
        public NodeTree(String value) { 
            this.value = value;
        }
    
        public String getValue() { 
            return value;
        }
    
        public void setValue(String value) { 
            this.value = value;
        }
    
        public NodeTree getLeftNodeTree() { 
            return leftNodeTree;
        }
    
        public void setLeftNodeTree(NodeTree leftNodeTree) { 
            this.leftNodeTree = leftNodeTree;
        }
    
        public NodeTree getRightNodeTree() { 
            return rightNodeTree;
        }
    
        public void setRightNodeTree(NodeTree rightNodeTree) { 
            this.rightNodeTree = rightNodeTree;
        }
    }

#### 实现 ####

package com.liuzhiqiang.test;
    
    import com.liuzhiqiang.domain.NodeTree;
    
    public class Traversal { 
    
        public static void main(String[] a) { 
            // 新建一颗二叉树
            NodeTree nodeTree = establishNodeTree();
    
            // 先序遍历
            System.out.println("先序遍历");
            preorder(nodeTree);
            // 中序
            System.out.println();
            System.out.println("中序遍历");
            lnr(nodeTree);
            // 后序
            System.out.println();
            System.out.println("后序遍历");
            houxu(nodeTree);
        }
    
        // 后序： 左树->右树->根
        static void houxu(NodeTree nodeTree) { 
            if (nodeTree.getLeftNodeTree() != null) { 
                houxu(nodeTree.getLeftNodeTree());
            }
    
            if (nodeTree.getRightNodeTree() != null) { 
                houxu(nodeTree.getRightNodeTree());
            }
    
            System.out.print(nodeTree.getValue() + ",");
    
        }
    
        // 中序： 左树 -> 根 -> 右树
        static void lnr(NodeTree nodeTree) { 
            if (nodeTree.getLeftNodeTree() != null) { 
                lnr(nodeTree.getLeftNodeTree());
            }
            System.out.print(nodeTree.getValue() + ",");
            if (nodeTree.getRightNodeTree() != null) { 
                lnr(nodeTree.getRightNodeTree());
            }
        }
    
        // 先序： 根节点->左子树->右子树
        static void preorder(NodeTree nodeTree) { 
            System.out.print(nodeTree.getValue() + ",");
            if (nodeTree.getLeftNodeTree() != null) { 
                preorder(nodeTree.getLeftNodeTree());
            }
            if (nodeTree.getRightNodeTree() != null) { 
                preorder(nodeTree.getRightNodeTree());
            }
    
        }
    
        static NodeTree establishNodeTree() { 
            // 根节点
            NodeTree nodeTree = new NodeTree("8");
            // 左侧1
            NodeTree leftNode1 = new NodeTree("3");
            nodeTree.setLeftNodeTree(leftNode1);
            // 右侧1
            NodeTree rightNodeTree1 = new NodeTree("10");
            nodeTree.setRightNodeTree(rightNodeTree1);
    
            // 左侧2
            NodeTree leftNode2 = new NodeTree("1");
            leftNode1.setLeftNodeTree(leftNode2);
            // 右侧2
            NodeTree rightNodeTree2 = new NodeTree("6");
            leftNode1.setRightNodeTree(rightNodeTree2);
    
            // 左侧3
            NodeTree leftNode3 = new NodeTree("4");
            rightNodeTree2.setLeftNodeTree(leftNode3);
    
            // 右侧3
            NodeTree rightNodeTree3 = new NodeTree("7");
            rightNodeTree2.setRightNodeTree(rightNodeTree3);
    
            // 右侧4
            NodeTree rightNodeTree4 = new NodeTree("14");
            rightNodeTree1.setRightNodeTree(rightNodeTree4);
    
            // 左侧4
            NodeTree leftNode4 = new NodeTree("13");
            rightNodeTree4.setLeftNodeTree(leftNode4);
    
    // NodeTree nodeTree = new NodeTree("A");
    //
    // NodeTree nodeTreeB = new NodeTree("B");
    //
    // NodeTree nodeTreeE = new NodeTree("E");
    //
    // nodeTree.setLeftNodeTree(nodeTreeB);
    // nodeTree.setRightNodeTree(nodeTreeE);
    //
    // NodeTree nodeTreeC = new NodeTree("C");
    // nodeTreeB.setRightNodeTree(nodeTreeC);
    //
    // NodeTree nodeTreeD = new NodeTree("D");
    // nodeTreeC.setLeftNodeTree(nodeTreeD);
    //
    // NodeTree nodeTreeF = new NodeTree("F");
    // nodeTreeE.setRightNodeTree(nodeTreeF);
    //
    // NodeTree nodeTreeG = new NodeTree("G");
    // nodeTreeF.setLeftNodeTree(nodeTreeG);
    //
    // NodeTree nodeTreeH = new NodeTree("H");
    // nodeTreeG.setLeftNodeTree(nodeTreeH);
    //
    // NodeTree nodeTreeK = new NodeTree("K");
    // nodeTreeG.setRightNodeTree(nodeTreeK);
            return nodeTree;
        }
    }

[image]: /images/20230531/872b6e4ba9cc4e14909bdc87d54f9d9b.png
[image 1]: /images/20230531/dd2274a2099e4fd0aa111b6a0470f804.png
[image 2]: /images/20230531/4be9678c10fe4e92bc1df4555e936409.png
[image 3]: /images/20230531/afdb2b06a2c84c4b838aa609a514a30b.png
[image 4]: /images/20230531/71aee7e8e182405091c92864b8479f9f.png