树：二叉排序树

小鱼儿 2023-02-28 01:23 64阅读 0赞

# 1，二叉树基本概念 #

*  树分为很多种，其中每一个节点最多有两个节点的树形式称之为二叉树
 *  二叉树的子节点分为左节点和父节点；对于一个父节点来说，可以单独存在左子节点或者右子节点，也可以同时存在左右子节点  
    ![在这里插入图片描述][20200718203230412.png]
 *  如果二叉树的所有叶子节点都在最后一层，并且`节点总数 = 2 ^ n - 1`，n为最大层数，则该二叉树可以称之为**满二叉树**  
    ![在这里插入图片描述][20200718203242978.png]
 *  如果二叉树的所有叶子节点都在最后一层或者倒数第二层，且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，则称之为**完全二叉树**  
    ![在这里插入图片描述][20200718203254135.png]

# 2，二叉树遍历 #

## 2.1，前序遍历 ##

*  先输出当前节点（初始为叶子节点）
 *  如果左子节点不为空，再递归前序遍历输出左子节点
 *  如果右子节点不为空，最后递归前序遍历输出右子节点

## 2.2，中序遍历 ##

*  如果左子节点不为空，先递归中序遍历输出左子节点
 *  再输出当前节点
 *  如果右子节点不为空，最后递归中序遍历输出右子节点

## 2.3，后续遍历 ##

*  如果左子节点不为空，先递归后序遍历输出左子节点
 *  如果右子节点不为空，再递归后序遍历输出右子节点
 *  最后输出当前节点

## 2.4，遍历代码汇总 ##

# 3，二叉树查找 #

## 3.1，前序查找 ##

*  先比较当前节点，当前节点匹配到直接返回
 *  再匹配左侧节点，并递归前序查找进行匹配，匹配到直接返回
 *  最后匹配右侧节点，并递归前序查找进行匹配，匹配到直接返回
 *  以上几步没有匹配到，则返回null，表示没有匹配到

## 3.2，中序查找 ##

*  先匹配左侧节点，并递归中序查找进行匹配，匹配到直接返回
 *  再比较当前节点，当前节点匹配到直接返回
 *  最后匹配右侧节点，并递归中序查找进行匹配，匹配到直接返回
 *  以上几步没有匹配到，则返回null，表示没有匹配到

## 3.3，后续查找 ##

*  先匹配左侧节点，并递归后序查找进行匹配，匹配到直接返回
 *  再匹配右侧节点，并递归后序查找进行匹配，匹配到直接返回
 *  再比较当前节点，当前节点匹配到直接返回
 *  以上几步没有匹配到，则返回null，表示没有匹配到

## 3.4，查找代码汇总 ##

# 4，二叉树删除 #

## 4.1，删除步骤 ##

*  如果删除的节点是叶子节点，则直接删除
 *  如果删除的是非叶子节点，则需要对删除节点的子节点进行处理
 *  用右侧最左节点代替该节点，并删除右侧最左节点

## 4.2，删除代码实现 ##

package com.self.datastructure.tree;
    
    import lombok.Data;
    import lombok.ToString;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /** * 二叉树 * * @author pj_zhang * @create 2020-03-21 22:02 **/
    public class BinaryTree { 
    
        public static void main(String[] args) { 
            MyBinaryTree binaryTree = new MyBinaryTree();
            binaryTree.addNode(5);
            binaryTree.addNode(2);
            binaryTree.addNode(1);
            binaryTree.addNode(4);
            binaryTree.addNode(3);
            binaryTree.addNode(8);
            binaryTree.addNode(6);
            binaryTree.addNode(9);
            binaryTree.addNode(10);
            binaryTree.middleShowDetails();
            System.out.println(binaryTree.delNode(1));;
            binaryTree.middleShowDetails();
        }
    
        static class MyBinaryTree { 
    
            private Node node;
    
            // 添加二叉树节点
            public void addNode(Integer data) { 
                if (null == node) { 
                    node = new Node(data);
                } else { 
                    addNode(data, node);
                }
            }
    
            private void addNode(Integer data, Node node) { 
                if (null == node) { 
                    throw new RuntimeException("Node 节点为空");
                }
                if (data > node.getData()) { 
                    Node rightNode = node.getRightNode();
                    if (null == rightNode) { 
                        node.setRightNode(new Node(data));
                    } else { 
                        addNode(data, node.getRightNode());
                    }
                } else if (data < node.getData()) { 
                    Node leftNode = node.getLeftNode();
                    if (null == leftNode) { 
                        node.setLeftNode(new Node(data));
                    } else { 
                        addNode(data, node.getLeftNode());
                    }
                } else { 
                    System.out.println("数据节点已经存在");
                }
            }
    
            /** * 二叉树节点删除 * * 如果删除节点为叶子节点, 则直接删除 * * 如果删除节点为非叶子节点, 且只有左节点或者有节点其中一个节点, 将子节点设置为该节点 * * 如果删除节点为非叶子节点, 则子节点完整, 则让右子节点代替该节点, 左子节点按顺序挂在右子节点的左侧位置 * * @param targetData * @return */
            public boolean delNode(Integer targetData) { 
                if (null == node) { 
                    return false;
                }
                return doDelNode(targetData, node);
            }
    
            private boolean doDelNode(Integer targetData, Node node) { 
                if (null == node) { 
                    return false;
                }
                if (targetData > node.getData()) { 
                    // 删除值大于当前节点值, 向右查找
                    return doDelNode(targetData, node.getRightNode());
                } else if (targetData < node.getData()) { 
                    // 删除值小于当前节点值, 向左查找
                    return doDelNode(targetData, node.getLeftNode());
                } else { 
                    // 找到后, 进行处理
                    // 获取右侧节点的最左节点
                    Node nextNode = findNextNode(node);
                    // 说明存在右侧节点
                    if (null == nextNode) { 
                        // 直接用左侧节点替换该节点
                        // 如果当前节点是根节点, 直接将根节点替换为其左侧节点
                        if (this.node == node) { 
                            this.node = node.getLeftNode();
                            this.node.setParentNode(null);
                        } else { 
                            // 删除节点是中间节点, 如果是父节点的左侧节点, 则将父节点的左侧节点替换为其左侧节点
                            if (node == node.getParentNode().getLeftNode()) { 
                                node.getParentNode().setLeftNode(node.getLeftNode());
                            } else if (node == node.getParentNode().getRightNode()) { 
                                // 删除节点是中间节点, 如果是父节点的右侧节点, 则将父节点的右侧节点替换为其左侧节点
                                node.getParentNode().setRightNode(node.getLeftNode());
                            }
                            if (null != node.getLeftNode()) { 
                                node.getLeftNode().setParentNode(node.getParentNode());
                            }
                        }
                    } else { 
                        // 存在后继节点
                        // 将当前值替换为后继节点的值
                        node.setData(nextNode.getData());
                        // 将后继节点挂空, 后继节点可能存在右侧节点, 用右侧节点进行替换
                        if (nextNode == nextNode.getParentNode().getLeftNode()) { 
                            nextNode.getParentNode().setLeftNode(nextNode.getRightNode());
                        } else if (nextNode == nextNode.getParentNode().getRightNode()) { 
                            // 删除节点是中间节点, 如果是父节点的右侧节点, 则将父节点的右侧节点替换为其左侧节点
                            nextNode.getParentNode().setRightNode(nextNode.getRightNode());
                        }
                        if (null != nextNode.getRightNode()) { 
                            nextNode.getRightNode().setParentNode(nextNode.getParentNode());
                        }
                    }
                    return true;
                }
            }
    
            /** * 获取右侧节点的最左节点 * @param node * @return */
            private Node findNextNode(Node node) { 
                Node nextNode = node.getRightNode();
                if (null == nextNode) { 
                    return nextNode;
                }
                while (null != nextNode.getLeftNode()) { 
                    nextNode = nextNode.getLeftNode();
                }
                return nextNode;
            }
    
            // 中序输出
            // 先输出左侧节点值
            // 再输出当前节点值
            // 最后输出中间节点值
            // 中序输出结果为有序数组
            public void middleShowDetails() { 
                doMiddleShowDetails(node);
            }
    
            public void doMiddleShowDetails(Node node) { 
                if (null == node) { 
                    return;
                }
                if (null != node.getLeftNode()) { 
                    doMiddleShowDetails(node.getLeftNode());
                }
                System.out.println("Node: " + node.getData());
                if (null != node.getRightNode()) { 
                    doMiddleShowDetails(node.getRightNode());
                }
            }
    
        }
    
        @Data
        @ToString
        static class Node { 
    
            private Integer data;
    
            private Node leftNode;
    
            private Node rightNode;
    
            public Node() { }
    
            public Node(Integer data) { 
                this(data, null, null);
            }
    
            public Node(Integer data, Node leftNode, Node rightNode) { 
                this.data = data;
                this.leftNode = leftNode;
                this.rightNode = rightNode;
            }
    
        }
    }

[20200718203230412.png]: /images/20230209/2655764d498946d187a5493aaa8f82ab.png
[20200718203242978.png]: /images/20230209/c11cf5f711044bffaa470567a0041e5c.png
[20200718203254135.png]: /images/20230209/35f80bfefd634210a6bde6e315590376.png