데이터 구조 - 트 리 (1): 트 리 의 디자인 취지 와 이 진 트 리 의 앞 순서, 중간 순서, 뒤 순서 옮 겨 다 니 기 (재 귀 와 순환 두 가지 버 전)

나무의 설계 취지
조작 시간 복잡 도

나무 라 는 데이터 구조의 등장 은 주로 링크 데이터 구조 에 대한 최적화 이다. 링크 데이터 구 조 는 선형 구조 이 고 조작 은 보통 O (N) 의 시간 복잡 도 를 필요 로 한다. 나 무 는 링크 의 변형 이다. 즉, 링크 의 모든 노드 는 하나의 노드 를 포함 하고 나무의 노드 는 여러 개의 노드 를 포함 할 수 있다. 예 를 들 어 이 진 트 리 를 뿌리 노드, 왼쪽 노드 로 할 수 있다.오른쪽 노드 의 세 노드 는 하나의 큰 노드 를 구성 하기 때문에 링크 에 비해 같은 노드 의 개 수 는 이런 큰 노드 가 존재 하기 때문에 길이 가 작 아 지고 매번 에 더 많은 키 노드 의 정 보 를 얻 을 수 있 으 며 조작 시간 복잡 도 도 도 줄 어 들 었 다. 예 를 들 어 이 진 트 리 는 보통 O (logN) 이 고 다 중 검색 트 리 는 노드 가 더욱 크 기 때문에 경로 가 더욱 짧 고 조작 시간 이 복잡 도가 더욱 작다.사실은 공간 이 시간 을 바 꾸 는 디자인 이다.

컴퓨터 분야 만 이런 사고방식 으로 최적화 하 는 것 이 아니 라 생활 분야 도 덧셈 과 곱셈 이다. 사실은 곱셈 은 모두 덧셈 으로 대체 할 수 있 지만 곱셈 을 사용 하 는 것 은 덧셈 에 비해 더욱 간단 하 다. 예 를 들 어 10 개 를 더 하면 덧셈 은 1 + 1 +... + 1 을 써 야 하고 곱셈 은 10 * 1 만 써 야 한다.인간 에 게 이 기호의 의 미 를 알 리 기만 하면 된다.

알고리즘 설계

최적화 시간 복잡 도 를 제외 하고 나무의 모든 노드 는 디자인 의도 에 따라 서로 다른 데 이 터 를 저장 할 수 있 고 뿌리 노드, 서브 트 리 의 차이 에 따라 디자인 할 수 있다. 예 를 들 어 이 진 트 리 가 산술 표현 식 을 처리 할 때 좌우 노드 는 조작 수 를 저장 할 수 있 고 뿌리 노드 는 조작 자 를 저장 할 수 있다.정렬 에 사용 하면 왼쪽 노드 에 가장 작은 데 이 터 를 저장 하고 뿌리 노드 가 그 다음 에 오른쪽 노드 에 가장 큰 데 이 터 를 저장 합 니 다.

이 진 트 리

정의: 각 노드 는 두 개의 노드 를 포함 하 는데 이 두 노드 는 각각 왼쪽 노드 와 오른쪽 노드 라 고 부른다. 다음 과 같다.

/**
 * @author xyz
 * @date 30/3/2019 10:57
 * @description:
 */

public class BinaryTree<T> {
    public T val;
    public BinaryTree<T> left;
    public BinaryTree<T> right;

    public BinaryTree(T val) {
        this.val = val;
    }
}

나무의 각 노드

데이터 정렬: 트 리 노드 에 수치 저장

1. 선착순 옮 겨 다 니 기

개념: 먼저 뿌리 노드 를 옮 겨 다 니 고 왼쪽 노드 를 옮 겨 다 니 며 마지막 으로 오른쪽 노드 를 옮 겨 다 닌 다.

뿌리 노드 - > 왼쪽 나무 - > 오른쪽 나무

순환 실현

/**
 *     ：root -> left -> right
 * @param root
 */
public void preTraversalRecursive(BinaryTree<Integer> root) {
    if (root == null) {
        return;
    }

    // root
    System.out.print(root.val + ",");

    // left
    if (root.left != null) {
        preTraversalRecursive(root.left);
    }

    // right
    if (root.right != null) {
        preTraversalRecursive(root.right);
    }
}

순환 실현

스 택 (후진 선 출) 과 결합 하여 이 루어 집 니 다. 뿌리 가 먼저 스 택 에 들 어간 다음 에 순환 적 으로 옮 겨 다 니 기 시작 합 니 다. 뿌리 노드 가 스 택 에서 나 오고 먼저 오른쪽 나무 가 스 택 에 들 어간 다음 에 왼쪽 나무 가 스 택 에 들 어 갈 때 왼쪽 나무 가 먼저 스 택 에서 나 오고 오른쪽 나무 가 나중에 스 택 에서 나 옵 니 다. 실현: root - > left - > right.아래 의 중 서 는 후 서 디자인 사고 와 유사 하 다.

//    （    ）   ：    ，        ：     ，      ，        ；     ...
public void preTraversal(BinaryTree<Integer> root) {
    Stack<BinaryTree<Integer>> stack = new Stack<>();
    if (root == null) {
        return;
    }
    stack.push(root);

    while (!stack.isEmpty()) {
        BinaryTree<Integer> current = stack.pop();

        // root
        System.out.print(current.val + ",");

        //         ，       ，      ，       ，      
        if (current.right != null) {
            stack.push(current.right);
        }

        if (current.left != null) {
            stack.push(current.left);
        }
    }
}

2. 중간 순서 옮 겨 다 니 기

개념: 먼저 왼쪽 노드 를 옮 겨 다 니 고 뿌리 노드 를 옮 겨 다 니 며 마지막 으로 오른쪽 노드 를 옮 겨 다 닌 다.

왼쪽 나무 - > 뿌리 노드 - > 오른쪽 나무

순환 실현

/**
 *     ：left -> root -> right
 * @param root
 */
public void midTraversalRecursive(BinaryTree<Integer> root) {
    if (root == null) {
        return;
    }

    // left
    if (root.left != null) {
        midTraversalRecursive(root.left);
    }

    // root
    System.out.print(root.val + ",");

    // right
    if (root.right != null) {
        midTraversalRecursive(root.right);
    }
}

순환 실현

중간 순서 가: left - > root - > right 로 옮 겨 다 니 기 때문에 하위 트 리 의 root 가 스 택 에 중복 되 어 저장 할 수 있 습 니 다. right - > root - > left 의 순 서 는 root 가 처 리 했 는 지 기록 해 야 합 니 다. 처 리 했 으 면 두 번 째 스 택 에서 바로 스 택 을 나 가면 됩 니 다. 좌우 하위 트 리 를 처리 하지 않 아 도 됩 니 다. 순환 을 피 할 수 있 습 니 다.

public void midTraversal(BinaryTree<Integer> root) {
    Stack<BinaryTree<Integer>> stack = new Stack<>();
    //                
    Map<BinaryTree, Boolean> childIsInStack = new HashMap<>();

    if (root == null) {
        return;
    }

    if (root.left == null && root.right == null) {
        System.out.print(root.val);
        return;
    }

    // right
    if (root.right != null) {
        stack.push(root.right);
    }

    // root
    stack.push(root);

    // left
    if (root.left != null) {
        stack.push(root.left);
    }

    childIsInStack.put(root, true);

    while (!stack.isEmpty()) {
        //   
        BinaryTree<Integer> current = stack.pop();

        if (current.left == null && current.right == null) {
            System.out.print(current.val + ",");
        } else {
            //       current             ，        ，     
            if (childIsInStack.get(current) == null) {
                //      ，       ，      
                if (current.right != null) {
                    stack.push(current.right);
                }

                // root
                //    root    ，       ：right -> root -> left，  left   
                childIsInStack.put(current, true);
                stack.push(current);

                // left
                if (current.left != null) {
                    stack.push(current.left);
                }
            } else {
                System.out.print(current.val + ",");
            }
        }
    }
}

3. 후 순 옮 겨 다 니 기

개념: 먼저 왼쪽 노드 를 옮 겨 다 니 고 오른쪽 노드 를 옮 겨 다 니 며 마지막 으로 뿌리 노드 를 옮 겨 다 닌 다.

왼쪽 나무 - > 오른쪽 나무 - > 뿌리 노드

순환 실현

/**
 *     ：left -> right -> root
 * @param root
 */
public void postTraversalRecursive(BinaryTree<Integer> root) {
    if (root == null) {
        return;
    }

    // left
    if (root.left != null) {
        postTraversalRecursive(root.left);
    }

    // right
    if (root.right != null) {
        postTraversalRecursive(root.right);
    }

    // root
    System.out.print(root.val + ",");
}

순환 실현

사고방식 은 중간 순서 와 유사 하 다.

public void postTraversal(BinaryTree<Integer> root) {
    Stack<BinaryTree<Integer>> stack = new Stack<>();
    //                
    Map<BinaryTree, Boolean> childIsInStack = new HashMap<>();

    if (root == null) {
        return;
    }

    // root
    stack.push(root);

    // right
    if (root.right != null) {
        stack.push(root.right);
    }

    // left
    if (root.left != null) {
        stack.push(root.left);
    }

    childIsInStack.put(root, true);

    while (!stack.isEmpty()) {
        //   
        BinaryTree<Integer> current = stack.pop();

        //     
        if (current.left == null && current.right == null) {
            System.out.print(current.val + ",");
        } else {
            if (childIsInStack.get(current) == null) {
                // root      ，      ，    ：root -> right -> left
                //            root ，            
                stack.push(current);
                childIsInStack.put(current, true);

                //      ，       ，      ；        ，      
                if (current.right != null) {
                    stack.push(current.right);
                }

                if (current.left != null) {
                    stack.push(current.left);
                }
            } else {
                //          ，     
                System.out.print(current.val + ",");
            }
        }
    }
}

4. 차원 옮 겨 다 니 기

뿌리 노드 부터 한 층 한 층 왼쪽 에서 오른쪽으로 각 층 의 노드 를 옮 겨 다 닌 다.

/**
*       ，      O(N)
* @param root
*/
public void treeLevelTraversal(BinaryTree<Integer> root) {
   if (root == null) {
       return;
   }

   //   FIFO     
   ArrayDeque<BinaryTree<Integer>> queue = new ArrayDeque<BinaryTree<Integer>>();
   queue.offerLast(root);

   while (!queue.isEmpty()) {
       BinaryTree<Integer> ele = queue.pollFirst();
       System.out.print(ele.val + ",");

       if (ele.left != null) {
           queue.offerLast(ele.left);
       }

       if (ele.right != null) {
           queue.offerLast(ele.right);
       }
   }
}

이상 의 전체 테스트 소스 코드 는 개인 GitHub: Binary TreeTraversal. java

   public static void main(String[] args) {
    BinaryTree<Integer> root = TreeBuilder.buildCommonTree();

    BinaryTreeTraversal treeTraversal = new BinaryTreeTraversal();

    // 4,3,1,2,5,6,7
    System.out.println("pre: ");
    treeTraversal.preTraversalRecursive(root);
    System.out.println();
    treeTraversal.preTraversal(root);
    System.out.println();

    // 1,3,2,4,6,5,7
    System.out.println("mid: ");
    treeTraversal.midTraversalRecursive(root);
    System.out.println();
    treeTraversal.midTraversal(root);
    System.out.println();

    // 1,2,3,6,7,5,4
    System.out.println("post: ");
    treeTraversal.postTraversalRecursive(root);
    System.out.println();
    treeTraversal.postTraversal(root);
    System.out.println();

    // 4,3,5,1,2,6,7
    System.out.println("level: ");
    treeTraversal.treeLevelTraversal(root);
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[JAVA] 배열 회전 출력

요소 가 출력 을 시작 하 는 위치 에 주의 하 십시오. 모두 몇 라운드 의 수출 이 있 습 니까? n/2 + 1 매 라 운 드 는 상, 우, 하, 좌 로 나 뉜 다. 각 방향의 시작 위치 와 좌표 의 관 계 를 구...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

데이터 구조 - 트 리 (1): 트 리 의 디자인 취지 와 이 진 트 리 의 앞 순서, 중간 순서, 뒤 순서 옮 겨 다 니 기 (재 귀 와 순환 두 가지 버 전)

좋은 웹페이지 즐겨찾기