1 package iYou.neugle.tree;
2
3 import java.util.ArrayList;
4 import java.util.List;
5
6 public class Binary_Tree<T> {
7 private Tree tree = new Tree();
8
9 class Tree {
10 public T data;
11 public Tree left;
12 public Tree right;
13 }
14
15 public enum Direction {
16 left, right
17 }
18
19 // 生成根节点
20 public void CreateRoot(T data) {
21 this.tree.data = data;
22 }
23
24 // 插入节点到指定位置
25 public boolean Insert(T parentData, T data, Direction direction) {
26 if (this.TreeIsEmpty()) {
27 System.out.println("树暂无节点，请先创建树");
28 return false;
29 }
30 return this.InsertNode(this.tree, parentData, data, direction);
31 }
32
33 private boolean InsertNode(Tree TreeNode, T parentData, T data,
34 Direction direction) {
35 if (TreeNode == null) {
36 return false;
37 }
38 if (TreeNode.data.equals(parentData)) {
39 Tree t = new Tree();
40 t.data = data;
41 if (direction == Direction.left) {
42 if (TreeNode.left == null) {
43 TreeNode.left = t;
44 return true;
45 } else {
46 System.out.println("该节点的左节点不为空!");
47 }
48 } else {
49 if (TreeNode.right == null) {
50 TreeNode.right = t;
51 return true;
52 } else {
53 System.out.println("该节点的右节点不为空!");
54 }
55 }
56 return false;
57 }
58
59 boolean b = InsertNode(TreeNode.left, parentData, data, direction);
60
61 if (!b) {
62 return InsertNode(TreeNode.right, parentData, data, direction);
63 } else {
64 return b;
65 }
66
67 }
68
69 // 获取二叉树深度
70 public int Deep() {
71 return this.TreeDeep(this.tree);
72 }
73
74 private int TreeDeep(Tree tree) {
75 int leftLen = 0;
76 int rightLen = 0;
77 if (tree == null) {
78 return 0;
79 }
80 leftLen = this.TreeDeep(tree.left);
81 rightLen = this.TreeDeep(tree.right);
82 if (leftLen > rightLen) {
83 return leftLen + 1;
84 } else {
85 return rightLen + 1;
86 }
87 }
88
89 // 判断二叉树是否为空
90 public boolean TreeIsEmpty() {
91 if (this.tree.data != null) {
92 return false;
93 }
94 return true;
95 }
96
97 // 根据值查找节点
98 public Tree Query(T data) {
99 return QueryTreeByValue(this.tree, data);
100 }
101
102 private Tree QueryTreeByValue(Tree tree, T data) {
103 if (tree == null) {
104 return null;
105 }
106 if (tree.data.equals(data)) {
107 System.out.println("----------");
108 System.out.println("查找到该节点，节点左子树为:"
109 + (tree.left == null ? "无" : tree.left.data));
110 System.out.println("查找到该节点，节点右子树为:"
111 + (tree.right == null ? "无" : tree.right.data));
112 System.out.println("----------");
113 return tree;
114 }
115 Tree t = QueryTreeByValue(tree.left, data);
116 if (t == null) {
117 return QueryTreeByValue(tree.right, data);
118 } else {
119 return t;
120 }
121 }
122
123 // 清空二叉树
124 public void ClearTree() {
125 this.tree = null;
126 }
127
128 // 先序遍历
129 public void DLR() {
130 this.Tree_DLR(this.tree);
131 }
132
133 private void Tree_DLR(Tree tree) {
134 if (tree == null) {
135 return;
136 }
137 System.out.println(tree.data);
138 this.Tree_DLR(tree.left);
139 this.Tree_DLR(tree.right);
140 }
141
142 // 中序遍历
143 public void LDR() {
144 this.Tree_LDR(this.tree);
145 }
146
147 private void Tree_LDR(Tree tree) {
148 if (tree == null) {
149 return;
150 }
151 this.Tree_LDR(tree.left);
152 System.out.println(tree.data);
153 this.Tree_LDR(tree.right);
154 }
155
156 // 后序遍历
157 public void LRD() {
158 this.Tree_LRD(this.tree);
159 }
160
161 private void Tree_LRD(Tree tree) {
162 if (tree == null) {
163 return;
164 }
165 this.Tree_LRD(tree.left);
166 this.Tree_LRD(tree.right);
167 System.out.println(tree.data);
168 }
169
170 // 层次遍历
171 public void Level() {
172 List<Tree> list = new ArrayList<Tree>();
173 list.add(this.tree);
174 while (!list.isEmpty()) {
175 Tree left = list.get(0).left;
176 Tree right = list.get(0).right;
177 if (left != null) {
178 list.add(left);
179 }
180 if (right != null) {
181 list.add(right);
182 }
183 System.out.println(list.get(0).data);
184 list.remove(0);
185 }
186 }
187 }
