Why Cannot Find deepest node in Binary search tree 28,22,23,19,21,125 ?


  • -1
    A

    #ifndef BT_type
    #define BT_type

    #include "BTNode.h"
    #include "Queue.h"
    #include <fstream>

    using namespace std;

    template <class T>
    class BST {
    private:
    int count;
    BTNode<T> *root;

    	// print operation for BST (same as BT)					
    	void preOrderPrint2(BTNode<T> *);	// recursive function for preOrderPrint()
    	void inOrderPrint2(BTNode<T> *);	// recursive function for inOrderPrint()
    	void postOrderPrint2(BTNode<T> *);	// recursive function for postOrderPrint()
    
    	// sample operation (extra functions) - same as BT
    	void countNode2(BTNode<T> *, int &);		// recursive function for countNode()
    	bool fGS2(T, BTNode<T> *);					// recursive function for findGrandsons(): to find the grandfather
    	void fGS3(BTNode<T> *, int);				// recursive function for findGrandsons(): to find the grandsons after the grandfather has been found
    	
    	// basic functions for BST
    	void insert2(BTNode<T> *, BTNode<T> *);		// recursive function for insert() of BST
    	void case3(BTNode<T> *);					// recursive function for remove()
    	void case2(BTNode<T> *, BTNode<T> *);		// recursive function for remove()
    	bool remove2(BTNode<T> *, BTNode<T> *, T);	// recursive function for remove()
    	//void BST<T>::deepestNodes2(BTNode<T> *, T & );
    
        
    
    
    public:
    	// basic functions for BST
    	BST();
    	bool empty();
    	int size();
    	bool insert (T);		// insert an item into a BST
    	bool remove(T);			// remove an item from a BST
    //	struct Node *left, *right;
    	
    	// print operation for BST (same as BT)
    	void preOrderPrint();			// print BST node in pre-order manner
    	void inOrderPrint();			// print BST node in in-order manner
    	void postOrderPrint();			// print BST node in post-order manner
    	void topDownLevelTraversal();	// print BST level-by-level
    
    	// sample operation (extra functions) - same as BT
    	int countNode();		// count number of tree nodes
    	bool findGrandsons(T);	// find the grandsons of an input father item
    
        //other useful functions for BST
    	bool display(int, int);
    	bool search(int, T &);
    	bool deepestNode();
    	bool printSubtree(T);
    	bool clear();
    

    };

    template <class T>
    bool BST<T>::clear()
    {

    }

    template <class T>
    bool BST<T>::printSubtree(T item)
    {

    }

    //====================The function is here, it is any problem why cannot print out deepest node from tree========================/////
    template <class T>
    bool BST<T>::deepestNode()
    {
    BTNode<T> *cur;

    if (empty()) return false;
    
    if(countNode()==NULL)
    cout << cur->item << ' '; 
    

    }

    template <class T>
    BST<T>::BST() {
    root = NULL;
    count = 0;
    }

    template <class T>
    bool BST<T>::empty() {
    if (count==0) return true;
    return false;
    }

    template <class T>
    int BST<T>::size() {
    return count;
    }

    template <class T>
    int BST<T>::countNode() {
    int counter=0;
    if (root==NULL) return 0;
    countNode2(root, counter);
    return counter;
    }

    template <class T>
    void BST<T>::countNode2(BTNode<T> *cur, int &count) {
    if (cur == NULL) return;
    countNode2(cur->left, count);
    countNode2(cur->right, count);
    count++;
    }

    template <class T>
    bool BST<T>::findGrandsons(T grandFather) {
    if (root==NULL) return false;
    return (fGS2(grandFather, root));
    }

    template <class T>
    bool BST<T>::fGS2(T grandFather, BTNode<T> *cur) {
    if (cur == NULL) return false;
    if (cur->item == grandFather) {
    cout << endl << "Grandfather " << cur->item << " has grandsons" << endl;
    fGS3(cur, 0); // do another TT to find grandsons
    return true;
    }
    if (fGS2(grandFather, cur->left)) return true;
    return fGS2(grandFather, cur->right);
    }

    template <class T>
    void BST<T>::fGS3(BTNode<T> *cur, int level) {
    if (cur == NULL) return;
    if (level==2) {
    cout << '\t' << cur->item;
    return; // No need to search downward
    }
    fGS3(cur->left, level+1);
    fGS3(cur->right, level+1);
    }

    template <class T>
    void BST<T>::topDownLevelTraversal() {
    BTNode<T> *cur;
    Queue<BTNode<T> *> q;

    if (empty()) return; 	// special case
    q.enqueue(root);	// Step 1: enqueue the first node
    while (!q.empty()) { 	// Step 2: do 2 operations inside
    	q.dequeue(cur);
    	if (cur != NULL) {
    		cout << cur->item << ' ';
    		if (cur->left != NULL) q.enqueue(cur->left);
    		if (cur->right != NULL) q.enqueue(cur->right);
    	}
    }
    

    }

    template <class T>
    void BST<T>::insert2(BTNode<T> *cur, BTNode<T> *newNode) {
    if (cur->item > newNode->item) {
    if (cur->left == NULL)
    cur->left = newNode;
    else
    insert2(cur->left, newNode);
    }
    else {
    if (cur->right == NULL)
    cur->right = newNode;
    else
    insert2(cur->right, newNode);
    }
    }

    //insert for BST
    template <class T>
    bool BST<T>::insert(T newItem) {
    BTNode<T> *cur = new BTNode<T>(newItem);
    if (!cur) return false; // special case 1
    if (root==NULL) {
    root = cur;
    count++;
    return true; // special case 2
    }
    insert2(root, cur); // normal
    count++;
    return true;
    }

    template <class T>
    void BST<T>::case3(BTNode<T> *cur) {
    BTNode<T> *is, *isFather;

    // get the IS and IS_parent of current node
    is = isFather = cur->right;				
    while (is->left!=NULL) {				
    	isFather = is;
    	is = is->left;
    }
    
    // copy IS node into current node
    cur->item = is->item;
    
    // Point IS_Father (grandfather) to IS_Child (grandson)
    if (is==isFather) 
    	cur->right = is->right;		// case 1: There is no IS_Father    
    else 
    	isFather->left = is->right;	// case 2: There is IS_Father
    
    // remove IS Node
    free(is);								
    

    }

    template <class T>
    void BST<T>::case2(BTNode<T> *pre, BTNode<T> *cur) {

    // special case: delete root node
    if (pre==cur) {	
    	if (cur->left!=NULL)	// has left son?
    		root = cur->left; 
    	else 
    		root = cur->right;
    
    	free(cur);
    	return;
    }
    
    if (pre->right==cur) {		// father is right son of grandfather? 
    	if (cur->left==NULL)			// father has no left son?
    		pre->right = cur->right;			// connect gfather/gson
    	else 
    		pre->right = cur->left;
    }
    else {						// father is left son of grandfather?
    	if (cur->left==NULL)			// father has no left son? 
    		pre->left = cur->right;				// connect gfather/gson
    	else 
    		pre->left = cur->left;
    }
    
    free(cur);					// remove item
    

    }

    template <class T>
    bool BST<T>::remove2(BTNode<T> *pre, BTNode<T> *cur, T item) {

    // Turn back when the search reaches the end of an external path
    if (cur == NULL) return false;
    
    // normal case: manage to find the item to be removed
    if (cur->item == item) {
    	if (cur->left == NULL || cur->right == NULL) 
    		case2 (pre, cur);	// case 2 and case 1: cur has less than 2 sons
    	else 
    		case3 (cur);		// case 3, cur has 2 sons
    	count--;				// update the counter
    	return true;
    }
    
    // Current node does NOT store the current item -> ask left sub-tree to check
    if (cur->item > item)
    	return remove2(cur, cur->left, item);
    
    // Item is not in the left subtree, try the right sub-tree instead
    return remove2(cur, cur->right, item);
    

    }

    template <class T>
    bool BST<T>::remove(T item) {
    if (root == NULL) return false; // special case 1: tree is empty
    return remove2(root, root, item); // normal case
    }

    #endif


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.