Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
2.1 kB
16
Indexable
Never
#include <iostream>
using namespace std;

class Node {
public:

	int data;
	Node * left;
	Node * right;
	
	Node(int d){
		data = d;
		left = NULL;
		right = NULL;
	}
	
};

Node * insert(Node * root, int d){
	
	if(root == NULL){
		return new Node(d);
	}
	
	// data is less than root's data
	if(d <= root->data){
		root->left = insert(root->left, d);
	} else {
		// data is greater than root's data
		root->right = insert(root->right, d);
	}
	
	return root;
	
}


bool search(Node * root, int d){
	
	if(root== NULL) return false;
	
	if(root->data == d) return true
	else if (root->data < d) return search(root->right, d);
	else return search(root->left, d);
	
}

Node * deleteANode(Node * root, int data){
	if(root==NULL) return NULL;
	
	if(root->data > data){
		root->left = deleteANode(root->left, data);
		return root;
	} else if(root->data < data){
		root->right = deleteANode(root->right, data);
		return root;
	} else {
		// root->data == data = This node you want to delete
		// 1. If this current node is a leaf node
		if(root->left == NULL && root->right == NULL){
			
			// 1. delete the actual node from the heap
			delete root;
			
			// 2. Break the link
			return NULL;
		}
		
		// 2. If the current node has only one child
		if(root->left != NULL && root->right == NULL){
			Node * temp = root->left;
			delete root;
			return temp;
		}
		if(root->right != NULL && root->left == NULL){
			Node * temp = root->right;
			delete root;
			return temp;
		}
		
		// 3. If the current node has 2 child
		if(root->left != NULL && root->right != NULL){
			
			Node * replaceNode = root->right;
			// find the inorder successor from the right subtree
			while(replaceNode->left != NULL){
				replaceNode = replaceNode->left;
			}
			root->data = replaceNode->data;
			root->right = deleteANode(root->right, replaceNode->data);
			
			return root;
			
			
			
			
			
			
		}
		
		
		
		
		
	}
	
	
}

Node * build(){
	int d;
	cin >> d;
	
	Node * root = NULL;
	while(d != -1){
		root = insert(root, d); /// 
		cin >> d;
	}
	
	return root;
}


int main() {
	// your code goes here
	
	Node * root = build();
	
	cout << "hello" << endl;
	return 0;
}