二叉树概念及基本功能实现

小鱼儿 2023-09-25 19:16 60阅读 0赞

**目录**

一、二叉树概述

二、代码实现一棵二叉树：

三、二叉树的遍历

四、二叉树遍历代码实现

1.先序遍历：

2.中序遍历：

3.后序遍历：

4.层次遍历（一层一层遍历）：

5.main方法执行

五、二叉树的查询和删除：

1.二叉树的查询：

2.二叉树的删除：

3.main方法执行：

六、二叉树深度的计算

七、线索化二叉树：

八、堆排序概述：

## 一、二叉树概述 ##

二叉树是每个节点最多有两个子树的树结构，也就是说树的度是2.

满二叉树：每一层的结点数都达到最大值。

完全二叉树：若设二叉树的深度为k，除第k层外，其他各层（1~k-1）的结点数都达到最大个数，第k层所有的结点都连续集中在最左边，这就是完全二叉树。

**注：**完全二叉树的话，所有的结点都连续集中在最左边，也就是如下图所示，右子节点可以没有，但如果右子节点有的话，则左子节点必须存在。下图中如果叶子结点只有4结点，5、6、7结点没有的话，也是完全二叉树。

![20766872262a4747a895a8091f72866c.png][]

## 二、代码实现一棵二叉树： ##

1.定义结点 2.创建一棵树，手动创建子节点 3.定义一个根节点

public class BinaryTree {
        //定义一个根节点
        Node root;
    
        //定义结点类
        public class Node{
            //存储数据节点
            Object item;
            //左子节点
            Node left;
            //右子节点
            Node right;
    
            public Node(Object obj){
                this.item = obj;
            }
        }
    
        //创建一棵树
        public void createTree(){
            //创建根节点
            root = new Node(1);
            //创建左子节点
            Node leftNode = new Node(2);
            //创建右子节点
            Node rightNode = new Node(3);
    
            //把左右子节点关联到根节点
            root.left = leftNode;
            root.right = rightNode;
    
            //创建左子节点的左子节点
            Node leftLeftNode = new Node(4);
            //创建左子节点的右子节点
            Node leftRightNode = new Node(5);
    
            //把左节点的左右子节点关联到左节点
            leftNode.left = leftLeftNode;
            leftNode.right = leftRightNode;
    
            //创建右子节点的左子节点
            Node rightLeftNode = new Node(6);
            //创建右子节点的右子节点
            Node rightRightNode = new Node(7);
    
            //把右结点的左右子节点关联到右节点
            rightNode.left = rightLeftNode;
            rightNode.right = rightRightNode;
        }
    }

## 三、二叉树的遍历 ##

![758cd5747e6440c7acd4ecaff33198b8.png][]

![c2f432134f504ae8a51c6aae54b6977c.png][]

注：每次遍历的时候，大化小，也就是把大的树化成一颗颗小的树。

比如先序遍历：根左右，先遍历根“1”，然后左子树“2 4 5”作为整体充当根节点的左子树，再进行先序遍历。最后遍历结果就是 1 245 367

## 四、二叉树遍历代码实现 ##

### **1.先序遍历：** ###

//实现先序遍历
        public void preTrival(Node node){
            //退出的条件
            if (node == null){
                return;
            }
            //先遍历根节点
            System.out.print(node.item+" ");
            //遍历左子树
            preTrival(node.left);
            //遍历右子树
            preTrival(node.right);
        }

### **2.中序遍历：** ###

//实现中序遍历
        public void midTrival(Node node){
            //退出的条件
            if (node == null){
                return;
            }
            //遍历左子树
            midTrival(node.left);
            //先遍历根节点
            System.out.print(node.item+" ");
            //遍历右子树
            midTrival(node.right);
        }

### **3.后序遍历：** ###

//实现后序遍历
        public void postTrival(Node node){
            //退出的条件
            if (node == null){
                return;
            }
            //遍历左子树
            postTrival(node.left);
            //遍历右子树
            postTrival(node.right);
            //先遍历根节点
            System.out.print(node.item+" ");
        }

> **注：由上面代码规律可以看出，除了根节点是直接打印其值之外，左节点、右节点都是通过递归遍历的方式遍历到。如：**
> 
> **先序遍历：**打印根节点--->递归遍历左节点--->递归遍历右节点
> 
> **中序遍历：**递归遍历左节点--->打印根节点--->递归遍历右节点
> 
> **后序遍历：**递归遍历左节点--->递归遍历右节点--->打印根节点

### **4.层次遍历（一层一层遍历）：** ###

**思路：**将根节点放入一个队列中，然后每次取出这个节点后，相应地将它的左右子节点依次放入队列中，按照队列的先进先出的特性，依次将元素出队列并打印。（如果觉得抽象，可以画图感受一下。）

//实现层次遍历(就是一层一层遍历)
        //思路：将根节点放入一个队列中，然后每次取出这个节点后，相应地将它的左右子节点依次放入队列
        //     中，按照队列的先进先出的特性，依次将元素出队列并打印。
        public void levelTrival(Node node){
            //创建一个队列
            ArrayDeque<Node> queue = new ArrayDeque<Node>(10);
            //将开始的结点放入到队列中
            queue.add(node);
            while (!queue.isEmpty()){
                //将队列中的结点出列
                Node n = queue.poll();
                System.out.print(n.item+" ");
                //将左子节点放入到队列中
                if (n.left != null){
                    queue.add(n.left);
                }
                //将右子节点放入到队列中
                if (n.right != null){
                    queue.add(n.right);
                }
            }
        }

### 5.main方法执行 ###

public class TestBinaryTree {
        public static void main(String[] args) {
            BinaryTree bTree = new BinaryTree();
            //创建二叉树
            bTree.createTree();
            //执行前序遍历二叉树
            bTree.preTrival(bTree.root);
    
            System.out.println("--------------------");
    
            //执行中序遍历二叉树
            bTree.midTrival(bTree.root);
    
            System.out.println("---------------------");
    
            //执行后序遍历二叉树
            bTree.postTrival(bTree.root);
    
            System.out.println("---------------------");
    
            //执行层次遍历
            bTree.levelTrival(bTree.root);
        }
    }

## 五、二叉树的查询和删除： ##

### 1.二叉树的查询： ###

查询可以选择任意一种遍历方式，在遍历的同时对当前元素的值进行比较判断。

这里选用先序遍历的方式来实现：

//实现树的查询,按先序遍历
        //思路：可以选择任意一种遍历方式，在遍历的同时对当前元素的值进行比较判断即可。
        public Node preSearch(Node node, Object obj){
            //先判断树是否为null
            if (node == null){
                return null;
            }
            //定义一个target用于接收preSearch的返回值,如果找到则接收当前结点，否则接收null
            Node target = null;
            if (node.item == obj){
                //找到元素
                return node;
            }else {
                //先遍历左子树
                target = preSearch(node.left,obj);
                //判断是否找到元素
                if (target != null){
                    return target;
                }
                //再遍历右子树
                target = preSearch(node.right,obj);
                //判断是否找到元素
                if (target != null){
                    return target;
                }
            }
            return null;
        }

### 2.二叉树的删除： ###

因为二叉树不像平衡树那么复杂，删除元素要考虑到平衡等因素，所以删除二叉树的元素时，如果是叶子结点则直接赋予null，如果是非叶子结点则将整个子树删除，也就是给当前非叶子结点赋予null。

//实现树的删除
        //思路：遍历树将树的每一个元素与目标值进行比较，找到了就将其设为null，
        //     如果是叶子结点，则直接设为null，如果是非叶子结点，就将整个子树删除，也就是将此节点设为null即可。
        public void deleteNode(Node node,Object obj){
            //先判断树是否为空
            if (node == null){
                return;
            }
            //判断根节点是否为目标结点
            if (node == root && root.item == obj){
                this.root = null;
            }
    
            //判断子节点是否为目标
            //先判断左子树是否存在目标
            if (node.left != null){
                if (node.left.item == obj){
                    //删除左子节点
                    node.left = null;
                    return;
                }else {
                    //从子树中进行删除
                    deleteNode(node.left,obj);
                }
            }
            //再判断右子树是否存在目标
            if (node.right != null){
                if (node.right.item == obj){
                    //删除左子节点
                    node.right = null;
                    return;
                }else {
                    //从子树中进行删除
                    deleteNode(node.right,obj);
                }
            }
        }

### 3.main方法执行： ###

public class TestBinaryTree02 {
        public static void main(String[] args) {
            BinaryTree bTree = new BinaryTree();
            bTree.createTree();
    
            //查询结点
            BinaryTree.Node result = bTree.preSearch(bTree.root, 13);
            if (result != null){
                System.out.println("结果："+result.item);
            }else {
                System.out.println("没有此节点");
            }
    
            //删除结点
            bTree.deleteNode(bTree.root,2);
            bTree.levelTrival(bTree.root);
        }
    }

## 六、二叉树深度的计算 ##

//二叉树高度的计算你（深度）
        //思路：将左子树与右子树进行递归比较，最后返回最深的值。
        //     比如从根节点开始，比较其左子树、右子树，到了左子树、右子树这边，再比较其对应的左子树右子树，
        //     以此循环，用递归的方式来判断。
        public int maxDepth(Node node){
            //先判断树是否为空
            if (node == null){
                return 0;
            }
    
            int leftDepth = 0;
            int rightDepth = 0;
    
            //1.先获取左子树的高度
            if (node.left != null){
                leftDepth = maxDepth(node.left);
            }
            //2.再获取右子树的高度
            if (node.right != null){
                rightDepth = maxDepth(node.right);
            }
            //3.判断左右子树谁大
            if (leftDepth > rightDepth){
               return leftDepth + 1;
            }else {
                return rightDepth + 1;
            }
        }

## 七、线索化二叉树： ##

在使用前序、中序、后序遍历的时候，都会用到递归，过多的使用递归可能会导致栈内存的溢出，这个时候可能通过将二叉树进行线索化，来避免使用递归进行树的遍历。

![f113c0ea41f945958836497a0e888929.png][]

在有N个节点的二叉树中会存在N+1个空指针域。可以利用这些空指针域，存放指向节点在某种遍历（前、中、后）下的前驱或后继节点的指针。

> 公式：2n（n-1），每个节点有两个指针，如果需要连接其他节点必须要使用n-1个指针，剩下的指针就是空的。

这种加了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树（Threaded BinaryTree）。

**线索二叉树的应用：**

（1）首先将二叉树进行线索化

（2）然后直接通过循环添加的线索遍历树，从而避免使用递归

## 八、堆排序概述： ##

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法，它是一种选择排序，它的最坏、最好、平均时间复杂度均为O（nlog![2^\{n\}][2_n]）

**堆是一棵完全二叉树：**

（1）当所有的结点的值都大于或者等于其左右的子节点的值称为大顶堆。

（2）当所有的结点的值都小于或者等于其左右的子节点的值称为小顶堆。

![4ad8eacc243441ebbc26bcdd762e4f1f.png][]

[20766872262a4747a895a8091f72866c.png]: https://img-blog.csdnimg.cn/20766872262a4747a895a8091f72866c.png
[758cd5747e6440c7acd4ecaff33198b8.png]: https://img-blog.csdnimg.cn/758cd5747e6440c7acd4ecaff33198b8.png
[c2f432134f504ae8a51c6aae54b6977c.png]: https://img-blog.csdnimg.cn/c2f432134f504ae8a51c6aae54b6977c.png
[f113c0ea41f945958836497a0e888929.png]: https://img-blog.csdnimg.cn/f113c0ea41f945958836497a0e888929.png
[2_n]: https://latex.csdn.net/eq?2%5E%7Bn%7D
[4ad8eacc243441ebbc26bcdd762e4f1f.png]: https://img-blog.csdnimg.cn/4ad8eacc243441ebbc26bcdd762e4f1f.png