[リソース構造]ツリー


木。

  • ノードからなる資料構造.
  • 配列やリストなどの線形データ構造では表現できない問題を解決するために使用されます.
  • 階層問題(階層問題)、循環依存性問題(循環依存性)など.
  • 階層図の例


  • 以下の階層は、通常のベクトル、配列として表すことはできません.
  • 位に示すように、CEOや副社長などがデータを格納する部分をノードと呼び、ノードとノードを接続する線をEdgeと呼ぶ.
  • 階層図は非循環図であり、方向性のある図である.
  • ツリー実装

    #include <iostream>
    #include <queue>
    using namespace std;
    
    // 직책과 바로 밑의 부하직원을 나타내는 node 
    struct node 
    {
        string position;
        node* first;
        node* second;
    };
    
    struct org_tree 
    {
        // tree에 기반이 되는 root를 생성.
        node* root;
    
        // root노드를 설정하는 함수.
        static org_tree create_org_structure(const string& pos) 
        {
            org_tree tree;
            tree.root = new node {pos, NULL, NULL};
            return tree;
        }
    
        // node가 있는지 없는지 확인하는 함수.
        static node* find(node* root, const string& value) 
        {
            // root가 없을 경우 NULL을 리턴.
            if (root == NULL) 
                return NULL;
            // root의 position 값이 찾는 값과 같을경우 root를 리턴.
            if (root->position == value)
                return root;
    
            // 찾는 값이 root가 아닐 경우 재귀를 통해 first node를 탐색.
            auto firstFound = find(root->first, value);
    
            if(firstFound != NULL)
                return firstFound;
    
            // 찾는 값이 firstFound가 아닐 경우 재귀를 통해 second node를 탐색.
            return find(root->second, value);
        }
    
        // 트리에 간선 추가
        bool addSubordinate(const string& manager, const string subordinate) 
        {
            auto managerNode = find(root, manager);
    
            // managerNode를 못 찾을 경우 추가 X.
            if(!managerNode)
            {
                cout << manager << "을 찾을 수 없습니다." << endl;
                return false;
            }
    
            // managerNode에 first, second값이 있다면 추가 X.
            if(managerNode->first && managerNode->second)
            {
                cout << manager << " 아래에 " << subordinate << "을 추가할 수 없습니다." << endl;
                return false;
            }
    
            // 비어있는 node에 삽입.
            if(!managerNode->first) 
                managerNode->first = new node {subordinate, NULL, NULL};
            else 
                managerNode->second = new node {subordinate, NULL, NULL};
    
            cout << manager << " 아래에 " << subordinate << "을 추가했습니다." << endl;
    
            return true;
        }
    };
    
    int main()
    {
        auto tree = org_tree::create_org_structure("CEO");
    
        tree.addSubordinate("CEO", "부사장");
        tree.addSubordinate("부사장", "IT부장");
        tree.addSubordinate("부사장", "마케팅부장");
        tree.addSubordinate("IT부장", "보안팀장");
        tree.addSubordinate("IT부장", "웹개발팀장");
        tree.addSubordinate("마케팅부장", "물류팀장");
        tree.addSubordinate("마케팅부장", "홍보팀장");
        tree.addSubordinate("부사장", "재무부장");
    }

    結果値