/*
This program demonstrates a few routines for processing binary
sort trees. It uses a binary sort tree of strings. The user
types in strings. The user's string is converted to lower case, and --
if it is not already in the tree -- it is inserted into the tree.
Then the number of nodes in the tree and a list of items in the tree
are output. The program ends when the user enters an empty string.
*/
#include <iostream>
#include <string>
using namespace std;
class TreeNode {
// An object of type TreeNode represents one node
// in a binary tree of strings.
public:
// Constructor. Make a node containing str.
TreeNode(string str) : item(str), left(NULL), right(NULL) {}
string item; // The data in this node.
TreeNode *left; // Pointer to left subtree.
TreeNode *right; // Pointer to right subtree.
};
typedef TreeNode* TreeNodePtr;
void treeInsert(TreeNodePtr& root, string newItem);
// Add the item to the binary sort tree to which the parameter
// "root" refers. Note that root is passed by reference since
// its value can change in the case where the tree is empty.
bool treeContains( TreeNodePtr root, string item );
// Return true if item is one of the items in the binary
// sort tree to which root points. Return false if not.
void treeList(TreeNodePtr node);
// Print the items in the tree in postorder, one item
// to a line. Since the tree is a sort tree, the output
// will be in increasing order.
int countNodes(TreeNodePtr node);
// Count the nodes in the binary tree to which node
// points. Return the answer.
int main() {
TreeNodePtr root;// Pointer to the root node in a binary tree. This
// tree is used in this program as a binary sort tree.
// The tree is not allowed to contain duplicate
// items. When the tree is empty, root is null.
root = NULL; // Start with an empty tree.
cout << "This programs stores strings that you enter in a binary sort\n";
cout << "tree. After each items is inserted, the contents of the tree\n";
cout << "are displayed. The number of nodes in the tree is also output.\n";
cout << " Any string you enter will be converted to lower case.\n";
cout << "Duplicate entries are ignored.\n";
while (true) {
// Get one string from the user, insert it into the tree,
// and print some information about the tree. Exit if the
// user enters an empty string. Note that all strings are
// converted to lower case.
cout << ("\n\nEnter a string to be inserted, or press return to end.\n");
string item; // The user's input.
if (cin.peek() == '\n')
break;
cin >> item;
cin.ignore(10000,'\n'); // just in case a space and other words typed
if (treeContains(root,item)) {
// Don't insert a second copy of an item that is already
// in the tree.
cout << "\nThat item is already in the tree.\n";
}
else {
treeInsert(root,item); // Add user's string to the tree.
cout << "\nThe tree contains " << countNodes(root) << " items.\n";
cout << "\nContents of tree:\n\n";
treeList(root);
}
} // end while
cout << "\n\nExiting program.\n\n";
} // end main()
void treeInsert(TreeNodePtr& root, string newItem) {
// Add the item to the binary sort tree to which the parameter
// "root" refers. Note that root is passed by reference since
// its value can change in the case where the tree is empty.
if ( root == NULL ) {
// The tree is empty. Set root to point to a new node containing
// the new item. This becomes the only node in the tree.
root = new TreeNode( newItem );
return;
}
else if ( newItem < root->item ) {
treeInsert( root->left, newItem );
}
else {
treeInsert( root->right, newItem );
}
} // end treeInsert()
bool treeContains( TreeNodePtr root, string item ) {
// Return true if item is one of the items in the binary
// sort tree to which root points. Return false if not.
if ( root == NULL ) {
// Tree is empty, so it certainly doesn't contain item.
return false;
}
else if ( item == root->item ) {
// Yes, the item has been found in the root node.
return true;
}
else if ( item < root->item ) {
// If the item occurs, it must be in the left subtree.
return treeContains( root->left, item );
}
else {
// If the item occurs, it must be in the right subtree.
return treeContains( root->right, item );
}
} // end treeContains()
void treeList(TreeNodePtr node) {
// Print the items in the tree in inorder, one item
// to a line. Since the tree is a sort tree, the output
// will be in increasing order.
if ( node != NULL ) {
treeList(node->left); // Print items in left subtree.
cout << " " << node->item << endl; // Print item in the node.
treeList(node->right); // Print items in the right subtree.
}
} // end treeList()
int countNodes(TreeNodePtr node) {
// Count the nodes in the binary tree to which node
// points. Return the answer.
if ( node == NULL ) {
// Tree is empty, so it contains no nodes.
return 0;
}
else {
// Add up the root node and the nodes in its two subtrees.
int leftCount = countNodes( node->left );
int rightCount = countNodes( node->right );
return 1 + leftCount + rightCount;
}
} // end countNodes()
一件事不明白，为什么这个函数“ void treeInsert（TreeNodePtr＆root，string newItem）;”在TreeNodePtr之后有“＆”标记？其他人不...困惑！
感谢您的帮助！
最佳答案
根指针为passed by reference，因为在树为空的情况下其值可以更改。
干杯，……
关于c++ - C++通过引用传递？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4982362/