二叉树的java兑现
二叉树的java实现
package other; import java.util.Stack; class TreeNode { private String key; private TreeNode lchild; //左孩子 private TreeNode rchild; //右孩子 private TreeNode parent; //双亲节点 public TreeNode(String key) { this.key = key; } public String getKey() { return key; } public void setKey(String key) { this.key = key; } public TreeNode getLchild() { return lchild; } public void setLchild(TreeNode lchild) { this.lchild = lchild; } public TreeNode getRchild() { return rchild; } public void setRchild(TreeNode rchild) { this.rchild = rchild; } public TreeNode getParent() { return parent; } public void setParent(TreeNode parent) { this.parent = parent; } public String toString() { // 打印出树种某个节点的信息 StringBuffer sb = new StringBuffer(); sb.append("key:" + this.key + " "); if (this.getLchild() != null) { sb.append(" left child:" + this.getLchild().getKey()); } if (this.getRchild() != null) { sb.append(" right child:" + this.getRchild().getKey()); } return sb.toString(); } } public class TreeTest { private static Stack<TreeNode> s; private static TreeNode root; public static TreeNode createTree(){ root = new TreeNode("6"); TreeNode l = new TreeNode("3"); TreeNode r = new TreeNode("8"); l.setParent(root); r.setParent(root); TreeNode ll = new TreeNode("2"); TreeNode rl = new TreeNode("7"); l.setLchild(ll); r.setLchild(rl); ll.setParent(l); rl.setParent(r); root.setLchild(l); root.setRchild(r); root.setParent(null); return root; } public static void main(String[] args) { // 简单的构造一个树,当然是先构造树上的每一个节点 root = createTree(); System.out.println(treeDepth(root)); // preOrderTraverse(root); // 递归先序遍历树 // // // // // TreeNode finded = treeSearchTranverse(root, "6"); // 查找树中的某个key是否存在 // System.out.println(finded); // // TreeNode finded2 = treeSearchTranverse(root, "6"); // 查找树中的某个key是否存在 // System.out.println(finded2); // inOrderNonTraverse(root); } // 递归先序遍历二叉树,后序和中序相似,只是调换输出子树根节点的次序 public static void preOrderTraverse(TreeNode t) { System.out.println("递归先序遍历"); if (t != null) { System.out.println(t.getKey()); preOrderTraverse(t.getLchild()); preOrderTraverse(t.getRchild()); } } public static void inOrderNonTraverse(TreeNode t) { // 中序遍历二叉树的非递归 s = new Stack<TreeNode>(); s.clear(); s.push(t);// 根节点入栈 while (!s.isEmpty()) { while (!s.isEmpty()&&s.peek()!= null) s.push(s.peek().getLchild());// 向左走到尽头 s.pop();//空指针退栈,别忘了 if (!s.isEmpty()) { TreeNode current = s.pop(); System.out.println(current.getKey()); s.push(current.getRchild()); } } } // 二叉查找树,必须满足左子树的关键字小于等于根,右子树的节点大于等于根,这样中序遍历该树,可得到一个有序序列 /* * 在二叉查找树上找关键字为key的节点,递归方法 */ public static TreeNode treeSearchTranverse(TreeNode root, String key) { if (root == null || root.getKey().equals(key)) return root; if (root.getKey().compareTo(key) > 0) { // 小于根节点的关键字,肯定在左子树上 return treeSearchTranverse(root.getLchild(), key); } else { return treeSearchTranverse(root.getRchild(), key); } } /* * 在二叉查找树上找关键字为key的节点,非递归方法 */ public static TreeNode treeSearchNonTranverse(TreeNode root, String key) { while (root != null && !root.getKey().equals(key)) { if (key.compareTo(root.getKey()) < 0) { root = root.getLchild(); // 指向左孩子 } else { root = root.getRchild(); } } return root; } /* * 返回查找树中的最小关键字,只需一直沿着节点的left指针即可 */ public static TreeNode TreeMin(TreeNode x) { while (x.getLchild() != null) { x = x.getLchild(); } return x; } /* * 返回查找树中的最大关键字,只需一直沿着节点的right指针即可 */ public static TreeNode TreeMax(TreeNode x) { while (x.getRchild() != null) { x = x.getRchild(); } return x; } /* * 返回中序遍历查找树时节点x的后继,无需对关键字进行比较,因为二叉查找树的结构,x的后继就是具有大于x.getKey()的关键字中最小者的那个节点 */ public static TreeNode TreeSuccessor(TreeNode x) { if (x.getRchild() != null) //根据中序遍历 return TreeMin(x.getRchild()); TreeNode y = x.getParent(); while(y!=null&&x==y.getRchild()){ //x是y的右孩子或x是根节点??? x=y; y=y.getParent(); } return y; //x是y的左孩子 } /* * 在二叉查找树中插入一个节点z,使之仍然保持查找树的特性???????????不懂,指针x跟踪路径,从根节点开始,下降,而y始终指向x的父节点。 */ public static void insertNode(TreeNode z){ TreeNode y =null; TreeNode x = getRoot(); //根的父节点为空 while(x!=null){ y=x; if(z.getKey().compareTo(x.getKey())<0) x=x.getLchild(); else x=x.getRchild(); } z.setParent(y); //插入的z节点的双亲节点 if(y==null){ setRoot(z);//当前树为空树,设置根节点 } else if(z.getKey().compareTo(y.getKey())<0){ y.setLchild(z); } else y.setRchild(z); } public static TreeNode getRoot() { return root; } public static void setRoot(TreeNode root) { TreeTest.root = root; } /* * 在二叉查找树中删除一个节点z,使之仍然保持查找树的特性 */ public static TreeNode deleteNode(TreeNode z){ TreeNode x,y; if(z.getLchild()==null||z.getRchild()==null){ y=z; } else y = TreeSuccessor(z); if(y.getLchild()!=null){ x=y.getLchild(); } else x = y.getRchild(); if(x!=null){ x.setParent(y.getParent()); } if(y.getParent()==null){ setRoot(x); } else if(y==y.getParent().getLchild()){ y.getParent().setLchild(x); } else{ y.getParent().setRchild(x); } if(y!=z){ z.setKey(y.getKey()); } return y; } public static int treeDepth(TreeNode t){ //计算树的深度 TreeNode lchild,rchild; int lchildDepth,rchildDepth; if(t==null) return 0; else { System.out.println("树节点不为空时:"); lchild = t.getLchild(); rchild = t.getRchild(); lchildDepth = treeDepth(lchild); rchildDepth = treeDepth(rchild); return lchildDepth>rchildDepth?(lchildDepth+1):(rchildDepth+1); } } }