Edit History

@madpugger what version of Prestashop are you using? 

I'm not sure I understand the "broken tree" part. If the actual category tree structure is corrupt, then you would need to force it to recalculate. This can be done via code, or more simply - just add a random category from the back office. That will force it to recalculate the tree as a side-effect and you can then delete this extra new category once it's done.

If you mean "broken" as in products in the wrong categories.... It does appear that you *can't* remove categories during a subsequent product import to update. During the import it appears to only add new categories for existing products (in controllers/admin/AdminImportController.php):
 

if (isset($product->id) && $product->id && Product::existsInDatabase((int) $product->id, 'product')) {
  $product->loadStockData();
  $category_data = Product::getProductCategories((int) $product->id);

  if (is_array($category_data)) {
    foreach ($category_data as $tmp) {
      if (!$product->category || is_array($product->category)) {
        $product->category[] = $tmp;
      }
    }
  }
}

The above code takes the existing categories and appends them to the categories you have in your import file (for existing products). Later it removes any duplicates. Ideally there should be a switch in there to specify whether you want to keep the existing categories or not. It would be worth logging it as a "feature request" (Prestashop github issues click "New Issue" and mark it as a feature request).

I *think* that if you were to simply edit the line:
 

$category_data = Product::getProductCategories((int) $product->id);

To:

$category_data = []; // Product::getProductCategories((int) $product->id);

Then you would only set the imported categories for the product. This has the side-effect of removing any categories not specified in the import.

Importing categories themselves is fraught. It *should* work but with some caveats.

I don't use the default CSV importer but when I look at the example import file for categories (in the docs folder) you can indeed specify the parent category in the category import. Looking at the code (I'm looking at 8.2.0 right now, although I don't imagine it has changed much if at all since 1.6) you can specify either a name or an ID for the parent category.

From the docs folder:
 

Category ID;Active (0/1);Name *;Parent category;Root category (0/1);Description;Meta title;Meta description;URL rewritten;Image URL

If you use a name for the parent category, then it will pick up the first category of that name that it finds as it's using Category::searchByName(). The parent category, if specified by name needs to pre-exist AND be unique for this to work.

If the parent category is specified by an id, then everything should be fine as it subsequently finds the subcategory id using the function Category::searchByNameAndParentCategoryId()

The upshot is that you should probably always use an absolute category id for the parent field, so make sure that you import the parent categories first. Best practice would be to import categories by level (i.e. first import parent categories, then separately import subcategories once you know the parent ids etc.). Since you have a category structure that you want now, then this is probably all moot for you, but maybe not for others starting their "import journey"

EDIT: Note that I don't recommend  modifying core files as suggested above. Doing it temporarily to sort out a problem is slightly different though and you can revert the change once the issue is fixed and then hopefully it gets fixed via a feature request. If I can find the time I might consider submitting a pull request with the necessary changes required to make the above happen, but there's no guarantee that the request will be accepted or which version it could be applied to, hence the question at the top of my response.....