完全二叉树的深度优先、广度优先遍历的实现

旧城等待， 2023-03-13 16:22 174阅读 0赞

\*\*完全二叉树：\*\*对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树;

**深度优先遍历实现方法：**

public static void show(Node tree){ 
        System.out.println(tree.value);
        if (tree.right != null){ 
            treeShow(tree.right);
        }
        if (tree.left != null){ 
            treeShow(tree.left);
        }
    }

**广度优先遍历实现方法：**（必须用到队列）

> 给定一个数组，建立二叉树并进行广度优先遍历  
> 构建：新建一个队列，创建一个结点，value是数组的第一个元素的值，把结点放入队列。开始循环，每一次循环从队列中拿出一个结点，然后再新建两个结点作为该结点的左右孩子结点，再从数组中拿出两个值作为两个孩子结点的值。然后把左右孩子结点分别加入队列，照此循环，最后遍历到数组末尾就可以构建完成二叉树  
> 遍历：新建一个队列，把根节点放入队列，从队列中拿出一个节点，将该节点的左右孩子放入队列，然后再拿出一个节点，再将他的左右孩子放入队列，循环操作。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQxOTIwMDY1_size_16_color_FFFFFF_t_70]

public class Test { 
        public static void main(String[] args) { 
        	//创建一个数组
            int[] num = new int[] { 12,32,24,31,23,11,34,55,22,33};
            //定义一个新节点
            Node node = new Node();
            //将数组的第一个数据赋值给节点对象的数据域
            node.data= num[0];
            //创建一个节点类型的队列，用于存放节点
            Queue<Node> queue = new LinkedList<>();
            //向队列中添加节点
            queue.offer(node);
            for (int i = 1; i < num.length;) { 
            	//新建一个节点
                Node node1 = new Node();
                //将队列中的头部元素赋值给该节点，并移除
                node1 = queue.poll();
                //创建左右两个节点
                Node left = new Node();
                Node right = new Node();
                node1.left = left;
                node1.right = right;
                if(i< num.length) { 
                    left.data = num[i];
                    queue.offer(left);
                }
                if(i + 1 < num.length) { 
                    right.data = num[i + 1];
                    queue.offer(right);
                }
                i += 2;
            }
            System.out.println(node);
            show(node);
        }
        //输出显示
        public static void show(Node tree){ 
        
            Queue<Node> queue = new LinkedList<>();
            queue.offer(tree);
            for (;!queue.isEmpty();) { 
                tree = queue.poll();
                System.out.println(tree.data);
                if(tree.left != null) { 
                    queue.offer(tree.left);
                }
                if(tree.right != null){ 
                    queue.offer(tree.right);
                }
            }
        }
    }

运行截图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQxOTIwMDY1_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQxOTIwMDY1_size_16_color_FFFFFF_t_70]: /images/20230312/c57204c3d3d54726a7e662bc3f1969b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQxOTIwMDY1_size_16_color_FFFFFF_t_70 1]: /images/20230312/331453fa5e31428b9022f69f2950c6f7.png