0

我在托管 C++ 中为学校创建了一个小型 BST 项目。工作得很好，但现在我试图弄清楚如何使用泛型做同样的项目（第一个项目使用 int）。对于我的生活，我看不到我从根本上搞砸了什么。希望有方向。

通用节点类.h：

/*
GenericNodeClass.h.  Created by Ed Thompson for IS375, C++ Intermediate, City University
of Seattle.

GenericNodeClass.h provides for members for creation of a generic binary tree

*/

#pragma once

#include "stdafx.h"
#include <iostream>
#include <deque>
#include <climits>

using namespace std;
using namespace System;
using namespace System::Collections;
using namespace System::Collections::Generic;

generic <typename T> where T : IComparable<T>, IEquatable<T>
ref class Node
{
public:
T data;
T parent;
Node<T> ^ left;
Node<T> ^ right;

// Constructor that takes one parameter:
// a T, representing the value of a new node
Node(T n) 
{
    data = n;
}
};

BinarySearchTreeClass.h

#include "stdafx.h"
#include <iostream>
#include <deque>
#include <climits>
#include "GenericNodeClass.h"

using namespace std;
using namespace System;
using namespace System::Collections;
using namespace System::Collections::Generic;

generic <typename T> where T : IComparable<T> , IEquatable<T>
ref class BinarySearchTreeClass

{
public:

Node<T>^ rootNode;
T _p;

// constructors
// default
BinarySearchTreeClass(){}

BinarySearchTreeClass(T t)
{
    // create a new Node in the Binary Search Tree 
    rootNode = gcnew Node<T> (t);
}

// method to return a node if it exists in the tree
// takes two parameters:  an instance of the Node class, and a
// value representing the value of the node to be looked up 
Node<T> ^ lookUp(Node<T> ^node, T key)
{
    if(node == nullptr)
        return node;
    if(node->data == key) 
        return node;
    else
    {
        if (node->data->CompareTo(key) < 0)
            return lookUp(node->right, key);
        else
            return lookUp(node->left, key);
    }
}

// method to create new node.  Method takes two parameters:
// a parameter of the value for the node data, and a value
// for the node's parent.
Node<T> ^newNode(T key, T parent)
    {
        Node<T> ^node = gcnew Node<T>(key);
        node->data = key;
        node->left = nullptr;
        node->right = nullptr;
        node->parent = parent;

        return node;
    }

// insertNode method inserts a new node into an existing 
// Binary Search Tree.  This method takes two parameters:
// an instance of Node<T> (node), and a value of T, 
// representing the value of the node being inserted
Node<T> ^insertNode(Node<T> ^node, T input)
{
    Node<T> ^returnNode;

    if (node != nullptr)
        _p = node->data;

    // if the node is non-existant, create a new node
    // with the value of the parameter 'input' and the 
    // value of the new node's parent (_p).
    if (node == nullptr)
    {
        // pass class variable _p to set value
        // of the new node's parent value.
        returnNode = newNode(input, _p);
        return returnNode;
    }

    // if the input parameter value is less than 
    // or equal to the node value, insert node using 
    // the left hand node leaf of the current node 
    // as starting point
    if (input->CompareTo(node->data) < 0)
    {
        // set variable p to value of node->data value (this
        // will be the parent of the new node)
        _p = node->data;
        node->left = insertNode(node->left, input);
    }

    // if the input parameter value is greater than 
    // the node value, insert node using the right hand
    // node leaf of the current node as starting point
    else
    {
        _p = node->data;
        node->right = insertNode(node->right, input);
    }
    return node;
}

// method to find the left most node in a Binary Search Tree
// takes an instance of Node<T> as parameter
Node<T> ^leftMost(Node<T> ^node)
{
    if (node == nullptr)
        return nullptr;
    while (node->left != nullptr)
        node = leftMost(node->left);
    return node;
}

// method of return the right most node in a Binary Search Tree
// takes an instance of Node<T> as parameter
Node<T> ^rightMost(Node<T> ^node)
{
    if (node == nullptr)
        return nullptr;
    while (node->right != nullptr)
        node = rightMost(node->right);
    return node;
}

// method to return the size of a Binary Tree
// takes an instance of Node<T> as parameter
int treeSize(Node<T> ^node)
{
    if(node == nullptr || node->left == nullptr && node->right == nullptr)
        return 0;

    else
        return treeSize(node->left) + 1 + treeSize(node->right);
}

// method that prints to console the value of each node from lowest to highest
// takes an instance of Node<T> as parameter
void printTreeInOrder(Node<T> ^node)
{
    if (node != nullptr)
    {
        printTreeInOrder(node->left);
        Console::WriteLine(node->data);
        printTreeInOrder(node->right);
    }
}

// method that prints to console a graphic representation of a binary tree
// takes an instance of Node<T> as parameter
void printGraphicRepresentation(Node<T> ^node)
{
    // the width of the tree is the max height /2 (?)
    // need to know how wide the tree is
    // At treeWidth / 2, print node 
    // on new line, at nodePosition - 1, if node has a left, print a "/"
    // on same line, at nodePosition + 1, if node has a right, print a "\"
}

// method that prints to console all members of a given node
// takes an instance of Node<T> as parameter
void printNodeMembers(Node<T> ^node)
{
    Console::WriteLine("Members of Node " + node->data + " include: ");
    if (node->parent != nullptr)
        Console::WriteLine("Parent: " + node->parent);
    else
        Console::WriteLine("This node has no parent.");
    if (node->left != nullptr)
        Console::WriteLine("Left-member: " + node->left->data);
    else
        Console::WriteLine("This node has no left-member.");
    if (node->right != nullptr)
     Console::WriteLine("Right-Member: " + node->right->data);
    else
        Console::WriteLine("This node has no right-member.");

}
};

测试类.cpp

#include "stdafx.h"
#include "GenericNodeClass.h"
#include "BinarySearchTreeClass.h"
#include <iostream>

using namespace std;
using namespace System;
using namespace System::IO;
using namespace System::Collections::Generic;

int main ()
{
BinarySearchTreeClass<int>^ BTree = gcnew BinarySearchTreeClass<int>();

// instantiate new Node instance with starter value
Node<int> ^rootNode = gcnew Node<int>(5);

// insert additional nodes
BTree->insertNode(rootNode, 3); 
BTree->insertNode(rootNode, 7);
BTree->insertNode(rootNode, 4);
BTree->insertNode(rootNode, 6);
BTree->insertNode(rootNode, 2);
BTree->insertNode(rootNode, 9);
BTree->insertNode(rootNode, 1);
BTree->insertNode(rootNode, 8);
BTree->insertNode(rootNode, 0);
BTree->insertNode(rootNode, 10);
BTree->insertNode(rootNode, 12);
BTree->insertNode(rootNode, 11);
Console::WriteLine("The value of the left-most node in this tree is: " + BTree->leftMost(rootNode)->data); 
Console::WriteLine("The value of the right-most node in this tree is: " + BTree->rightMost(rootNode)->data);
Console::WriteLine("The size of this Binary Search Tree is: " + BTree->treeSize(rootNode));
Console::WriteLine("Printing Binary Search Tree in order: ");
BTree->printTreeInOrder(rootNode);

// TO EXAMINE THE PROPERTIES OF A GIVEN NODE, CHANGE THE SECOND PARAMETER OF 
// THE lookUp METHOD IN THE FOLLOWING LINE OF CODE TO THE NODE DESIRED TO BE EXAMINED
BTree->printNodeMembers(BTree->lookUp(rootNode, 7));
Console::WriteLine();
return 0;
}
4

1 回答 1

0

比较运算符不可用于泛型。没有定义它们的接口，并且与 C++ 模板不同，编译器不知道将使用的所有类型。

你想要的是IComparable<T>. 此接口定义方法CompareTo(T)，如果第一个对象分别小于、等于或大于另一个对象，则该方法将返回负数、零或正数。（这可能有点难以记住，所以请记住：(x [symbol] y)变成(x.CompareTo(y) [symbol] 0)。）

给定一个通用类型T，您不知道是否T实际实现IComparable<T>。您想要做的是强制编译器只允许实现IComparable<T>.

generic <typename T> where T : IComparable<T> ref class Node { ... };
generic <typename T> where T : IComparable<T> ref class BinarySearchTreeClass { ... };

现在您可以CompareTo在您的类中使用该方法：

if (node->data->CompareTo(key) < 0)
    return lookUp(node->right, key);
else
    return lookUp(node->left, key);

其他几个小的语法问题：

generic <typename T> ref class Node<T>: 不需要Node<T>，只要Node。Node 类已经是通用的，因为generic <typename T>，您也不需要<T>。

Node<T>(){}: 你不需要<T>. 泛型类的构造函数已经是泛型的，不需要再指定。

于 2012-11-29T06:38:50.587 回答