Java 数据结构 二叉树

简介

与前面所介绍循序表以及链表的结构所不同，树结构是一种描述非线性层次关系的数据结构。
其主要有一下几个特点：

• 在一个树结构中，有且仅有一个结点没有直接前驱，那这个结点就是树的根结点
• 除了根结点外，其余结点有且仅有一个直接前驱
• 每个结点可以有n个直接后驱（二叉树最多只有两个）
  而在树结构中，二叉树是最简单的一种形式。在研究树结构时，二叉树是树结构内容中的重点。二叉树的描述、处理相对简单，而且更重要的是，任意的树都可以转为二叉树，因此，二叉树是所有树的基础。

二叉树 结构图

二叉树遍历算法

主要有以下三种：

• 先序遍历
• 中序遍历
• 后序遍历
  
  
  

Java代码实现

/**
 * 二叉树结构
 * Created by Sheldon on 2019/4/3.
 * Project Name: alstudy.
 * Package Name: tree.
 */

// 二叉树结构
public class ChainTree {

    // 结点数据
    String data;
    // 左子树
    ChainTree leftTree;
    // 右子树
    ChainTree rightTree;
    // 二叉树根结点
    ChainTree root;

    /**
     * 初始化二叉树，向根结点插入数据
     * @param data
     */
    ChainTree(String data){
        this.data = data;
        this.root = this;
    }

    public static ChainTree bulieTree(String[] datas, int index){
        ChainTree node = null;
        if (index<datas.length){
            String value = datas[index];
            if (value=="#"){
                return null;
            }
            node = new ChainTree(value);
//            node.leftTree = bulieTree(datas, 2*index+1);
//            node.rightTree = bulieTree(datas,2*index+2);
            node.addLeftTree(bulieTree(datas, 2*index+1));
            node.addRightTree(bulieTree(datas,2*index+2));
            return node;
        }
        return node;
    }

    /**
     * 添加左子树
     * @return
     */
    public void addLeftTree(ChainTree node){
        leftTree = node;
    }

    /**
     * 添加右子树
     * @return
     */
    public void addRightTree(ChainTree node){
        rightTree = node;
    }

    /**
     * 先序遍历
     * @param root
     */
    public void DLR(ChainTree root){
        ChainTree node = root;
        if (node!=null){
            System.out.printf(node.data+", ");
            DLR(node.leftTree);
            DLR(node.rightTree);
        }
    }

    /**
     * 中序遍历
     * @param root
     */
    public void LDR(ChainTree root){
        ChainTree node = root;
        if (node!=null){
            LDR(node.leftTree);
            System.out.printf(node.data+", ");
            LDR(node.rightTree);
        }
    }

    /**
     * 后序遍历
     * @param root
     */
    public void LRD(ChainTree root){
        ChainTree node = root;
        if (node!=null){
            LRD(node.leftTree);
            LRD(node.rightTree);
            System.out.printf(node.data+", ");
        }
    }

    /**
     * 二叉树深度
     * @param node
     * @return
     */
    public int depth(ChainTree node){
        int depleft, depright;
        if (node==null){
            return 0;
        }else {
            depleft = depth(node.leftTree);
            depright = depth(node.rightTree);
            if (depleft>depright){
                return depleft+1;
            }else {
                return depright+1;
            }
        }
    }

    public static void main(String[] args) {
        String[] datas = new String[]{"0","1","2","3","4","5","6","7","8","9","10"};
        // 构建双叉树
        ChainTree chainTree = bulieTree(datas,0);
        // 先序遍历（中->左->右）
        chainTree.DLR(chainTree.root);
        System.out.println();
        // 中序遍历（左->右->中）
        chainTree.LDR(chainTree.root);
        System.out.println();
        // 后序遍历（左->右->中）
        chainTree.LRD(chainTree.root);
        System.out.println();
        // 二叉树深度
        System.out.println(chainTree.depth(chainTree.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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

运行结果：