复旦大学961-数据结构-第二章-树（4）-完全树的数组存储形式

你的名字 2022-12-11 13:45 144阅读 0赞

[961全部内容链接][961]

### 文章目录 ###

*  完全二叉树的数组表示形式
 *   *  完全二叉树的Java定义
     *  完全二叉树的前序遍历（递归）
     *  完全二叉树的前序遍历（非递归）
     *  完全二叉树的中序遍历（递归）
     *  完全二叉树的中序遍历（非递归）
     *  完全二叉树的后序遍历（递归）
     *  完全二叉树的后序遍历（非递归）
 *  完全n叉树的数组存储形式

# 完全二叉树的数组表示形式 #

## 完全二叉树的Java定义 ##

public class CompleteBinaryTree { 
    
        private final static int MAX_SIZE = 100;
        Object[] elements = new Object[MAX_SIZE];
        int size; // 当前完全二叉树的元素个数
    }

## 完全二叉树的前序遍历（递归） ##

private static void preOrder(Object[] elements, int i) { 
        if (i>=elements.length || elements[i] == null) return;
        System.out.print(elements[i] + " " );  // 输出根节点
        preOrder(elements, i * 2); // 访问左孩子
        preOrder(elements, i * 2 + 1); // 访问右孩子
    }
    
    public static void preOrder(CompleteBinaryTree tree) { 
        preOrder(tree.elements, 1); // 从1开始，0不存储数据，方便计算
    }

## 完全二叉树的前序遍历（非递归） ##

public static void preOrder(CompleteBinaryTree tree) { 
        Object[] elements = tree.elements;
        int i = 1; // 第0个位置不存储数据，方便计算
        Set set = new HashSet(); // 用于记录已经被访问过的节点
        while (i > 0) { 
            if (!set.contains(elements[i])) { 
                // 若该节点没有被访问过，则访问该节点，并记录
                System.out.print(elements[i] + " ");
                set.add(elements[i]);
            }
            if (i * 2 < elements.length && elements[i * 2] != null  // 若有左孩子且没有被访问过，则访问左孩子
                    && !set.contains(elements[i * 2])) { 
                i = i * 2; // 访问左孩子
            } else if (i * 2 + 1 < elements.length && elements[i * 2 + 1] != null &&
                    !set.contains(elements[i * 2 + 1])) {  // 若有右孩子且没有被访问过，则访问右孩子
                i = i * 2 + 1; // 访问右孩子
            } else { 
                i = i / 2; // 如果左右孩子都为空，或都被访问过，则回到父节点；
            }
        }
    }

基本思路：

1.  初始化一个Set集合，来存放已经被访问过的节点
2.  从根节点开始，若根节点没访问过，则访问，然后判断其左子树是否被访问过，若没访问过，则访问左子树，若左子树被访问过，则判断右子树是否被访问过，若右子树没有被访问则访问右子树。若左右子树都被访问过，则返回当前节点的父节点。

这里我使用了一个Set来记录被访问过的左右节点，所以空间复杂度为O(n)。实际上根本没必要。但是没仔细想怎么弄，欢迎在评论区帮忙改正。

**方法二**：与普通二叉树的非递归前序遍历一样的方式

public static void preOrder(CompleteBinaryTree tree) { 
        Object[] elements = tree.elements;
        int i = 1; // 第0个位置不存储数据，方便计算
        Stack<Integer> stack = new Stack<>(); // 初始化栈，用于存储各个子树的根节点
        while (i < tree.size + 1 || stack.size() > 0) {  // 如果要访问的节点不为空或者栈不为空，则继续
            if (i < tree.size + 1) {  // 如果要访问的节点不为空，则输出，然后入栈，接着访问其左子树
                System.out.print(elements[i] + " ");
                stack.push(i);
                i = i * 2;
            } else {  // 若要访问的节点为空，则从栈中弹出一个根节点，然后访问该根节点的右子树
                int temp = stack.pop();
                i = temp * 2 + 1;
            }
        }
    }

## 完全二叉树的中序遍历（递归） ##

private static void inOrder(Object[] elements, int i) { 
        if (i>=elements.length || elements[i] == null) return;
        inOrder(elements, i * 2); // 访问左孩子
        System.out.print(elements[i] + " " );  // 输出根节点
        inOrder(elements, i * 2 + 1); // 访问右孩子
    }
    
    public static void inOrder(CompleteBinaryTree tree) { 
        inOrder(tree.elements, 1); // 从1开始，0不存储数据，方便计算
    }

## 完全二叉树的中序遍历（非递归） ##

todo

## 完全二叉树的后序遍历（递归） ##

private static void postOrder(Object[] elements, int i) { 
        if (i>=elements.length || elements[i] == null) return;
        postOrder(elements, i * 2); // 访问左孩子
        postOrder(elements, i * 2 + 1); // 访问右孩子
        System.out.print(elements[i] + " " );  // 输出根节点
    }
    
    public static void postOrder(CompleteBinaryTree tree) { 
        postOrder(tree.elements, 1); // 从1开始，0不存储数据，方便计算
    }

## 完全二叉树的后序遍历（非递归） ##

todo

# 完全n叉树的数组存储形式 #

todo 应该不考，先不弄

[961]: https://blog.csdn.net/zhaohongfei_358/article/details/111414370