二叉树部分功能实现（JAVA）

WBOY

发布： 2016-07-25 09:02:30

原创

896 人浏览过

主要实现了二叉树的一般用法，可能会有些错误，还望纠正一下。

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("