请选择 进入手机版 | 继续访问电脑版
查看: 898|回复: 2

[Java语言] 二叉树部分功能实现(JAVA)

3万

主题

3万

帖子

10万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
100197
发表于 2016-8-13 15:18:54
主要实现了二叉树的一般用法,可能会有些错误,还望纠正一下。
  1. package structure.tree;
  2. public class Node {
  3. public int idata;
  4. public double ddata;
  5. public Node leftNode;
  6. public Node rightNode;
  7. public Node() {
  8. }
  9. public void display() {// отй╬╫з╣Ц
  10. System.out.print('{');
  11. System.out.print(idata);
  12. System.out.print(',');
  13. System.out.print(ddata);
  14. System.out.print('}');
  15. }
  16. }
复制代码
[code]package structure.tree; import java.util.Stack; public class Tree { /* 节点属性, 树是由节点构成的 */ private Node root; public Tree() { root = null; } /** * 查找指定key值的树节点 * * @param key * @return */ public Node find(int key) { Node current = root; while(current.idata != key) { if(key < current.idata) current = current.leftNode; else current = current.rightNode; if(current == null) return null; } return current; } /** * 往树结构插入指定节点 * 说明: 插入成功返回true,插入失败返回false * * @param key * @param data * @return */ public boolean insert(int key, double data) { boolean flag = true; boolean isLeftNode = false; Node node = new Node(); node.idata = key; node.ddata = data; Node parent = new Node(); if(root == null) root = node; else { Node current = root; while(current != null) { parent = current; if(current.idata > key) { isLeftNode = true; current = current.leftNode; } else if(current.idata < key) { isLeftNode = false; current = current.rightNode; } else flag = false; }// 结束while循环 }// 结束else条件 if((flag == true) && isLeftNode) parent.leftNode = node; else if((flag == true) && !isLeftNode) parent.rightNode = node; return flag; } /** * 删除树中的指定节点 * 说明:删除成功返回true,删除失败或者没找到则返回false * 算法: * |-- 找到要删除的节点 * |-- 删除叶节点 * |-- 删除只有一个子节点的节点 * |-- 删除有两个子节点的节点 * * @param key * @return */ public boolean delete(int key) { boolean flag = true; boolean isLeftNode = false; Node current = root; Node parent = root; while(current.idata != key) { parent = current; if(current.idata > key) { isLeftNode = true; current = current.leftNode; } else { isLeftNode = false; current = current.rightNode; } if(current == null) {// 没有找到相应的指定节点 flag = false; return flag; } }// 结束while循环 // 执行到此,就意味着找到要删除的节点current // 删除的节点是叶结点 if(current.leftNode == null && current.rightNode == null) { if(isLeftNode == true) parent.leftNode = null; else parent.rightNode = null; } // 删除的节点只有左子节点 else if(current.rightNode == null) { if(current == root) root = current.leftNode; else if(isLeftNode) parent.leftNode = current.leftNode; else parent.rightNode = current.leftNode; } // 删除的节点只有右子节点 else if(current.leftNode == null) { if(current == root) root = current.rightNode; else if(isLeftNode) parent.leftNode = current.rightNode; else parent.rightNode = current.rightNode; } // 删除的节点有左子节点和右子节点 else { Node replacedNode = getReplacedNode(current); if(current == root) root = replacedNode; else if(isLeftNode) parent.leftNode = replacedNode; else parent.rightNode = replacedNode; } return flag; } /** * 判断选择遍历方式 * * @param traverseType */ public void traverse(int traverseType) { switch(traverseType) { case 1: System.out.print("\n先序遍历:"); preOrder(root); break; case 2: System.out.print("\n中序遍历:"); inOrder(root); break; case 3: System.out.print("\n后序遍历:"); postOrder(root); break; } System.out.println(); } /** * 先序排列 */ private void preOrder(Node node) { if(node != null) { System.out.print(node.idata + " "); preOrder(node.leftNode); preOrder(node.rightNode); } } /** * 中序排列 */ private void inOrder(Node node) { if(node != null) { preOrder(node.leftNode); System.out.print(node.idata + " "); preOrder(node.rightNode); } } /** * 后序排列 */ private void postOrder(Node node) { if(node != null) { preOrder(node.leftNode); preOrder(node.rightNode); System.out.print(node.idata + " "); } } /** * 找到替换【被删除节点】的节点并且构建出以【替换点】为根的子树 * 说明:寻找【被删除节点】中右子树中key值最小的点作为【替换节点】,很明显是右子树中左叶子节点(如果有的话) * * @param delNode * @return */ private Node getReplacedNode(Node delNode) { Node current = delNode.rightNode; Node replacedNode = delNode; Node replacedParentNode = delNode; while(current != null) { replacedParentNode = replacedNode; replacedNode = current; current = current.leftNode; } if(replacedNode != delNode.rightNode) { // replacedNode就是要替换掉【被删除节点】的节点 replacedParentNode.leftNode = replacedNode.rightNode; replacedNode.rightNode = delNode.rightNode; } replacedNode.leftNode = delNode.leftNode; return replacedNode; } /** * 显示树结构 * * @param node */ @SuppressWarnings("unchecked") public void displayTree() { System.out.println("


回复

使用道具 举报

0

主题

20

帖子

56

积分

猿er

Rank: 1

积分
56
发表于 2016-8-14 07:43:52
||"); boolean isRowEmpty = false; int nBlanks = 32;// 控制每一行打印出的空格数 Stack displayStack = new Stack();// 要打印显示数据的节点存放到displayStack displayStack.push(root); while(!isRowEmpty) { isRowEmpty = true; Stack stockStack = new Stack();// 暂存将要打印显示数据的节点(会放入displayStack进行打印) for(int i = 0; i < nBlanks; i++) System.out.print(" "); while(!displayStack.isEmpty()) { Node node = (Node)displayStack.pop(); if(node != null) { System.out.print(node.idata); stockStack.push(node.leftNode); stockStack.push(node.rightNode); if(node.leftNode != null || node.rightNode != null) isRowEmpty = false; } else { System.out.print("--"); stockStack.push(null); stockStack.push(null); } for(int j = 0; j < nBlanks*2 - 2; j++) System.out.print(" "); }// 结束while(!displayStack.isEmpty())循环 System.out.println(); nBlanks = nBlanks/2; while(!stockStack.isEmpty()) displayStack.push(stockStack.pop()); }// 结束while(!isRowEmpty) System.out.println("
回复 支持 反对

使用道具 举报

0

主题

12

帖子

38

积分

猿er

Rank: 1

积分
38
发表于 2016-8-15 07:39:10
||");
        }
       
       
}
[/code]
                                                                                                               
                                       
                                                                               
                                            
  1. package structure.tree;
  2. import java.io.BufferedReader;
  3. import java.io.IOException;
  4. import java.io.InputStreamReader;
  5. public class TreeApp {
  6.         public static void main(String[] args) throws IOException {
  7.                 Tree tree = new Tree();
  8.                 int key;
  9.                 double value;
  10.                 tree.insert(50, 1.5);
  11.                 tree.insert(25, 1.2);
  12.                 tree.insert(75, 1.7);
  13.                 tree.insert(12, 1.5);
  14.                 tree.insert(37, 1.2);
  15.                 tree.insert(43, 1.7);
  16.                 tree.insert(30, 1.5);
  17.                 tree.insert(33, 1.2);
  18.                 tree.insert(87, 1.7);
  19.                 tree.insert(93, 1.5);
  20.                 tree.insert(97, 1.5);
  21.                
  22.                 while(true) {
  23.                         System.out.println("以下五个操作(用英文单词表示):");
  24.                         System.out.println("显示树结构show,插入节点insert,查找节点find,删除节点delete,遍历树结构traverse:");
  25.                         System.out.print("请输入上面操作单词的首字符:");
  26.                         char choice = getChar();
  27.                         switch(choice) {
  28.                         case 's':
  29.                                 tree.displayTree();
  30.                                 break;
  31.                         case 'i':
  32.                                 System.out.print("请输入节点的key值(需是整数类型):");
  33.                                 key = getInt();
  34.                                 System.out.print("\n请在输入节点的value值(需是浮点类型):");
  35.                                 value = getDouble();
  36.                                 tree.insert(key, value);
  37.                                 break;
  38.                         case 'f':
  39.                                 System.out.print("请输入您要查询节点的key值(需是整数类型):");
  40.                                 key = getInt();
  41.                                 Node foundNode = tree.find(key);
  42.                                 if(foundNode == null)
  43.                                         System.out.println("没有找到对应key值的节点...");
  44.                                 else {
  45.                                         System.out.print("找到相应key值的节点:");
  46.                                         foundNode.display();
  47.                                 }
  48.                                 break;
  49.                         case 'd':
  50.                                 System.out.print("请输入您要删除节点的key值(需是整数类型):");
  51.                                 key = getInt();
  52.                                 boolean delSuccess = tree.delete(key);
  53.                                 if(delSuccess)
  54.                                         System.out.println("已成功删除该节点...");
  55.                                 else
  56.                                         System.out.println("删除节点失败...");
  57.                                 break;
  58.                         case 't':
  59.                                 System.out.println("先序遍历请输入1操作,中序遍历请输入2操作,后序遍历请输入3操作...");
  60.                                 System.out.print("请选择操作:");
  61.                                 key = getInt();
  62.                                 tree.traverse(key);
  63.                                 break;
  64.                         default:
  65.                                 System.out.println("您输入的不合法,请核查输入是否有误...");
  66.                                 break;
  67.                         }
  68.                 }
  69.                
  70.         }
  71.        
  72.         public static String getString() throws IOException {
  73.                 InputStreamReader isr = new InputStreamReader(System.in);
  74.                 BufferedReader br = new BufferedReader(isr);
  75.                 return br.readLine();
  76.         }
  77.        
  78.         public static char getChar() throws IOException {
  79.                 return getString().charAt(0);
  80.         }
  81.        
  82.         public static int getInt() throws IOException {
  83.                 return Integer.parseInt(getString());
  84.         }
  85.        
  86.         public static double getDouble() throws IOException {
  87.                 return Double.parseDouble(getString());
  88.         }
  89. }
复制代码
回复 支持 反对

使用道具 举报