데이터 구조 기반 의 이 진 트 리 깊이 우선 옮 겨 다 니 기, 넓이 우선 옮 겨 다 니 기

1552 단어 데이터 구조
원본 링크:https://me.csdn.net/bjweimengshu
 
 
이 진 트 리 는 무엇 입 니까?
나무의 각 노드 에는 최대 두 개의 아이 노드 가 있다.
주의 하 세 요. 최대 2 개, 1 개 또는 0 개 일 수도 있 습 니 다.
  • 이 진 트 리 는 무엇 입 니까?

  • 모든 비 잎 노드 는 좌우 아이 가 존재 하고 모든 잎 노드 는 같은 등급 에 있다 (이곳 의 잎 노드 는 특정한 나무의 뿌리, 즉 이 나무의 마지막 층 이 되 지 않 았 다).
    이 진 트 리 의 모든 가지 가 가득 하 다.
  • 완전 이 진 트 리 는 무엇 입 니까?

  • 마지막 잎 사 귀 노드 앞 에 있 는 모든 노드 가 꽉 찼 다.
     
    나 무 는 비 선형 데이터 구조 로 이 진 트 리 는 링크 와 배열 로 표현 할 수 있다.
    체인 메모리 구조:
         각 노드 는 세 부분 을 포함한다.
  • 데 이 터 를 저장 하 는 data 변수;
  • 왼쪽 아이의 left 지침 을 가리킨다.
  • 오른쪽 아 이 를 가리 키 는 right 지침
  • 배열 저장 소:
            층계 순서에 따라 이 진 트 리 의 노드 를 배열 에 대응 하 는 위치 에 놓 아 라.한 노드 의 왼쪽 아이 나 오른쪽 아이 가 비어 있 으 면 배열 의 해당 위치 도 비어 있다.
           부모 노드 아래 표 시 를 parent 라 고 가정 하면 왼쪽 아이 아래 표 시 는 2 입 니 다.×parent + 1, 오른쪽 아이 아래 표 시 는 2 입 니 다.×parent+2
     Note: 희소 한 이 진 트 리 에 있어 서 배열 표현 법 을 사용 하 는 것 은 공간 을 낭비 하 는 것 입 니 다.
     
    이 진 트 리 의 일반적인 동작: 찾기, 상대 순서 유지
    이 진 트 리 찾기 (): 이 나무의 왼쪽 트 리 는 부모 노드 보다 작고 오른쪽 트 리 는 부모 노드 보다 크 며 이 진 트 리 의 질서 성 을 확보 합 니 다.
    이 진 트 리 자체 균형 방식: 붉 은 검 은 나무, AVL 나무, 나무 더미 등
     
    깊이 우선 순위:
    1. 앞 순 서 를 옮 겨 다 니 기: 출력 순 서 는 뿌리 노드, 왼쪽 트 리, 오른쪽 트 리 입 니 다.
    2. 중간 순서 옮 겨 다 니 기: 출력 순 서 는 왼쪽 하위 트 리, 뿌리 노드, 오른쪽 하위 트 리 입 니 다.
    3. 후 순 옮 겨 다 니 기: 출력 순 서 는 왼쪽 하위 트 리, 오른쪽 하위 트 리, 뿌리 노드
    /**
    *     
    *@param inputList     
    */
    public static TreeNode createBinaryTree(LinkedListinputList){
        TreeNode node=null;
        if(inputList==null || inputList.isEmpty()){
        
        }
    }

    좋은 웹페이지 즐겨찾기