本文共 5600 字,大约阅读时间需要 18 分钟。
package com.demo;/** * 二叉排序树(查找树) */public class BiTree { private BiNode root; public void insertNode(int data){ BiNode node = new BiNode(data, null, null); if(root == null){ root = node; }else{ BiNode currentNode = root; BiNode parentNode; while(true){ parentNode = currentNode; if(data < currentNode.data){ if((currentNode = currentNode.lchild) != null){ continue; }else{ parentNode.lchild = node; return; } }else{ if((currentNode = currentNode.rchild) != null){ continue; }else{ parentNode.rchild = node; return; } } } } } //删除节点 public void delete(int data){ if(root == null) return; BiNode node = root;//需要删除的节点 boolean left = true; BiNode pre = node;//需要删除的节点的父节点 while(true){ if(node.data == data){ if(node.lchild == null && node.rchild == null){ System.out.println("没有子节点"); if(left) pre.lchild=null; else pre.rchild=null; return; }else if(node.lchild!=null && node.rchild==null){ System.out.println("只有左子节点"); System.out.println("pre:"+pre.data); System.out.println("node:"+node.data); if(left){ pre.lchild = node.lchild; node = null; return; }else{ pre.rchild = node.lchild; node = null; return; } }else if(node.lchild == null && node.rchild != null){ System.out.println("只有右子节点"); System.out.println("pre:"+pre.data); System.out.println("node:"+node.data); pre.rchild = node.rchild; node = null; return; }else{ System.out.println("左右子节点都有"); BiNode lchild = node.rchild;//肯定不为null。 pre = lchild; while(lchild.lchild != null){ pre = lchild; lchild = lchild.lchild; } pre.lchild = null; node.data = lchild.data; return; } }else if(data > node.data){ pre = node; node = node.rchild; left = false; }else{ pre = node; node = node.lchild; left = true; } } } //查找 public BiNode find(int data){ if(root == null) return null; BiNode node = root; while(node!= null){ if(node.data == data){ return node; }else if(data > node.data){ node = node.rchild; }else{ node = node.lchild; } } return null; } //前序遍历 public void preOrder(BiNode node){ if(node == null) return; else{ System.out.print(node.data+" "); preOrder(node.lchild); preOrder(node.rchild); } } //中序遍历 public void inOrder(BiNode node){ if(node == null) return; else{ inOrder(node.lchild); System.out.print(node.data+" "); inOrder(node.rchild); } } //后序遍历 public void postOrder(BiNode node){ if(node == null) return; else{ postOrder(node.lchild); postOrder(node.rchild); System.out.print(node.data+" "); } } static class BiNode { int data; BiNode lchild; BiNode rchild; public BiNode(int data, BiNode lchild, BiNode rchild){ this.data = data; this.lchild = lchild; this.rchild = rchild; } /* (non-Javadoc) * @see java.lang.Object#toString() */ @Override public String toString() { return "BiNode [data=" + data + ", lchild=" + lchild + ", rchild=" + rchild + "]"; } } public static void main(String[] args) { BiTree tree = new BiTree(); tree.insertNode(5); tree.insertNode(2); tree.insertNode(1); tree.insertNode(4); tree.insertNode(3); tree.insertNode(7); tree.insertNode(6); tree.insertNode(9); tree.insertNode(8); System.out.print("前序遍历:"); tree.preOrder(tree.root); System.out.println(); System.out.print("中序遍历:"); tree.inOrder(tree.root); System.out.println(); System.out.print("后序遍历:"); tree.postOrder(tree.root); System.out.println(); int i = 4; System.out.println("删除数据为"+i+"的节点"); tree.delete(i); System.out.print("前序遍历:"); tree.preOrder(tree.root); System.out.println(); System.out.print("中序遍历:"); tree.inOrder(tree.root); System.out.println(); System.out.print("后序遍历:"); tree.postOrder(tree.root); System.out.println(); int j = 5; System.out.println("查找数据为"+j+"的节点"); BiNode node = tree.find(j); System.out.println(node); }}
转载地址:http://pejqi.baihongyu.com/