主要实现了二叉树的一般用法，可能会有些错误，还望纠正一下。 package structure.tree;public class node { public int idata; public double ddata; public node leftnode; public node rightnode; public node() { } public void display() {// отй╬╫з╣ц system.out.print('{'); system.out.print(idata); system.out.print(','); system.out.print(ddata); system.out.print('}'); }}
复制代码
[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 key) { isleftnode = true; current = current.leftnode; } else 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(