Java Web开发之道 光盘源代码1

package tree; public class Tree { private Tnode root; public Tree(){ root=null; } public Tnode find(int key){ //查找节点的方法 Tnode current=root; //定义当前节点为头结点 if(current.iDate!=key){ //比对查找关键字 if(key<current.iDate){ //如果小于，则进入左子树 current=current.leftChild; //将左节点赋给当前节点 } else{ current=current.rightChild; //将右节点赋给当前节点 } if(current==null){ //判断当前节点是否为空 return null; } } System.out.println("所查找的节点的数据是："+current.dDate); return current; } public void insert(int id, double dd){ //插入节点的方法 Tnode newTnode= new Tnode(); //初始化一个新节点 newTnode.iDate=id; newTnode.dDate=dd; if(root==null){ //看根节点是否为空 root=newTnode; System.out.println("根节点插入！"); } else{ Tnode current=root; //将根节点赋给当前节点 Tnode parent; while(true){ parent=current; if(id<current.iDate){ //比对关键字，小于则进入左节点 current=current.leftChild; if(current==null){ //判断当前节点是否为空，是！则直接赋值新节点 parent.leftChild=newTnode; System.out.println("插入的节点关键字是："+parent.leftChild.iDate); return; } } else{ current=current.rightChild; if(current==null){ //判断当前节点是否为空 parent.rightChild=newTnode; System.out.println("插入节点关键字是："+parent.rightChild.iDate); return; } } } } System.out.println("根节点的关键字是："+root.iDate); } public void inOrder(Tnode localRoot){ //利用递归对树进行遍历操作 if(localRoot!=null){ inOrder(localRoot.leftChild); System.out.print(localRoot.iDate); inOrder(localRoot.rightChild); } } public boolean delete(int key){ //删除节点的方法 Tnode current=root; Tnode parent=root; boolean isLeftChild=true; while(current.iDate!=key){ //寻找要删除的节点 parent=current; if(key<current.iDate){ //判断是否去节点 isLeftChild=true; //标记节点为真 current=current.leftChild; //将左节点作为当前节点 } else{ //是否去右节点 isLeftChild=false; current=current.rightChild; //将右节点作为当前节点 } } if(current.leftChild==null&&current.rightChild==null){ //当前节点的左右节点都为空 if(current==root){ //如果当前节点为根节点 root=null; } else if(isLeftChild){ //如果是左节点 parent.leftChild=null; } else{ //如果是右节点 parent.rightChild=null; } } else if(current.rightChild==null){ //如果当前节点只有左节点 if(current==root){ //如果当前节点是根节点 root=current.leftChild; //将当前节点的右节点赋给当前节点 } else if(isLeftChild){ //如果当前节点是一个左节点 parent.leftChild=current.leftChild; //将当前节点的左节点赋给当前节点的双亲节点的左节点 } else{ //如果当前节点是一个右节点 parent.rightChild=current.leftChild; } } else if(current.leftChild==null){ //如果当前节点只有右节点 if(current==root){ root=current.rightChild; } else if(isLeftChild){ parent.leftChild=current.rightChild; } else{ parent.rightChild=current.rightChild; } } else{ //如果当前节点左右节点都有 Tnode successor=getSuccessor(current); //调用寻找其中序遍历时的后继节点的方法 if(current==root){ root=successor; } else if(isLeftChild){ parent.leftChild=successor; } else{ parent.rightChild=successor; successor.leftChild=current.leftChild; } } System.out.println("关键字为"+current.iDate+"的节点已被删除！"); return true; } private Tnode getSuccessor(Tnode delNode){ //寻找其中序遍历时的后继节点的方法 Tnode successorParent=delNode; Tnode successor=delNode; Tnode current=delNode.rightChild; while(current!=null){ successorParent=successor; successor=current; current=current.leftChild; } if(successor==delNode.rightChild){ successorParent.leftChild=successor.rightChild; successor.rightChild=delNode.rightChild; } return successor; } public void perOrder(Tnode localRoot){ //前序遍历 System.out.println(localRoot.iDate+" "); perOrder(localRoot.leftChild); perOrder(localRoot.rightChild); } public void postOrder(Tnode localRoot){ //后序遍历 postOrder(localRoot.leftChild); postOrder(localRoot.rightChild); System.out.println(localRoot.iDate+" "); } }