Java实现简单的二叉树

布满荆棘的人生 2022-08-04 10:51 129阅读 0赞

package test;  
  
  
public class Tree \{  
  
  
/\*\*  
\* @param args  
\*/  
TreeNode root;  
TreeNode parent;  
boolean b;  
  
  
public static void main(String\[\] args) \{  
// TODO Auto-generated method stub  
Tree t = new Tree();  
t.add(5);  
t.add(7);  
t.add(9);  
t.add(1);  
t.p();  
System.out.println();  
t.modify(3, 18);  
t.delete(9);  
t.p();  
\}  
  
  
public boolean add(int d) \{  
// 增加数据的方法  
TreeNode jd = new TreeNode(d);  
if (root == null) \{  
// 如果根节点为空，那么把新节点加给根节点  
root = jd;  
\} else \{  
TreeNode current = root;  
while (current != null) \{  
// 试找到一个位置加新节点  
if (d == current.data) \{  
// 如果已经存在，则直接返回false，表示加失败  
return false;  
  
  
\} else if (d > current.data) \{  
// 如果改制大于当前节点，那么应该往右边找  
parent = current;  
b = true;  
current = current.right;  
\} else if (d < current.data) \{  
parent = current;  
b = false;  
current = current.left;  
\}  
\}  
if (b) \{  
// 如果是右儿子为空，就加父节点的右边  
parent.right = jd;  
\} else \{  
parent.left = jd;  
\}  
\}  
return true;  
\}  
  
  
public TreeNode find(int d) \{  
// 查询的方法  
TreeNode current = root;  
while (current != null) \{  
if (current.data == d)  
return current;  
else \{  
// 记录找到节点的父节点，以方便删除操作  
parent = current;  
if (d > current.data) \{  
current = current.right;  
b = true;  
\} else if (d < current.data) \{  
current = current.left;  
b = false;  
\}  
\}  
\}  
return current;  
\}  
  
  
public boolean delete(int d) \{  
TreeNode current = find(d);  
if (current == null) \{  
return false;  
\} else if (current.left == null && current.right == null) \{  
// 如果要删除的节点是叶节点  
if (current == root) \{  
// 如果是根节点，直接让根节点==null  
root = null;  
  
  
\} else if (b) \{  
parent.right = null;  
\} else \{  
parent.left = null;  
\}  
\} else if (current.left == null) \{  
// 如果有删除节点只有右节点  
if (b) \{  
parent.right = current.right;  
\} else \{  
parent.left = current.right;  
\}  
\} else if (current.right == null) \{  
// 如果删除节点只有左节点  
if (b) \{  
// 该变量记录了要删除的节点，在其父节点的左边还是右边  
parent.right = current.left;  
\} else \{  
parent.left = current.left;  
\}  
\} else \{  
TreeNode temp = fenlie(current);  
// 分裂节点  
if (b)  
parent.right = temp;  
else  
parent.left = temp;  
\}  
return true;  
\}  
  
  
public TreeNode fenlie(TreeNode c) \{  
TreeNode temp = c.right;  
TreeNode p = temp;// 用来记录要删除几点右儿子那边的最小节点  
TreeNode pp = temp;// 用来记录要删除节点右儿子那边的最小节点的父节点  
while (temp != null) \{  
// 找到要删除节点右边儿子那边的最小节点  
pp = p;  
p = temp;  
temp = temp.left;  
\}  
if (pp == p) \{  
// 如果删除节点的右儿子节点没有左儿子  
// 把删除节点的左儿子加到删除节点的右儿子的左边  
pp.left = c.left;  
return pp;  
\} else \{  
pp.left = p.right;// 把找到的节点的右儿子部分加到该节点父节点的左边  
p.left = c.left;// 把删除节点的左儿子加到分裂节点的左边  
p.right = c.right;// 把删除节点的右儿子加到分裂节点的右边  
return p;  
\}  
\}  
  
  
public boolean modify(int s, int m) \{  
// 修改数据的方法=先删除后增加，这样还是有顺序的  
delete(s);  
return add(m);  
\}  
  
  
public void print(TreeNode jd) \{  
// 递归中序遍历该有序二叉树  
if (jd != null) \{  
print(jd.left);  
System.out.print(jd + " ");  
print(jd.right);  
\}  
\}  
  
  
public void p() \{  
print(root);  
\}

package test;  
  
  
public class TreeNode \{  
  
  
/\*\*  
\* @param args  
\*/  
int data;  
TreeNode left;  
TreeNode right;  
  
  
public TreeNode(int data) \{  
this.data = data;  
\}  
  
  
public String toString() \{  
return data + "";  
\}  
  
  
\}