小丑西瓜9

这个屌丝很懒，什么也没留下！

热门标签

二叉树及其遍历方式+代码_补充代码实现二叉树遍历的各项操作。

作者：小丑西瓜9 | 2024-06-14 03:06:57

踩

补充代码实现二叉树遍历的各项操作。

二叉树及其遍历方式

1、树型结构及基本概念
- 1.1 树型结构概念
- 1.2 一些重要概念
2. 二叉树及基本概念

1、树型结构及基本概念

1.1 树型结构概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
树型结构的特点

子树不相交
除根节点外，每个节点有且仅有一个父节点
一颗N个节点的树有N-1条边

1.2 一些重要概念

在这里插入图片描述

节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A节点的度为6
树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为6
叶子节点或终端节点：度为0的节点称为叶节点；如上图：B、C、H、I…等节点为叶节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的孩子节点
根结点：一棵树中，没有双亲结点的结点；如上图：A
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次；如上图：树的高度为4
非终端节点或分支节点：度不为0的节点；如上图：D、E、F、G…等节点为分支节点
兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C是兄弟节点
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
森林：由m（m>=0）棵互不相交的树的集合称为森林
在这里插入图片描述

2. 二叉树及基本概念

2.1 二叉树概念

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
二叉树的特点：

每个结点最多有两棵子树，即二叉树不存在度大于 2 的结点。
二叉树的子树有左右之分，其子树的次序不能颠倒，因此二叉树是有序树。

2.2 两种特殊的二叉树

1. 满二叉树: 一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。
结论：

如果一个满二叉树的层数为K，则结点总数是2^k - 1 ，反之也成立。
满二叉树第K层节点个数为2^(k-1)
满二叉树的边长=结点个数-1

2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。
结论：

完全二叉树中，若存在度为1的结点，则有且只有一个，且只有左子树，没有右子树
完全二叉树与满二叉树结点编号一一对应

2.3 二叉树的性质

若规定根节点的层数为1，则一棵非空二叉树的第k层上最多有2^(k-1) (k>0)个结点,满二叉树的情况。
若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大结点数是2^k - 1 (k>=0)
对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1
具有n个结点的完全二叉树的深度k为log2(n+1) 上取整
根结点从1开始编号，设父节点编号为k,则左子树2k,右子树2k+1
根结点从0开始编号，设父节点编号为k,则左子树2k+1,右子树2k+2
若子节点编号为k,父节点编号为k/2

2.4 二叉树的存储

二叉树的存储结构分为：顺序存储和类似于链表的链式存储
二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式，具体如下：

// 孩子表示法
class Node {
 int val; // 数据域
 Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
 Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class Node {
 int val; // 数据域
 Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
 Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
 Node parent; // 当前节点的根节点
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.5 二叉树的基本操作

1.前序遍历:访问根结点—>递归访问根的左子树—>递归访问根的右子树。(根左右)
2.前序遍历:根的左子树—>根节点—>根的右子树。（左根右）
3.前序遍历:根的左子树—>根的右子树—>根节点。（左右根）
在这里插入图片描述
前序遍历结果：ABDEHCFG
前序特点：前序遍历结果集中，第一个输出的一定是当前树的根节点
中序遍历结果：DBEHAFCG
中序特点：中序遍历结果中，左子树的遍历结果在根节点的左侧，右子树的的遍历结果在根的右侧
后序遍历结果：DHEBFGCA
后序特点：后序遍历结果中，最后一个输出根节点
注：

根据前序和中序遍历结果可以还原一个二叉树
将后序遍历结果反转与前序遍历结果对比：
后序遍历转置：ACGFBEHD
前序遍历： ABDEHCFG
后续转置恰好是前序遍历的镜像：根右左
创建上图二叉树代码

package bin_tree;
/**
 * 基础二叉树实现
 * 左右孩子表示法
 */
public class MyBinTree {
    private static class TreeNodes{
        char val; // 节点值
        TreeNodes left; // 左子树根节点
        TreeNodes right;  // 右子树根节点
        // 构造方法
        public TreeNodes(char val) {
            this.val = val;
        }
    }
    /**
     * 创建一个二叉树，返回根节点
     */
    public static TreeNodes build(){
        // 创建8个节点
        TreeNodes nodeA=new TreeNodes('A');
        TreeNodes nodeB=new TreeNodes('B');
        TreeNodes nodeC=new TreeNodes('C');
        TreeNodes nodeD=new TreeNodes('D');
        TreeNodes nodeE=new TreeNodes('E');
        TreeNodes nodeF=new TreeNodes('F');
        TreeNodes nodeG=new TreeNodes('G');
        TreeNodes nodeH=new TreeNodes('H');
        // 将这8个节点进行连接
        nodeA.left=nodeB;
        nodeA.right=nodeC;
        nodeB.left=nodeD;
        nodeB.right=nodeE;
        nodeE.right=nodeH;
        nodeC.left=nodeF;
        nodeC.right=nodeG;
        return nodeA;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

2.5.1 前序遍历代码——递归和非递归实现（根左右）

递归实现

/**
     * 先序遍历二叉树，传入一个二叉树的根节点，就可以按照先序遍历的方式遍历节点
     * 根左右
     * @param root
     */
 public static void preOrder(TreeNodes root){
        // 判空
        if(root==null){
            return;
        }
        // 输出根节点
        System.out.println(root.val + " ");
        // 递归左子树
        preOrder(root.left);
        // 递归右子树
        preOrder(root.right);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

前序遍历代码——非递归实现（根左右）

package bin_tree.leetcode;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
/**
 * 前序遍历 非递归实现
 */
class Num144_preOrderTraversal {
    // 将节点值存储在List集合中
    List<Character> ret = new ArrayList<>();

    public List<Character> preorderTraversal(TreeNode root) {
        // 1.判空
        if (root == null) {
            return ret;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            // 先访问根节点
            ret.add(cur.val);
            // 压入右孩子
            if (cur.right != null) {
                stack.push(cur.right);
            }
            // 压入左孩子
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
        return ret;
    }
    /**
     * 创建一个二叉树，返回根节点
     */
    public static TreeNode build() {
        // 创建8个节点
        TreeNode nodeA = new TreeNode('A');
        TreeNode nodeB = new TreeNode('B');
        TreeNode nodeC = new TreeNode('C');
        TreeNode nodeD = new TreeNode('D');
        TreeNode nodeE = new TreeNode('E');
        TreeNode nodeF = new TreeNode('F');
        TreeNode nodeG = new TreeNode('G');
        TreeNode nodeH = new TreeNode('H');
        // 将这8个节点进行连接
        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeE.right = nodeH;
        nodeC.left = nodeF;
        nodeC.right = nodeG;
        return nodeA;
    }
    public static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;
        TreeNode() {
        }
        TreeNode(char val) {
            this.val = val;
        }
        TreeNode(char val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public static void main(String[] args) {
        TreeNode root = build();
        Num144_preOrderTraversal a = new Num144_preOrderTraversal();
        System.out.println(a.preorderTraversal(root));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

2.5.2 中序遍历代码——递归和非递归实现（根左右）

中序遍历——递归实现（左根右）

 /**
     * 中序遍历二叉树，传入一个二叉树的根节点，就可以按照中序遍历的方式遍历节点
     * 左根右
     * @param root
     */
    public static void inOderTraversal(TreeNodes root){
        // 判空
        if(root==null){
            return;
        }
        // 递归左子树
        inOderTraversal(root.left);
        // 输出根节点
        System.out.println(root.val + " ");
        // 递归右子树
        inOderTraversal(root.right);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

中序遍历——非递归实现

package bin_tree.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 中序遍历 非递归实现
 */
class Num94_InorderTraversal {
    // 将节点值存储在List集合中
    List<Character> ret = new ArrayList<>();

    public List<Character> inorderTraversal(TreeNode root) {
        // 1.判空
        if (root == null) {
            return ret;
        }
        // 当前走到的节点
        TreeNode cur=root;
        Deque<TreeNode> stack = new ArrayDeque<>();
       while(cur!=null || !stack.isEmpty()){
           // 访问左子树，一直走到最底
           while(cur!=null){
               stack.push(cur);
               cur=cur.left;
           }
           // 此时已经走到左子树为空的位置
           cur=stack.pop();
           ret.add(cur.val);
           // 继续访问右子树
           cur=cur.right;
       }
        return ret;
    }

    /**
     * 创建一个二叉树，返回根节点
     */
    public static TreeNode build() {
        // 创建8个节点
        TreeNode nodeA = new TreeNode('A');
        TreeNode nodeB = new TreeNode('B');
        TreeNode nodeC = new TreeNode('C');
        TreeNode nodeD = new TreeNode('D');
        TreeNode nodeE = new TreeNode('E');
        TreeNode nodeF = new TreeNode('F');
        TreeNode nodeG = new TreeNode('G');
        TreeNode nodeH = new TreeNode('H');
        // 将这8个节点进行连接
        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeE.right = nodeH;
        nodeC.left = nodeF;
        nodeC.right = nodeG;
        return nodeA;
    }

    public static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(char val) {
            this.val = val;
        }

        TreeNode(char val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        TreeNode root = build();
        Num94_InorderTraversal a = new Num94_InorderTraversal();
        System.out.println(a.inorderTraversal(root));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

2.5.3 后序遍历代码——递归和非递归实现（根左右）

后序遍历：左右根
传入一个二叉树的根节点，就可以按照中序遍历的方式遍历节点

 /**
     * 后序遍历：左右根
     * 传入一个二叉树的根节点，就可以按照中序遍历的方式遍历节点
     */
    public static void postOderTraversal(TreeNodes root){
        // 判空
        if(root==null){
            return;
        }
        // 递归左子树
        postOderTraversal(root.left);
        // 递归右子树
        postOderTraversal(root.right);
        // 输出根节点
        System.out.println(root.val + " ");
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

后续遍历——非递归实现（左右根）

package bin_tree.leetcode;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
/**
 * 后序遍历 非递归实现
 */
    class Num145_PostorderTraversal {
    // 将节点值存储在List集合中
    List<Character> ret = new ArrayList<>();

    public List<Character> postorderTraversal(TreeNode root) {
        // 1.判空
        if (root == null) {
            return ret;
        }
        // 当前走到的节点
        TreeNode cur=root;
        // 上一个完全访问的节点（左右根都处理完了）
        TreeNode prev=null;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while(cur!=null || !stack.isEmpty()){
            // 访问左子树，一直走到最底
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            // 此时已经走到左子树为空的位置,cur取栈顶元素
            cur=stack.pop();
            // 判断右树是否为空，或者被访问过
            if (cur.right==null||prev==cur.right){
                ret.add(cur.val);
                // 当前节点cur就是最后处理的根节点，更新prev引用，变为cur节点
                prev=cur;
                cur=null;
            }else{
                //此时右树不为空且没有处理过，将根节点压入栈中继续处理右子树
                stack.push(cur);
                cur=cur.right;
            }
        }
        return ret;
    }

    /**
     * 创建一个二叉树，返回根节点
     */
    public static TreeNode build() {
        // 创建8个节点
        TreeNode nodeA = new TreeNode('A');
        TreeNode nodeB = new TreeNode('B');
        TreeNode nodeC = new TreeNode('C');
        TreeNode nodeD = new TreeNode('D');
        TreeNode nodeE = new TreeNode('E');
        TreeNode nodeF = new TreeNode('F');
        TreeNode nodeG = new TreeNode('G');
        TreeNode nodeH = new TreeNode('H');
        // 将这8个节点进行连接
        nodeA.left = nodeB;
        nodeA.right = nodeC;
        nodeB.left = nodeD;
        nodeB.right = nodeE;
        nodeE.right = nodeH;
        nodeC.left = nodeF;
        nodeC.right = nodeG;
        return nodeA;
    }

    public static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(char val) {
            this.val = val;
        }

        TreeNode(char val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        TreeNode root = build();
        Num145_PostorderTraversal a = new Num145_PostorderTraversal();
        System.out.println(a.postorderTraversal(root));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

完整代码+测试

package bin_tree;
/**
 * 基础二叉树实现
 * 左右孩子表示法
 */
public class MyBinTree {
    private static class TreeNodes{
        char val; // 节点值
        TreeNodes left; // 左子树根节点
        TreeNodes right;  // 右子树根节点
        // 构造方法
        public TreeNodes(char val) {
            this.val = val;
        }
    }
    /**
     * 创建一个二叉树，返回根节点
     */
    public static TreeNodes build(){
        // 创建8个节点
        TreeNodes nodeA=new TreeNodes('A');
        TreeNodes nodeB=new TreeNodes('B');
        TreeNodes nodeC=new TreeNodes('C');
        TreeNodes nodeD=new TreeNodes('D');
        TreeNodes nodeE=new TreeNodes('E');
        TreeNodes nodeF=new TreeNodes('F');
        TreeNodes nodeG=new TreeNodes('G');
        TreeNodes nodeH=new TreeNodes('H');
        // 将这8个节点进行连接
        nodeA.left=nodeB;
        nodeA.right=nodeC;
        nodeB.left=nodeD;
        nodeB.right=nodeE;
        nodeE.right=nodeH;
        nodeC.left=nodeF;
        nodeC.right=nodeG;
        return nodeA;

    }
    /**
     * 先序遍历二叉树，传入一个二叉树的根节点，就可以按照先序遍历的方式遍历节点
     * 根左右
     * @param root
     */
    public static void preOrder(TreeNodes root){
        // 判空
        if(root==null){
            return;
        }
        // 输出根节点
        System.out.print(root.val + " ");
        // 递归左子树
        preOrder(root.left);
        // 递归右子树
        preOrder(root.right);
    }
    /**
     * 中序遍历二叉树，传入一个二叉树的根节点，就可以按照中序遍历的方式遍历节点
     * 左根右
     * @param root
     */
    public static void inOderTraversal(TreeNodes root){
        // 判空
        if(root==null){
            return;
        }
        // 递归左子树
        inOderTraversal(root.left);
        // 输出根节点
        System.out.print(root.val + " ");
        // 递归右子树
        inOderTraversal(root.right);
    }
    /**
     * 后序遍历：左右根
     * 传入一个二叉树的根节点，就可以按照中序遍历的方式遍历节点
     */
    public static void postOderTraversal(TreeNodes root){
        // 判空
        if(root==null){
            return;
        }
        // 递归左子树
        postOderTraversal(root.left);
        // 递归右子树
        postOderTraversal(root.right);
        // 输出根节点
        System.out.print(root.val + " ");
    }
    public static void main(String[] args) {
        TreeNodes root=build();
        System.out.print("前序遍历结果为:");
        preOrder(root);
        System.out.println();
        System.out.print("中序遍历结果为:");
        inOderTraversal(root);
        System.out.println();
        System.out.print("后序遍历结果为:");
        postOderTraversal(root);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/716014