臺大 113 年資管所 資訊科技概論 參考答案

int BinarySearchTree::InsertNewEmployee(int newID, string newName, int newAge)
{
    TreeNode *newPtr = new TreeNode;      // 建立新節點
    newPtr->employeeID    = newID;
    newPtr->emplyeeName   = newName;
    newPtr->age           = newAge;
    newPtr->leftChildPtr  = NULL;
    newPtr->rightChildPtr = NULL;

    if (rootPtr == NULL) {                // 空樹，新節點成為 root
        rootPtr = newPtr;
        return 1;
    }

    TreeNode *cur = rootPtr, *parent = NULL;
    while (cur != NULL) {                 // 找插入位置，同時記住父節點
        parent = cur;
        if (newID < cur->employeeID)
            cur = cur->leftChildPtr;
        else if (newID > cur->employeeID)
            cur = cur->rightChildPtr;
        else {                            // ID 重複，插入失敗
            delete newPtr;
            return 0;
        }
    }

    if (newID < parent->employeeID)       // 掛到父節點正確的一側
        parent->leftChildPtr = newPtr;
    else
        parent->rightChildPtr = newPtr;
    return 1;
}

void BinarySearchTree::ListAllEmployee()
{
    inorder(rootPtr);                 // 從樹根開始中序走訪
}

void BinarySearchTree::inorder(TreeNode *treePtr)
{
    if (treePtr == NULL) return;      // 遞迴終止條件
    inorder(treePtr->leftChildPtr);   // 左
    cout << treePtr->employeeID  << " "
         << treePtr->emplyeeName << " "
         << treePtr->age << endl;     // 根：印出 (ID, name, age)
    inorder(treePtr->rightChildPtr);  // 右
}