树的优点：结合和链表和有序数组的优点。【链表的：插入快(时间复杂度0(1))，查找慢 有序数组：查找方便(时间维度0(logN))，插入慢】
以下是关于二叉树的多种遍历方法，以及添删改查的常规操作
import java.util.Stack; /** * @author JenKenYANG * */ public class Tree{ private Node root; //利用二叉树的特性 左子节点小于父节点 右子节点大于或等于父节点 所以利用这一点来寻找是否有相同的节点，如果没有则为null public Node find(int key) { Node current = root; while(current.iDate != key) { if(key<root.iDate) { current=current.liftChild; }else { current=current.rightChild; } if(current==null) { return null; } } return current; } //二叉树的添加 public void insert(int id,double dd) { Node newNode = new Node(); newNode.iDate=id; newNode.fDate=dd; if(root==null) { root=newNode; }else { Node current=root; Node parten; while(true) { parten=current; //parten就相当于要查找的那个点的父节点 if(id<current.iDate) { current=current.liftChild; if(current==null) { parten.liftChild=newNode; return; } }else { current=current.rightChild; if(current==null) { parten.rightChild=newNode; return; } } } } } //删除节点会面临：①删除的只是页节点。 ②删除的是有一个子节点的节点 ③删除有两个子节点的节点 public boolean delete(int key) { /*Node cutNode=find(key); if(cutNode.liftChild==null && cutNode.rightChild==null) { cutNode=null; }else if(cutNode.liftChild!=null) { }else if(cutNode.rightChild!=null) { }else { }*/ //这个思路错的原因是，因为要删除节点不是光让这个节点是null 还得让父节点对它的指向为null。 Node cur=root; Node parent=root; boolean isLeftChild=true; while (cur.iDate != key) { parent=cur;//为了在跳出循环前保留父节点 if(cur.iDate>key) { cur=cur.liftChild; isLeftChild=true; }else { cur=cur.rightChild; isLeftChild=false; } } if(cur==null) { return false; } if(cur.liftChild==null && cur.rightChild==null) { if(cur==root) { root=null; } else if(isLeftChild) { parent.liftChild=null; }else { parent.rightChild=null; } }else if(cur.rightChild==null) { if(cur==root) { root=cur.liftChild; }else if(isLeftChild) { parent.liftChild=cur.liftChild; }else { parent.rightChild=cur.liftChild; } }else if(cur.liftChild==null) { if(cur==root) { root=cur.rightChild; }else if(isLeftChild) { parent.liftChild=cur.rightChild; }else { parent.rightChild=cur.liftChild; } }else { /*if(cur==root) { root=cur.rightChild; root.liftChild=cur.liftChild; }else if(isLeftChild) { parent.liftChild=cur.rightChild; }else { parent.rightChild=cur.rightChild; }*/ //这个不能直接来用上面单节点的方法来替换，因为如果替换的节点本身是个有双节点的父类，那么二叉树树就会 //失去它一个父节点只能有两个子节点的特性，变成了三个节点的树。 Node successor=getSuccessor(cur); if(cur==root) { root=successor; }else if(isLeftChild) { parent.liftChild=successor; }else { parent.rightChild=successor; } successor.liftChild=cur.liftChild; } return true; } //为删除时遇到的有双子节点的删除，寻找后继节点 public Node getSuccessor(Node delNode) { Node successorParent=delNode; Node successor=delNode; Node cur=delNode.rightChild; while(cur!=null) { successorParent=successor; successor=cur; cur=cur.liftChild; } if(successor != delNode.rightChild) { successorParent.liftChild=cur.rightChild; successor.rightChild=delNode.rightChild; } return successor; } //中序遍历 public void inOrder(Node localRoot) { if(localRoot != null) { inOrder(localRoot.liftChild); System.out.print(localRoot.iDate+" "); inOrder(localRoot.rightChild); } } //前序遍历 先根再左再右 public void inOrderAfter(Node localRoot) { if (localRoot != null) { System.out.print(localRoot.iDate+" "); inOrderAfter(localRoot.liftChild); inOrderAfter(localRoot.rightChild); } } //后序遍历 先左再右最后根 public void inOrderBack(Node localRoot) { if(localRoot != null) { inOrderBack(localRoot.liftChild); inOrderBack(localRoot.rightChild); System.out.println(localRoot.iDate+" "); } } //中序遍历<栈> //先将左树压进栈然后当把localRoot压进栈后，跳出当前循环，顺序出栈，之后再次进入循环重复上述步骤 public void inOrder2(Node localRoot) { Stack<Node> stack=new Stack<Node>(); while (localRoot != null || !stack.empty()) { while (localRoot != null) { stack.push(localRoot); localRoot=localRoot.liftChild; } if(!stack.empty()){ localRoot=stack.pop(); System.out.println(localRoot.iDate); localRoot=localRoot.rightChild; } } } //先序遍历<栈> public void inOrderAfter2(Node localRoot) { Stack<Node> stack=new Stack<Node>(); while (localRoot != null || !stack.empty()) { while (localRoot != null) { System.out.println(localRoot.iDate); stack.push(localRoot); localRoot=localRoot.liftChild; } if(!stack.empty()) { localRoot=stack.pop(); localRoot=localRoot.rightChild; } } } //后序遍历<栈> public void inOrderBack2(Node localRoot) { // Stack<Node> stack=new Stack<Node>(); Stack<Node> stack=new Stack<Node>(); // while (localRoot != null || !stack.empty()) { // while (localRoot != null) { // stack.push(localRoot); // localRoot=localRoot.liftChild; // } // if (!stack.empty()) { // localRoot=stack.pop(); // localRoot=localRoot.rightChild; // } // } Stack<Node> stack = new Stack<Node>(); Stack<Node> output = new Stack<Node>();//构造一个中间栈来存储逆后序遍历的结果 Node node = root; while (node != null || stack.size() > 0) { if (node != null) { output.push(node); stack.push(node); node = node.rightChild; } else { node = stack.pop(); node = node.liftChild; } } System.out.println(output.size()); while (output.size() > 0) { System.out.println(output.pop().iDate); } } // public void inOrderBack3(Node localRoot) { if(root==null) { return; } Stack<Node> stack=new Stack<Node>(); Stack<Node> out=new Stack<Node>();//用来存储将要输出的内容 stack.push(localRoot); //先把根放入栈底 while(!stack.empty()) { Node temp=stack.pop(); out.push(temp); if(temp.liftChild!=null) { stack.push(temp.liftChild); } if(temp.rightChild!=null){ stack.push(temp.rightChild); } } while (!out.empty()) { System.out.println(out.pop().iDate); } } //查找最大值 <> public int getMax() { Node cur=root; Node maxNode=root; while(cur != null) { maxNode=cur; cur=cur.liftChild; } return maxNode.iDate; } //查找最小值 <> public int getMin() { Node cur=root; Node minNode=root; while(cur != null) { minNode=cur; cur=cur.rightChild; } return minNode.iDate; } }
