数据结构_二叉树_前中后序遍历、查找、删除

叁歲伎倆 2023-07-11 06:10 13阅读 0赞

### 文章目录 ###

*   *  树节点定义
     *  遍历
     *  查找
     *  删除

## 树节点定义 ##

class TreeNode {
        
    	int val;
    	TreeNode left;
    	TreeNode right;
    
    	public TreeNode(int val) {
        
    		super();
    		this.val = val;
    	}
    
    	@Override
    	public String toString() {
        
    		return "TreeNode [val=" + val + "]";
    	}
    }

## 遍历 ##

/**
     * 前序遍历
     */
    public void preOrder() {
        
    	System.out.print(this.val);
    	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.print(this.val);
    	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.print(this.val);
    }

## 查找 ##

/**
     * 前序遍历查找
     * @param val
     * @return
     */
    public TreeNode preOrderSearch(int val) {
        
    	if (this.val == val) {
        
    		return this;
    	}
    	TreeNode result = null;
    	if (this.left != null) {
        
    		result = this.left.preOrderSearch(val);
    	}
    	if (result != null) {
        
    		return result;
    	}
    	if (this.right != null) {
        
    		return this.right.preOrderSearch(val);
    	}
    	return result;
    }
    
    /**
     * 中序遍历查找
     * @param val
     * @return
     */
    public TreeNode infixOrderSearch(int val) {
        
    	TreeNode result = null;
    	if (this.left != null) {
        
    		result = this.left.infixOrderSearch(val);
    	}
    	if (result != null) {
        
    		return result;
    	}
    	if (this.val == val) {
        
    		return this;
    	}
    	if (this.right != null) {
        
    		return this.right.infixOrderSearch(val);
    	}
    	return result;
    }
    
    /**
     * 后续遍历查找
     * @param val
     * @return
     */
    public TreeNode postOrderSearch(int val) {
        
    	TreeNode result = null;
    	if (this.left != null) {
        
    		result = this.left.postOrderSearch(val);
    	}
    	if (result != null) {
        
    		return result;
    	}
    	if (this.right != null) {
        
    		result = this.right.postOrderSearch(val);
    	}
    	if (result != null) {
        
    		return result;
    	}
    	if (this.val == val) {
        
    		return this;
    	}
    	return result;
    }

## 删除 ##

/**
     * 删除子节点
     * 1.如果删除的节点是叶子节点，则删除该节点
     * 2.如果删除的节点是非叶子节点，则删除该子树
     * @param val
     */
    public void delete(int val) {
        
    	if (this.left != null && this.left.val == val) {
        
    		this.left = null;
    		return;
    	}
    	if (this.right != null && this.right.val == val) {
        
    		this.right = null;
    		return;
    	}
    	if (this.left != null) {
        
    		this.left.delete(val);
    	}
    	if (this.right != null) {
        
    		this.right.delete(val);
    	}
    }