完全二叉树和满二叉树

完全二叉树实现（基于数组）

完全二叉树除最后一层外，其它各层的节点数目均已达最大值，且最后一层所有节点从左向右连续地紧密排列，故使用数组实现不会造成空间浪费，相比递归更容易理解

原理

根据树的层次结构，可知

  • 若父节点从1开始，其左节点为2n，右节点为2n+1
  • 若父节点从0开始，其左节点为2n+1，右节点为2n+2
  • 若子节点为n，则其父节点为n-1/2

代码实现

  • getTreeNum()获取总节点数，返回size
  • getTreeDepth()获取树高度，n个数两两平分为log2n+1层（层数从1算起）
  • getLeafNum()获取叶节点数，其为总节数减去上层节点数总和（等差数列和为2n+1）
  • getCurrentLevelNum()获取指定层次节点，最后一层即为叶节点数，其余各层都是2的幂
class CompleteBinaryTree<T> {
    private Object[] elements;
    private int size;

    public CompleteBinaryTree() {
        elements = new Object[7];
        size = 0;
    }

    public CompleteBinaryTree(T[] array) {
        elements = array;
        size = array.length;
    }

    public void add(int value) {
        elements[size] = value;
        size++;
    }

    public T remove() {
        T temp = (T) elements[0];
        elements[0] = elements[size - 1];
        elements[size - 1] = 0;
        size--;
        return temp;
    }

    public int getTreeNum() {
        return size;
    }

    public int getTreeHeight() {
        if (size == 0) {
            return 0;
        }
        return (int) (Math.log(size) / Math.log(2)) + 1;
    }
    
    public int getLeafNum() {
        if (size == 0) {
            return 0;
        }
        if (size == 1) {
            return 1;
        }
        return size - (2 * (getTreeDepth() - 2) + 1);
    }

    public int getCurrentLevelNum(int level) {
        if (level > getTreeDepth()) {
            return 0;
        } else if (level == getTreeDepth()) {
            return getLeafNum();
        } else {
            return (int) Math.pow(2, level - 1);
        }
    }

    public void preOrderTraversalWithoutRecursion() {
        Stack<Integer> stack = new Stack<>();
        if (size != 0) {
            stack.push(0);
            while (!stack.empty()) {
                int index = stack.pop();
                visitNode(index);
                if (2 * index + 2 < size) {
                    stack.push(2 * index + 2);
                }
                if (2 * index + 1 < size) {
                    stack.push(2 * index + 1);
                }
            }
        }
    }

    public void MidOrderTraversalWithoutRecursion() {
        Stack<Integer> stack = new Stack<>();
        int index = 0;
        while (index < size || !stack.empty()) {
            if (index < size) {
                stack.push(index);
                index = 2 * index + 1;
            } else {
                index = stack.pop();
                visitNode(index);
                index = 2 * index + 2;
            }
        }
    }

    public void SufOrderTraversalWithoutRecursion() {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        if (size != 0) {
            stack1.push(0);
            while (!stack1.empty()) {
                int index = stack1.pop();
                stack2.push(index);
                if (index * 2 + 1 < size) {
                    stack1.push(index * 2 + 1);
                }
                if (index * 2 + 2 < size) {
                    stack1.push(index * 2 + 2);
                }
            }
            while (!stack2.empty()) {
                visitNode(stack2.pop());
            }
        }
    }

    public void LevelTraversal() {
        for (int i = 0; i < size; i++) {
            visitNode(i);
        }
    }

    private void visitNode(int index) {
        System.out.print((T) elements[index] + " ");
    }

    public boolean BreadthFirstSearch(T value) {
        for (int i = 0; i < size; i++) {
            visitNode(i);
            if ((T) elements[i] == value) {
                return true;
            }
        }
        return false;
    }

    public boolean DepthFirstSearch(T value) {
        Stack<Integer> stack = new Stack<>();
        if (size != 0) {
            stack.push(0);
            while (!stack.empty()) {
                int index = stack.pop();
                visitNode(index);
                if ((T) elements[index] == value) {
                    return true;
                }
                if (2 * index + 2 < size) {
                    stack.push(2 * index + 2);
                }
                if (2 * index + 1 < size) {
                    stack.push(2 * index + 1);
                }
            }
        }
        return false;
    }
}

  • preOrderTraversalWithoutRecursion()：前序遍历，先入栈根节点，再出栈根节点，判断该节点是否存在子节点，若存在则入栈其右左节点，随后出栈其左右节点，即根-左-右

  • MidOrderTraversalWithoutRecursion()：中序遍历，先入栈根节点，再循环入栈其全部左节点，直到左节点全部入栈，出栈左节点，再出栈子树根节点判断是否有右节点，若有则入栈，随后出栈右节点，即左-根-右

  • SufOrderTraversalWithoutRecursion()：后序遍历，栈1入栈根节点，出栈并入栈2，栈1入栈左右节点，每次出栈右左节点，故栈2出栈顺序为左-右-根

  • LevelTraversal：层次遍历，由于完全二叉树是按顺序摆放的，故根据下标顺序遍历即可

  • BreadthFirstSearch()：广度优先搜索，同层次遍历

  • DepthFirstSearch()：深度优先搜索，同前序遍历

测试代码

Integer[] array = {1, 2, 3, 4, 5, 6};
CompleteBinaryTree completeBinaryTree = new CompleteBinaryTree(array);
System.out.print("不用递归前序遍历：");
completeBinaryTree.preOrderTraversalWithoutRecursion();
System.out.println();
System.out.print("不用递归中序遍历：");
completeBinaryTree.MidOrderTraversalWithoutRecursion();
System.out.println();
System.out.print("不用递归后序遍历：");
completeBinaryTree.SufOrderTraversalWithoutRecursion();
System.out.println();
System.out.print("层次遍历: ");
completeBinaryTree.LevelTraversal();
System.out.println();
System.out.print("广度优先搜索: ");
boolean breadthFirstResult = completeBinaryTree.BreadthFirstSearch(5);
System.out.print(breadthFirstResult ? "found" : "not found");
System.out.println();
System.out.print("深度优先搜索: ");
boolean depthFirstResult = completeBinaryTree.DepthFirstSearch(5);
System.out.print(depthFirstResult ? "found" : "not found");
System.out.println();
System.out.println("树高度：" + completeBinaryTree.getTreeHeight());
System.out.println("总节点数：" + completeBinaryTree.getTreeNum());
System.out.println("叶节点数：" + completeBinaryTree.getLeafNum());
System.out.println("第三层节点数：" + completeBinaryTree.getCurrentLevelNum(3));

这里的打印同上面普通的二叉树

不用递归前序遍历：1 2 4 5 3 6 
不用递归中序遍历：4 2 5 1 6 3 
不用递归后序遍历：4 5 2 6 3 1 
层次遍历: 1 2 3 4 5 6 
广度优先搜索: 1 2 3 4 5 found
深度优先搜索: 1 2 4 5 found
树高度：3
总节点数：6
叶节点数：3
第三层节点数：3

完全二叉树、堆和优先级队列的关系

为了保证完全二叉树的性质，上面代码的

  • add()：添加元素到二叉树尾部
  • remove()：删除头部元素，并将末尾元素补上（或删除元素移动后序元素）

无参数指定的删除对于普通的二叉树是无任何意义的，因为无法知道接下来获取的元素是哪个

但对基于完全二叉树实现的堆，每次删除可获取最大或最小值

与此同时，添加元素默认添加到尾部，根据这两个特性可进一步构成优先级队列

具体介绍可看数据结构——堆和优先级队列

满二叉树实现

每层节点都达到最大值（即2的幂）的二叉树为满二叉树，其也用数组实现，原理同完全二叉树，不再赘述

# 数据结构 # 算法 # java
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

cover

大数据毕业设计选题推荐-基于大数据的农作物产量数据分析与可视化系统-Hadoop-Spark-数据可视化-BigData

avatar 魔乐社区
cover

大模型推理适配实战：手把手带你完成vLLM Ascend迁移实操

avatar 魔乐社区
cover

基于python大数据的汽车数据分析系统设计与实现

avatar 魔乐社区