Pre-middle and post-order traversal of binary tree to find and delete

Table of Contents

Binary tree concept

Analysis of front, middle and back order traversal ideas:

Analysis of search ideas in front, middle and back order:

Analysis of ideas for deleting nodes:

Code

---

The concept of binary tree

Full binary tree and complete binary tree

Full binary tree: all leaf nodes are at the last level (leaf nodes have no left or right nodes behind them)

Complete binary tree: All leaf nodes are at the last level and the penultimate level, and the leaf nodes of the penultimate level are continuous on the left, and the leaf nodes of the penultimate level are continuous on the right.

Analysis of ideas for front, middle and back order traversal:

Analysis of search ideas in the front, middle and back order:

Analysis of ideas for deleting nodes:

Code Implementation

package Tree;

public class BinaryTreeDemo {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        HeroNode root = new HeroNode(1, "Song Jiang");
        HeroNode node2 = new HeroNode(2, "Wu Yong");
        HeroNode node3 = new HeroNode(3, "Lu Junyi");
        HeroNode node4 = new HeroNode(4, "Lin Chong");
        HeroNode node5 = new HeroNode(5, "Li Kui");

        root.setLeft(node2);
        root.setRight(node3);
        node3.setLeft(node5);
        node3.setRight(node4);

        binaryTree.setRoot(root);

        System.out.println("Preorder traversal");
        binaryTree.preOrder();
//
// System.out.println("In-order traversal");
// binaryTree.infixOrder();
//
// System.out.println("Post-order traversal");
// binaryTree.postOrder();

        //preorder traversal
// System.out.println("Preorder traversal mode~~~~");
//HeroNode resNode = binaryTree.preOrderSearch(5);
// if(resNode!=null){
// System.out.printf("Found, the information is no=%d name=%s", resNode.getNo(), resNode.getName());
// System.out.println();
// }else {
// System.out.printf("No hero with no=%d found",5);
// System.out.println();
// }
       //In-order traversal search
// System.out.println("In-order traversal mode~~~~");
// HeroNode resNode = binaryTree.infixOrderSearch(4);
// if(resNode!=null){
// System.out.printf("Found, the information is no=%d name=%s", resNode.getNo(), resNode.getName());
// System.out.println();
// }else {
// System.out.printf("No hero with no=%d found",4);
// System.out.println();
// }
// Subsequent traversal
// System.out.println("Post-order traversal mode~~~~");
// HeroNode resNode = binaryTree.postOrderSearch(2);
// if(resNode!=null){
// System.out.printf("Found, the information is no=%d name=%s", resNode.getNo(), resNode.getName());
// System.out.println();
// }else {
// System.out.printf("No hero with no=%d found",2);
// System.out.println();
// }
        //Test to delete node
        System.out.println("Preorder traversal before deletion");
        binaryTree.preOrder();
        binaryTree.delNode(3);
        System.out.println("After deletion, preorder traversal");
        binaryTree.preOrder();
    }
}

//Create BinaryTree binary tree
class BinaryTree {
    private HeroNode root;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    //delete node
    public void delNode(int no){
        if(root!=null){
            if(root.getNo()==no){
                root=null;
            }else {
                root.delNode(no);
            }
        }else {
            System.out.println("Empty tree, cannot be deleted");
        }
    }

    //preorder traversal
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("The binary number is empty and cannot be traversed");
        }
    }

    //In-order traversal
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("The binary number is empty and cannot be traversed");
        }
    }

    //post-order traversal
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("The binary number is empty and cannot be traversed");
        }
    }

    //preorder traversal
    public HeroNode preOrderSearch(int no) {
        if (root != null) {
            return root.preOrderSearch(no);
        } else {
            return null;
        }
    }

    //In-order traversal
    public HeroNode infixOrderSearch(int no) {
        if (root != null) {
            return root.infixOrderSearch(no);
        } else {
            return null;
        }
    }
    //Subsequent traversal
    public HeroNode postOrderSearch(int no){
        if(root!=null){
            return this.root.postOrderSearch(no);
        }else {
            return null;
        }
    }
}

//Create the HeroNode node first
classHeroNode {
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + ''' +
                '}';
    }
    //Delete nodes recursively
    public void delNode(int no){
        if (this.left!=null & amp; & amp;this.left.no==no){
            this.left=null;
            return;
        }
        if(this.right!=null & amp; & amp;this.right.no==no){
            this.right=null;
            return;
        }
        if (this.left!=null){
            this.left.delNode(no);
        }
        if (this.right!=null){
            this.right.delNode(no);
        }
    }

    //Write the method of preorder traversal
    public void preOrder() {
        System.out.println(this);//Output the parent node first
        //Recursively traverse the left subtree in preorder
        if (this.left != null) {
            this.left.preOrder();
        }
        //Recursively traverse the right subtree in preorder
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    //Write a method for in-order traversal
    public void infixOrder() {
        //Recursively traverse the left subtree in z order
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);//Output parent node
        //Recursively traverse the right subtree in z order
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    //Write a method for post-order traversal
    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }

    //Preorder traversal search
    public HeroNode preOrderSearch(int no) {
        if (this.no == no) {
            return this;
        }
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }

    //In-order traversal search
    public HeroNode infixOrderSearch(int no) {
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        if (this.no == no) {
            return this;
        }
        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }
        return resNode;
    }

    //Subsequent traversal search
    public HeroNode postOrderSearch(int no) {
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        if (this.right != null) {
            resNode = this.right.postOrderSearch(no);
        }
        if (this.no == no) {
            return this;
        }
        return resNode;
    }
}