1
我正在創建一個二叉搜索樹，它需要能夠刪除節點，並在節點被正確刪除時返回true;如果該值不存在，則返回false那個樹。我這樣做是因爲我需要刪除多個數字，並且我想創建一個while循環來刪除它的所有內容，而這是真的。例如，一棵樹有以下整數：{79,83,147,71,95,49,15,191}。另一棵樹有以下整數{26,79,144,88,147,200,90}。我的任務是找到樹1中樹2中的任何元素，並從樹1中刪除它們（在這種情況下，爲79和147）。我想創建一個循環遍歷樹2中的所有數字，然後從樹中搜索並刪除它。以下是我迄今爲止的刪除節點功能（假設樹已經建成並填寫）：從我的二叉搜索樹中刪除節點時遇到困難
Node.h：
template<class ItemType>
class Node {
public:
ItemType data;
Node * left;
Node * right;
//Constructors/Destructors
Node();
Node (ItemType inData);
~Node();
};
//--------------------------------------------------------------//
//-- Constructor/Destructor --//
//--------------------------------------------------------------//
/** Standard Constructor */
template<class ItemType>
Node<ItemType>::Node() {
left = right = NULL;
}
/** Overload Constructor */
template<class ItemType>
Node<ItemType>::Node (ItemType inData) {
data = inData;
left = right = NULL;
}
/** Standard Destructor */
template<class ItemType>
Node<ItemType>::~Node() {
right = left = NULL;
}
從Source.cpp：
Tree2.postorder_print();
int ridOf = 79;
if (Tree2.remove (ridOf)) {
Tree2.postorder_print();
cout << endl << "Number of Nodes: " << Tree2.get_num_of_nodes() << endl;
cout << "Height: " << Tree2.get_tree_height() << endl << endl;
}
從Tree.h：
template<class ItemType>
void BTree<ItemType>::postorder_print_helper (Node<ItemType> * inRoot, int & count) {
if (inRoot != NULL) {
postorder_print_helper (inRoot->left, count);
postorder_print_helper (inRoot->right, count);
count++;
std::cout << setw (4) << inRoot->data << " ";
if (count % 5 == 0) { std::cout << endl; }
}
} // end of void BTree<ItemType>::postorder_print_helper (Node<ItemType> * inRoot)
template<class ItemType>
void BTree<ItemType>::postorder_print_helper (Node<ItemType> * inRoot, int & count) {
if (inRoot != NULL) {
postorder_print_helper (inRoot->left, count);
postorder_print_helper (inRoot->right, count);
count++;
std::cout << setw (4) << inRoot->data << " ";
if (count % 5 == 0) { std::cout << endl; }
}
} // end of void BTree<ItemType>::postorder_print_helper (Node<ItemType> * inRoot)
template<class ItemType>
bool BTree<ItemType>::remove_helper (Node<ItemType> * inRoot, ItemType toRemove) {
//if this is the node with the data
if (inRoot->data == toRemove) {
//Create Null Node that points to NUll
Node<ItemType> * nullNode = new Node <ItemType> ;
//if inRoot has No Children
if (inRoot->left == NULL && inRoot->right == NULL) {
inRoot = nullNode;
return true;
}
//if inRoot has 2 Children
else if (inRoot->left != NULL && inRoot->right != NULL) {
Node<ItemType> * temp = new Node <ItemType>;
temp = return_max_value (inRoot->left);
Node<ItemType> * tempRight = new Node <ItemType>;
tempRight = inRoot->right;
Node<ItemType> * tempLeft = new Node <ItemType>;
tempLeft = inRoot->left;
inRoot = nullNode;
inRoot = temp;
temp->left = tempLeft;
temp->right = tempRight;
return true;
}
//if inRoot has 1 child
else {
//if inRoot has left child
if (inRoot->right == NULL) {
Node<ItemType> * temp = new Node <ItemType>;
temp = inRoot->left;
inRoot = nullNode;
inRoot = temp;
return true;
}
//if inRoot has right child
else {
Node<ItemType> * temp = new Node <ItemType>;
temp = inRoot->right;
inRoot = nullNode;
inRoot = temp;
return true;
}
}
}
//If not the node with the data See if toRemove is less than inRoot and perform recursive action
else if (toRemove < inRoot->data) {
remove_helper (inRoot->left, toRemove);
} //end if (toRemove < inRoot->data)
//See if toRemove is greater than inRoot and perform recursive action
else if (toRemove > inRoot->data) {
remove_helper (inRoot->right, toRemove);
}// end of else
//return false if data cannot be found
else return false;
}
我的一些結果是不同的，都是錯誤的。其中一個結果就是無限循環不斷打印樹。另一個結果是它會執行刪除操作並顯示成功，但如果您查看兩個打印輸出，它們是相同的，並且該節點不會被刪除（如果返回false，則不應再將其打印出來，但它會這樣做）。然後在第二個print_preorder期間發生第三個結果。它會中斷並停止在一個空節點上，但左側和右側的數據都會顯示「無法讀取內存」。我做錯了什麼？我無法弄清楚。我試圖刪除一個節點之前，我所有的其他樹功能（包括前序打印）。
只是澄清一點，我有我的remove_helper函數的問題。所以我可以移動到從Tree1中刪除Tree2中存在的節點。
剛剛爲結果構建一棵新樹如何？它看起來像集合差異。 –
我不確定你的意思。我的實際代碼有用獨特的隨機數創建的樹。 – kingcobra1986
我的意思是代替修改一棵樹，如果這是困難的地方，只需要在結果中創建一個新的樹。 –