완전 이 진 트 리 체인 비 재 귀적 삽입 트 리

최근 에 비 귀속 체인 식 완전 이 진 트 리 를 사용 해 야 하 는 상황 을 만 났 다.그림 의 한 노드 는 이러한 이 진 트 리 로 여러 개의 똑 같은 특징 을 가 진 노드 를 저장 합 니 다.인터넷 에서 대충 찾 아 봤 는데 못 봤 어 요. 여기 서 먼저 백업 해 주세요.방법 은 나무의 구조 체 에 마지막 노드 를 가리 키 는 지침 과 삽입 할 위 치 를 가리 키 는 아버지의 지침 을 저장 하 는 것 이다.점 의 구조 체 에는 트 리 의 같은 층 을 가리 키 는 다음 노드 (또는 다음 줄 의 첫 번 째 노드) 가 저장 되 어 있다.

struct Node{
    Node*left, *right;
    Node*neigh;
    int data;
    Node(){ left = right = neigh = NULL;  }
};
Node*par[N];
struct Tree{
    int size;
    Node*root;
    Node*lastRt;  //              
    Node*lastLeaf;  //           
    Tree(){ root = NULL; lastRt = lastLeaf = NULL; size = 0; }
    ~Tree(){
        queueq;
        q.push(root);
        while (!q.empty()){
            Node*rt = q.front(); q.pop();
            if (rt == NULL)return;
            q.push(rt->left);
            q.push(rt->right);
            delete rt;
        }
    }
    void insert(int x){
        par[x] = root;
        if (root == NULL){
            root = new Node;
            root->data = x;
            lastRt = root;
            lastRt->neigh = NULL;
            lastLeaf = root;
            size++;
            return;
        }
        if (lastRt->left == NULL){
            lastRt->left = new Node;
            lastRt->left->data = x;
            lastLeaf->neigh = lastRt->left;
            lastLeaf = lastLeaf->neigh;
            size++;
        }
        else if (lastRt->right == NULL){
            lastRt->right = new Node;
            lastRt->right->data = x;
            lastLeaf->neigh = lastRt->right;
            lastLeaf = lastLeaf->neigh;
            size++;
        }
        else{
            lastRt = lastRt->neigh;
            insert(x);
        }
    }
    void show(){
        queueq;
        q.push(root);
        while (!q.empty()){
            Node*t = q.front(); q.pop();
            if (t == NULL)return;
            cout << t->data << " ";
            q.push(t->left);
            q.push(t->right);
        }
    }
    void preshow(Node*rt){
        if (rt == NULL)return;
        cout << rt->data << " ";
        preshow(rt->left);
        preshow(rt->right);
    }
};