【数据结构-Java】实现二叉树

超、凢脫俗 2023-01-06 14:56 172阅读 0赞

> 能提高数据存储，读取的效率, 比如利用 二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也 可以保证数据的插入，删除，修改的速度。

1.  二叉树的子节点分为左节点右节点
2.  每个节点最多只能有两个子节点

<table> 
 <thead> 
  <tr> 
   <th>1）节点：节点对象2）根节点：3）父节点4）子节点5）叶子节点：没有子节点的节点6）节点的权：（节点的值）7）路径：从根节点找到该节点的路线8）层：9）子树：10）树的高度：11）森林：多棵子树构成的森林</th> 
   <th><img src="https://img-blog.csdnimg.cn/img_convert/150239df02a5d00851bf6ea80f73c08c.png" alt="image.png"></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td></td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

>  *  满二叉树：如果该二叉树的所有叶子节点都在最后一层，并且节点总数=2^n-1,n为层数
>  *  完全二叉树：如果该二叉树所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续

二叉树的代码实现：
        //创建树
        class binaryTree { 
            private Node root;
        
            public void setRoot(Node root) { 
                this.root = root;
            }
        
            public void delete(int index){ 
                if(this.root==null){ 
                    return;
                }
                this.root.delete(index);
            }
        
            //前序遍历查找
            public Node preOrdersearch(int index) { 
                if (this.root == null) { 
                    return null;
                }
                Node node = this.root.preOrdersearch(index);
                return node;
            }
        
            //中序遍历查找
            public Node infixOrdersearch(int index) { 
                return this.root.infixOrdersearch(index);
            }
        
            //后续
            public Node postOrdersearch(int index) { 
                return this.root.postOrdersearch(index);
            }
        
            //前序遍历
            public void preOrder() { 
                if (this.root != null) { 
                    this.root.preOrder();
                } else { 
                    throw new RuntimeException("没有节点");
                }
            }
        
            public void infixOrder() { 
                if (this.root != null) { 
                    this.root.infixOrder();
                } else { 
                    throw new RuntimeException("没有节点");
                }
            }
        
            public void postOrder() { 
                if (this.root != null) { 
                    this.root.postOrder();
                } else { 
                    throw new RuntimeException("没有节点");
                }
            }
        }

**节点**

/** * 节点 */
    class Node { 
        private int no;
        private String name;
        private Node left;//左节点
        private Node right;//右节点
    
        public Node(int no, String name) { 
            this.no = no;
            this.name = name;
        }
    
        //删除节点
        public void delete(int no){ 
            if(this.left!=null&&this.left.no == no){ 
                this.left = null;
                return;
            }
            if(this.right!=null&&this.right.no==no){ 
                this.right = null;
                return;
            }
            if(this.left!=null){ 
                this.left.delete(no);
            }
            if(this.right!=null){ 
                this.right.delete(no);
            }
        }

#### 二叉树的遍历： ####

1、前序遍历：先输出父节点，再遍历左子树和右子树

1.  先输出当前节点（初始的时候是root节点）
2.  如果左节点不为空，则递归继续前序遍历
3.  如果右节点不为空，则递归继续前序遍历

2、中序遍历：先遍历左子树，再输出父节点，再遍历右子树

1.  如果左节点不为空，则递归继续中序遍历
2.  先输出当前节点
3.  如果有节点不为空，则递归继续中序遍历

3、后序遍历：先遍历左子树，再遍历右子树，最后输出父节点

1.  如果左子节点不为空，则递归继续后序遍历
2.  如果当前节点的右子节点不为空，则递归后序遍历
3.  先输出当前节点

/** * 前序遍历 * 1、先输出当前节点 * 2、判断当前节点左子节点是否存在，存在则向左子节点进行前序遍历 * 2、判断当前节点右子节点是否存在，存在则进行前序遍历 */
        public void preTra() { 
            System.out.println(this);//输出父结点
            if (this.left != null) this.left.preTra();//向左子树遍历
            if (this.right != null) this.right.preTra();//向右子树遍历
        }
    
        /** * 中序遍历 * 1、先判断当前节点左子节点是否为空，不为空则进行中序遍历 * 2、输出当前节点 * 3、判断当前节点左子节点是否为空，不为空进行中序遍历 */
        public void inorderTra() { 
            if (this.right != null) this.left.inorderTra();
            System.out.println(this);
            if (this.left != null) this.right.inorderTra();
        }
    
        /** * 后序遍历 * 1、判断当前节点左子节点是否为空，不为空则进行后序遍历 * 2、判断右子节点 * 3、输出当前节点 */
        public void postTra() { 
            if (this.left != null) this.left.postTra();
            if (this.right != null) this.right.postTra();
            System.out.println(this);
        }

#### 二叉树的查找： ####

*  前序查找
 *  中序查找
 *  后续查找

/** * 前序遍历查找 */
        public TreeNode preTraFind(int no) { 
            if (no == this.no) { 
                return this;
            }//找到该节
            TreeNode resNode = null;
            if (this.left != null) { //向左子树遍历
                resNode = this.left.preTraFind(no);
            }
            if (this.right != null) { //向右子树遍历
                resNode = this.right.preTraFind(no);
            }
            return resNode;
        }
    
        /** * 中序遍历查找 */
        public TreeNode inorderTraFind(int no) { 
            TreeNode resNode = null;
            if (this.left != null) resNode = this.left.inorderTraFind(no);
            if (no == this.no) { 
                return this;
            }
            if (this.right != null) resNode = this.right.inorderTraFind(no);
            return resNode;
        }
    
        /** * 后序遍历查找 */
        public TreeNode postTraFind(int no) { 
            TreeNode resNode = null;
            if (this.left != null) resNode = this.left.postTraFind(no);
            if (this.right != null) resNode = this.right.postTraFind(no);
            if (this.no == no) return this;
            return resNode;
        }

#### 删除结点 ####

##### 1、情况一 #####

1.  如果删除的节点是叶子节点，则删除该节点
2.  如果删除的节点是非叶子节点，则删除该子树

思路

1.  因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断 当前这个结点是不是需要删除结点
2.  如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将 this.left = null; 并且就返回 (结束递归删除)
3.  如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将 this.right= null ;并且就返回 (结束递归删除)
4.  如果第 2 和第 3 步没有删除结点，那么我们就需要向左子树进行递归删除
5.  如果第 4 步也没有删除结点，则应当向右子树进行递归删除.
6.  如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将 this.left = null; 并且就返回(结 束递归删除)

![image.png][]

/** * 删除节点 * * @param no */
        public void deleteNode(int no) { 
            if (this.left != null && this.left.no == no) { 
                this.left = null;
                return;
            }
            if (this.right != null && this.right.no == no) { 
                this.right = null;
                return;
            }
            if (this.left != null) this.left.deleteNode(no);
            if (this.right != null) this.right.deleteNode(no);
        }

##### 2、情况二 #####

如果要删除的节点是非叶子节点，现在我们不希望将该非叶子节点为根节点的子树删除，需要指定规则, 假如

规定如下:

1.  如果该非叶子节点 A 只有一个子节点 B，则子节点 B 替代节点 A
2.  如果该非叶子节点 A 有左子节点 B 和右子节点 C，则让左子节点 B 替代节点 A。

/** * 删除节点， * 如果要删除的节点是非叶子节点，现在我们不希望将该非叶子节点为根节点的子树删除， * 需要指定规则, 假如 规定如下: * 2) 如果该非叶子节点 A 只有一个子节点 B，则子节点 B 替代节点 A * 3) 如果该非叶子节点 A 有左子节点 B 和右子节点 C，则让左子节点 B 替代节点 A。 * * @param no */
        public void deleteNodeSec(int no) { 
            if (this.left != null && this.left.no == no) { 
                if(this.left.left == null&& this.left.right==null){ 
                    this.left = null;
                    return;
                }else if(this.left.left != null&& this.left.right==null){ 
                    this.left = this.left.left;
                    return;
                }else if(this.left.left == null&& this.left.right!=null){ 
                    this.left = this.left.right;
                    return;
                }else { //两边都不为空
                    this.left = this.left.left;
                    //找到右子树最后一个节点将右节点放过去
                    TreeNode finaNode = getFinaNode();
                    finaNode.right = this.left.right;
                }
            }
    
            if (this.right != null && this.right.no == no) { 
                if(this.right.left == null&& this.right.right==null){ 
                    this.right = null;
                    return;
                }else if(this.right.left != null&& this.right.right==null){ 
                    this.right = this.right.left;
                    return;
                }else if(this.right.left == null&& this.right.right!=null){ 
                    this.right = this.right.right;
                    return;
                }else { //两边都不为空
                    this.right = this.right.left;
                    //找到右子树最后一个节点将右节点放过去
                    TreeNode finaNode = getFinaNode();
                    finaNode.left = this.left.right;
                }
            }
        }

[image.png]: /images/20221119/df566064736941578c39f5ec4ff7d249.png