Java二叉树前中后序遍历，前中后序查找，删除结点

墨蓝 2023-06-08 10:46 12阅读 0赞

**结点二叉树**  
前序遍历，中序遍历，后序遍历  
前序查找，中序查找，后序查找  
删除结点

public class BiraryTreeDemo { 
        public static void main(String[] args) { 
            TreeNode root = new TreeNode(1);
            TreeNode node2 = new TreeNode(2);
            TreeNode node3 = new TreeNode(3);
            TreeNode node4 = new TreeNode(4);
            TreeNode node5 = new TreeNode(5);
            root.setLeft(node2);
            root.setRight(node3);
            node3.setLeft(node5);
            node3.setRight(node4);
            BinaryTree binaryTree = new BinaryTree();
            //设置根节点
            binaryTree.setRoot(root);
    // System.out.println("前序遍历");
    // binaryTree.preOrder();
    // System.out.println("中序遍历");
    // binaryTree.infixOrder();
    // System.out.println("后序遍历");
    // binaryTree.postOrder();
    
    // System.out.println("前序遍历查找");
    // TreeNode treeNode = binaryTree.postOrderSearch(15);
    //
    // if (treeNode != null) { 
    // System.out.println(treeNode);
    // }
            System.out.println("删除前，前序遍历");
            binaryTree.postOrder();
            System.out.println("删除后，前序遍历");
            binaryTree.deleteNode(3);
            binaryTree.postOrder();
            
        }
    }
    
    class BinaryTree { 
        private TreeNode root;
    
        public void setRoot(TreeNode root) { 
            this.root = root;
        }
    
        //前序遍历
        public void preOrder() { 
            if (this.root != null) { 
                this.root.preOrder();
            } else { 
                System.out.println("二叉树为空");
            }
        }
    
        public void infixOrder() { 
            if (this.root != null) { 
                this.root.infixOrder();
            } else { 
                System.out.println("二叉树为空");
            }
    
        }
    
        public void postOrder() { 
            if (this.root != null) { 
                this.root.postOrder();
            } else { 
                System.out.println("二叉树为空");
            }
    
    
        }
    
        public TreeNode preOrderSearch(int no) { 
            if (root != null) { 
                return root.preOrderSearch(no);
            } else { 
                return null;
            }
        }
    
        public TreeNode infixOrderSearch(int no) { 
            if (root != null) { 
                return root.infixOrderSearch(no);
            } else { 
                return null;
            }
        }
    
        public TreeNode postOrderSearch(int no) { 
            if (root != null) { 
                return root.postOrderSearch(no);
            } else { 
                return null;
            }
        }
    
        public void deleteNode(int no) { 
            if (root != null) { 
                //判断根节点是否为要删除的
                if (root.getVal() == no) { 
                    root = null;
                } else { 
                    root.deleteNode(no);
                }
            } else { 
                System.out.println("二叉树为空");
            }
        }
    
    
    }
    
    
    class TreeNode { 
        private int val;
        private TreeNode left;
        private TreeNode right;
    
        public TreeNode(int val) { 
            this.val = val;
        }
    
        public int getVal() { 
            return val;
        }
    
        public void setVal(int val) { 
            this.val = val;
        }
    
        public TreeNode getLeft() { 
            return left;
        }
    
        public void setLeft(TreeNode left) { 
            this.left = left;
        }
    
        public TreeNode getRight() { 
            return right;
        }
    
        public void setRight(TreeNode right) { 
            this.right = right;
        }
    
        @Override
        public String toString() { 
            return "TreeNode{" +
                    "val=" + val +
                    '}';
        }
    
        //前序遍历方法
        public void preOrder() { 
            //先输出父结点
            System.out.println(this);
            //递归左子树
            if (this.left != null) { 
                this.left.preOrder();
            }
            if (this.right != null) { 
                this.right.preOrder();
            }
        }
    
        //中序遍历
        public void infixOrder() { 
            //
            if (this.left != null) { 
                this.left.infixOrder();
            }
            System.out.println(this);
            if (this.right != null) { 
                this.right.infixOrder();
            }
        }
    
        public void postOrder() { 
            if (this.left != null) { 
                this.left.postOrder();
            }
            if (this.right != null) { 
                this.right.postOrder();
            }
            System.out.println(this);
    
        }
    
        /** * @param no 查找的no * @return 返回结点 **/
        public TreeNode preOrderSearch(int no) { 
            System.out.println("进入前序遍历查找");
            if (this.val == no) { 
                return this;
            }
            TreeNode trs = null;
            if (this.left != null) { 
                trs = this.left.preOrderSearch(no);
            }
            //说明左子树找到了
            if (trs != null) { 
                return trs;
            }
            //左子树没找到，找右子树
            if (this.right != null) { 
                trs = this.right.preOrderSearch(no);
            }
            return trs;
        }
    
        public TreeNode infixOrderSearch(int no) { 
            TreeNode trs = null;
            if (this.left != null) { 
                trs = this.left.infixOrderSearch(no);
    
            }
            if (trs != null) { 
                return trs;
            }
            System.out.println("进入中序遍历查找");
            if (this.val == no) { 
                return this;
            }
            if (this.right != null) { 
                trs = this.right.infixOrderSearch(no);
            }
            return trs;
        }
    
        public TreeNode postOrderSearch(int no) { 
            TreeNode trs = null;
            if (this.left != null) { 
                trs = this.left.postOrderSearch(no);
            }
            if (trs != null) { 
                return trs;
            }
            if (this.right != null) { 
                trs = this.right.postOrderSearch(no);
            }
            if (trs != null) { 
                return trs;
            }
            System.out.println("进入后序遍历查找");
            if (this.val == no) { 
                return this;
            }
            return trs;
        }
    
        //递归删除结点
        public void deleteNode(int no) { 
            if (this.left != null && this.left.val == no) { 
                this.left = null;
                return;
            }
            if (this.right != null && this.right.val == no) { 
                this.right = null;
                return;
            }
            if (this.left != null) { 
                this.left.deleteNode(no);
            }
            if (this.right != null) { 
                this.right.deleteNode(no);
            }
    
        }
    
    
    }