本文介绍了无法在二进制搜索树28,22,23,19,21,125中找到最深的节点的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
#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();
};
//==================Function Are Here=========================//
template <class T>
bool BST<T>::deepestNode()
{
BTNode<T> *cur;
if (empty()) return false;
if(countNode()==NULL)
cout << cur->item << ' ';
}
template <class T>
bool BST<T>::search(int target, T &item)
{
}
template <class T>
bool BST<T>::display(int order, int source)
{
}
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>
void BST<T>::preOrderPrint() {
if (root == NULL)
{
return;// handle special case
}
else preOrderPrint2(root);// do normal process
cout << endl;
}
template <class T>
void BST<T>::preOrderPrint2(BTNode<T> *cur) {
if (cur == NULL) return;
cout << cur->item << ' ';
preOrderPrint2(cur->left);
preOrderPrint2(cur->right);
}
template <class T>
void BST<T>::inOrderPrint() {
if (root == NULL) return;// handle special case
else inOrderPrint2(root);// do normal process
cout << endl;
}
template <class T>
void BST<T>::inOrderPrint2(BTNode<T> *cur) {
if (cur == NULL) return;
inOrderPrint2(cur->left);
cout << cur->item << ' ';
inOrderPrint2(cur->right);
}
template <class T>
void BST<T>::postOrderPrint() {
if (root == NULL) return;// handle special case
else postOrderPrint2(root);// do normal process
cout << endl;
}
template <class T>
void BST<T>::postOrderPrint2(BTNode<T> *cur) {
if (cur == NULL) return;
postOrderPrint2(cur->left);
postOrderPrint2(cur->right);
cout << cur->item << ' ';
}
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推荐答案
这篇关于无法在二进制搜索树28,22,23,19,21,125中找到最深的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！