王道書 P175 T6

/**
 * 用二叉樹鍊式存儲實作 王道P175 T6
 *
 * ①算法思想
 * 首先要把value的值轉換成一個一個節點，并用CSTree類型的指針數組把每個結點的位址存儲一下；
 * 然後開始建立孩子--兄弟連結清單。
 * 關于孩子兄弟連結清單的建立：
 * 想象在一棵樹中，根節點有三個孩子，第一個孩子還有一個孩子，層次序列為：1、2 3 4、 5
 * int 一個 k，k代表的是每一層最後一個節點在pointer數組中的下标，剛開始 k 為 0。
 * 再int一個 d，d 是從degree數組中取出的對應節點的度，
 * 可知根節點的度為d，是以剛開始 d 為 3，k為 0。
 * 2是1的第一個孩子，我們要讓 1 的firstChild指向2，然後 3 4 連接配接在 2 的後面，
 * 也就是拿到一個節點，先看一下這個節點的度，然後讓這個節點的firstChild = pointer[++k]。
 * 然後在執行 3 4 連接配接在 2 的後面這個過程中，一直++k，這樣 2 3 4 連完了之後k就是 3 了，
 * 下面就要檢視 2 的度了，再次執行 2 的firstChild = pointer[++k]......
 *
 * ②算法設計
 */


#include <stdio.h>
#include <iostream>
#define MaxSize 100

typedef struct CSTreeNode{
    int data;
    struct CSTreeNode *firstChild,*nextSibling;
}CSTreeNode,*CSTree;



//P175 T6
CSTree CreatCSTree(int value[],int degree[],int n){//value存的是節點的值，degree存的是節點的度，n告訴我有多少個節點
    //把value數組裡的值都轉換為節點
    //首先要開一個用來儲存節點指針的數組
//    CSTree *pointer = (CSTree*)malloc(sizeof(CSTree)*n);//申請n個CSTree指針大小的空間，
//    //這些空間裡存放的是指針，也就是一個一個節點的位址，pointer指向了這個數組空間的首位址。
//    CSTree T = (CSTree)malloc(sizeof(CSTreeNode));
//    pointer[0] = T;//把根節點的位址放如指針數組
      CSTree pointer[n];
      //下面把每一個value都轉化成節點
      for (int i = 0; i < n; ++i) {
        CSTree Node = (CSTreeNode*)malloc(sizeof(CSTreeNode));
        Node -> data = value[i];
        Node -> firstChild = Node -> nextSibling = NULL;
        pointer[i] = Node;
      }
      //建立孩子-兄弟連結清單
      int d,k = 0;
      for (int i = 0; i < n; ++i) {
        d = degree[i];
        if(d != 0){
            pointer[i] -> firstChild = pointer[++k];//從pointer數組裡面取節點的位址,把根節點和他的第一個孩子連起來
            for(int j = 2; j <= d; j++){//把第一個孩子和他的兄弟們連起來
                pointer[k] -> nextSibling = pointer[++k];
            }
        }
    }
      return pointer[0];//連接配接完成後傳回根節點的指針
}