復旦大学961-データ構造-第2章-ツリー(4)-完全ツリーの配列格納形式

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; //          ，      ，      ；
        }
    }
}

基本的な考え方:

は、すでにアクセスするノード

を格納するために、Setのセットを初期化する.

はルートノードから始まり、ルートノードがアクセスしていない場合はアクセスし、左サブツリーがアクセスされているかどうかを判断し、アクセスしていない場合は左サブツリーにアクセスし、左サブツリーがアクセスされている場合は右サブツリーがアクセスされているかどうかを判断し、右サブツリーがアクセスされていない場合は右サブツリーにアクセスする.左右のサブツリーがアクセスされると、現在のノードの親ノードが返されます.

ここでは,アクセスされた左右のノードを記録するためにSetを用いたので,空間複雑度はO(n)である.実際には必要ありません.しかし、どうすればいいかよく考えていません.コメントエリアで修正してください.
方法2:普通の二叉木の非再帰前序遍歴と同じ方法

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は試験を受けないべきで,まずやらない.