Java数据结构--二叉树

根节点：树中没有父节点的节点叶节点：没有子节点的节点非叶节点：叶节点以外的结点分支度：每个结点拥有的子节点个数，树中最大的分支度即为该树的分支度阶层：根节点阶层为1，其子节点为2，以此类推二叉树可以为空，树不可以（至少要有根节点）二叉树的子树有顺序关系二叉树的分支度必须为0、1、2对于二叉树：叶子节点 = 度数为2的节点+1节点个数 = 叶子节点 + 度数为1的节点 + 度数为2的节点

二叉树结点类：

public class TreeNode { int data; TreeNode left; TreeNode right; public TreeNode(int data) { this.data = data; } public String toString() { return data+" "; } }

二叉树的增删改查：

public class Tree { TreeNode root; TreeNode parent; boolean b; /** * 增加结点 * @param data * @return */ public boolean add(int data) { TreeNode node = new TreeNode(data); if(root == null){ root = node; } else { TreeNode current = root; while (current!=null) { if(data == current.data) { return false; //如果已经存在，直接返回false } else if (data > current.data) { parent = current; //记录要加新结点的父节点 b = true; //记录是左边还是右边 current = current.right; } else if (data < current.data) { parent = current; b = false; current = current.left; } } if(b) { parent.right = node; //如果右子节点为空，就加父节点的右边 } else { parent.left = node; } } return true; } /** * 查询结点 * @param data * @return */ public TreeNode find(int data) { TreeNode current = root; while (current!=null) { if(current.data==data) { return current; }else { parent = current; //记录找到结点的父节点，方便删除操作 if (data > current.data) { current = current.right; b = true; } else if (data < current.data) { current = current.left; b = false; } } } return current; } /** * 删除结点 * @param data * @return */ public boolean delete(int data) { TreeNode current = find(data); if (current == null) { return false; } else if (current.left == null && current.right == null) { if (current == root) { //如果要删除的是根节点 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 = split(current); if (b) { parent.right = temp; }else { parent.left = temp; } } return true; } private TreeNode split(TreeNode current) { TreeNode temp = current.right; TreeNode minRight = temp; //用来记录要删除结点右儿子那边的最小结点 TreeNode parentMinRight = temp; //用来记录要删除结点 的右儿子那边的最小的结点的父节点 while (temp != null) { parentMinRight = minRight; minRight = temp; temp = temp.left; } if(parentMinRight == minRight) { parentMinRight.left = current.left; return parentMinRight; }else { parentMinRight.left = minRight.right; minRight.left = current.left; minRight.right = current.right; return minRight; } } /** * 递归中序遍历有序二叉树 * @param node */ public void print(TreeNode node){ if (node!=null) { print(node.left); System.out.println(node+" "); print(node.right); } } public void printRoot() { print(root); } /** * 修改数据 * @param s * @param m * @return */ public boolean modify(int s, int m) { //修改数据 = 先删除 在增加 delete(s); return add(m); } }

测试代码：

public class Test { public static void main(String[] args) { Tree t = new Tree(); t.add(5); t.add(7); t.add(3); t.add(9); t.printRoot(); t.delete(7); t.printRoot(); } }

运行结果：

3 5 7 9 3 5 9