Binary tree partial function implementation (JAVA)-PHP Tutorial-php.cn

Binary tree partial function implementation (JAVA)

WBOY

Release： 2016-07-25 09:02:30

Original

894 people have browsed it

It mainly implements the general usage of binary trees. There may be some errors. I hope they can be corrected.

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('}');
}
}

Copy code

[code]package structure.tree; import java.util.Stack; public class Tree { /* Node attributes, the tree is composed of nodes */ private Node root; public Tree() { root = null; } /*** Find the tree node with the specified key value * * @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) {//The corresponding specified node was not found flag = false; return flag; } }//End the while loop // Execution to this point means finding the node current to be deleted //The deleted node is a leaf node if(current.leftNode == null && current.rightNode == null) { if(isLeftNode == true) parent.leftNode = null; else parent.rightNode = null; } //The deleted node only has the left child node else if(current.rightNode == null) { if(current == root) root = current.leftNode; else if(isLeftNode) parent.leftNode = current.leftNode; else parent.rightNode = current.leftNode; } //The deleted node only has the right child node else if(current.leftNode == null) { if(current == root) root = current.rightNode; else if(isLeftNode) parent.leftNode = current.rightNode; else parent.rightNode = current.rightNode; } //The deleted node has left child node and right child node else { Node replacedNode = getReplacedNode(current); if(current == root) root = replacedNode; else if(isLeftNode) parent.leftNode = replacedNode; else parent.rightNode = replacedNode; } return flag; } /*** Determine the selection traversal method * * @param traverseType*/ public void traverse(int traverseType) { switch(traverseType) { case 1: System.out.print("n preorder traversal:"); preOrder(root); break; case 2: System.out.print("n in-order traversal:"); inOrder(root); break; case 3: System.out.print("n post-order traversal:"); postOrder(root); break; } System.out.println(); } /*** Sort in order*/ private void preOrder(Node node) { if(node != null) { System.out.print(node.idata + " "); preOrder(node.leftNode); preOrder(node.rightNode); } } /*** Sorted in middle order*/ private void inOrder(Node node) { if(node != null) { preOrder(node.leftNode); System.out.print(node.idata + " "); preOrder(node.rightNode); } } /*** Sorted in descending order*/ private void postOrder(Node node) { if(node != null) { preOrder(node.leftNode); preOrder(node.rightNode); System.out.print(node.idata + " "); } } /*** Find the node that replaces the [deleted node] and construct a subtree rooted at the [replacement point] * Description: Find the point with the smallest key value in the right subtree of the [deleted node] as the [replacement node], which is obviously the left leaf node in the right subtree (if any) * * @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; } /*** Show tree structure * * @param node*/ @SuppressWarnings("unchecked") public void displayTree() { System.out.println("