트 리 데이터 구조 (기초 트 리) 의 특징 과 응용 장면

3937 단어 데이터 구조
나무.
특징.
  • 구조 직관
  • 한 그루 의 나무 가 특정한 성질 을 만족 시 키 면 모든 결점 이 만족 하도록 요구한다
  • 상시 형상
  • 일반 이 진 트 리
  • 밸 런 스 이 진 트 리
  • 완전 이 진 트 리
  • 이 진 트 리 검색
  • 사지 수
  • 다 진 트 리
  • 붉 은 검 은 나무, 밸 런 스 이 진 트 리 (의향 직위 사용 시 시험)
  • 조작 및 응용 장면 옮 겨 다 니 기
  • 앞 순 서 를 옮 겨 다 니 기 (뿌리 정도): 나무 에서 새 나 무 를 검색 하고 만 듭 니 다
  • 중간 순서 옮 겨 다 니 기 (왼쪽 오른쪽): 이 진 트 리 검색
  • 뒤의 순서 (왼쪽, 오른쪽): 특정한 노드 를 분석 할 때 왼쪽 나무 와 오른쪽 나무의 정 보 를 사용 해 야 한다. 즉, 정 보 를 검색 할 때 나무의 밑부분 부터 나 무 를 다 듬 을 때 잎 에서 뿌리 로 다 듬 는 것 과 같다
  • .
    예제
    힘 단추 230 사고: 앞에서 말 한 바 와 같이 중간 순서 로 이 진 트 리 를 옮 겨 다 니 면 결점 질서 있 는 서열 이라는 특성 을 얻 을 수 있 습 니 다. 먼저 중간 순서 로 이 진 트 리 를 옮 겨 다 니 고 해당 노드 의 값 을 찾 으 면 됩 니 다.
    class Solution {
    public:
        vector<int> inorder(TreeNode* root,vector<int>& vi){       
            if(root==NULL)
                return vi;
            inorder(root->left,vi);
            vi.push_back(root->val);
            inorder(root->right,vi);
            return vi;
        }
        int kthSmallest(TreeNode* root, int k) {
            vector<int>vi;
            inorder(root,vi);
            return vi[k-1];
        }
    };
    

    좋은 웹페이지 즐겨찾기