如何使用 C++ 将字符数组转换为二叉树
How to Convert a Char Array to a Binary Tree using C++
我有一个作业要将 postfix 表达式从 txt 文档转换为二叉树，然后计算该表达式。基础 class 是为我完成的，因此我不会将其包含在我的代码片段中。我正在使用和 getline() 逐行读取文件并将每个分配给一个字符串变量，然后传递给我的派生 class。然而，我正在努力解决的部分是将该字符串转换为 char 数组（因为分配要求我们这样做），然后使用该数组来确定将每个索引值添加到树上的位置。我认为问题是文本文档使用的数字大于 9（例如：35），我不知道如何在我的代码中说明这一点，所以我不断收到分段错误。无论如何，我将 post 下面的一些代码，如有任何帮助、解释或参考，我将不胜感激。
主要功能：
int main()
{
ifstream inFile;
ofstream outFile;
string pfx;
binaryExpressionTree tree;
inFile.open("RpnData.txt");
outFile.open("RpnDataOut.txt");
do
{
tree.destroyTree();
getline(inFile, pfx);
tree.buildExpressionTree(pfx);
outFile << tree.evaluateExpressionTree() << endl;
}
while (inFile);
}
我的头文件 class:
#ifndef EXPRESSIONTREE_H
#define EXPRESSIONTREE_H
#include "binaryTree.h"
class binaryExpressionTree : public binaryTreeType<string>
{
public:
void buildExpressionTree(string);
//Function to build the binary expression tree using a postfix string as a parameter
//Precondition: Must read a string as a parameter
//Postcondition: Will convert the string to a binary tree
double evaluateExpressionTree();
//Function to evaluate the expression tree
//Postcondition: Recursively calls the private function to evaluate the expression tree
bool search(const string&) const;
//Function to search for a string in the tree
//Precondition: Must have the address of a string to search for
//Postcondition: Returns true if string is found in the tree and false otherwise
void insert(const string&);
//Function to insert a string at the end of a branch on the tree
//Precondition: Must have the address of a string to insert
//Postcondition: Inserts the string at the end of a branch
void deleteNode(const string&);
//Function to delete one node (containing the string provided as a parameter) of the tree
//Precondition: Must have the address of a string to delete
//Postcondition: Deletes the string from the tree
private:
double evaluateExpressionTree(nodeType<string>*);
//Private function to evaluate the expression tree
//Precondition: Must have a pointer to a nodeType on the tree
//Postcondition: Returns the value of the postfix expression
};
#endif
产生问题的代码：
void binaryExpressionTree::buildExpressionTree(string pfxExpression)
{
stack<nodeType<string>*> *tree;
char* expression = new char[pfxExpression.length() +1];
strcpy(expression, pfxExpression.c_str());
for (int i = 0; i < pfxExpression.length(); i++)
{
if ((expression[i] >= 'a' && expression[i] <= 'z') || (expression[i] >= 'A' && expression[i] <= 'Z') || (expression[i] >= '0' && expression[i] <= '9'))
{
nodeType<string> *newNode;
newNode = new nodeType<string>; //Create new node
newNode->info = string(expression[i], expression[i+1]); //Set string of i to i+1 character in array to the info field
newNode->lLink = nullptr; //Make pointers for each branch nullptr
newNode->rLink = nullptr;
tree->push(newNode); //Push node onto the stack
//Through the use of cout statements, I have found that the error lies on the line above
}//end if
以下是在文本文件中找到的表达式：
35 27 + 3 *
23 30 15 * /
34 24 12 7 / * + 23 -
3 7 + 14 *
以下来自赋值说明本身，作为 buildExpressionTree() 成员函数的算法。如果格式不对，我深表歉意，我尽量让它更易读。
Here is the algorithm for building the expression tree:
Initialize a stack of pointers to binary tree nodes
Get a postfix expression (this will be an input to the evaluateExpressionTree function)
// This line did not really make sense to me since evaluate() takes no parameters
Convert the string to a character array (include <cstring>)
// This is the wording that led me to believe we are supposed to convert it
//to a char array
For each token in the expression:
If token is a number:
Create a node
Convert the token from a character array to a string
Store the string in the info field
Push the new node onto the stack
else if token is an operator:
Create a node and store the operator in the info field
If stack is not empty:
Use top() to get a reference to the node at the top of the stack
Store the reference in the rLink field of the new node.
Use pop() to remove the node from the stack
If stack is not empty:
Use top() to get a reference to the node at the top of the stack
Store the reference in the lLink field of the new node
Use pop() to remove the node from the stack
Push the new node back onto the stack
else:
Error – Stack is empty
else:
Error – Stack is empty
else:
Error – unsupported token
Get the next token
//This ends the for loop
if stack is not empty:
Pop the expression tree from the stack and store in root
If stack is not empty:
There was an error, set root back to null
最后，我将包含基础 class。需要挖掘的东西很多，我的教授没有把头文件和实现文件分开。
//Header File Binary Search Tree
#ifndef H_binaryTree
#define H_binaryTree
#include <iostream>
using namespace std;
//Definition of the Node
template <class elemType>
struct nodeType
{
elemType info;
nodeType<elemType> *lLink;
nodeType<elemType> *rLink;
};
//Definition of the class
template <class elemType>
class binaryTreeType
{
protected:
nodeType<elemType> *root;
public:
const binaryTreeType<elemType>& operator=
(const binaryTreeType<elemType>&);
//Overload the assignment operator.
bool isEmpty() const;
//Function to determine whether the binary tree is empty.
//Postcondition: Returns true if the binary tree is empty;
// otherwise, returns false.
void inorderTraversal() const;
//Function to do an inorder traversal of the binary tree.
//Postcondition: Nodes are printed in inorder sequence.
void preorderTraversal() const;
//Function to do a preorder traversal of the binary tree.
//Postcondition: Nodes are printed in preorder sequence.
void postorderTraversal() const;
//Function to do a postorder traversal of the binary tree.
//Postcondition: Nodes are printed in postorder sequence.
int treeHeight() const;
//Function to determine the height of a binary tree.
//Postcondition: Returns the height of the binary tree.
int treeNodeCount() const;
//Function to determine the number of nodes in a
//binary tree.
//Postcondition: Returns the number of nodes in the
// binary tree.
int treeLeavesCount() const;
//Function to determine the number of leaves in a
//binary tree.
//Postcondition: Returns the number of leaves in the
// binary tree.
void destroyTree();
//Function to destroy the binary tree.
//Postcondition: Memory space occupied by each node
// is deallocated.
// root = NULL;
virtual bool search(const elemType& searchItem) const = 0;
//Function to determine if searchItem is in the binary
//tree.
//Postcondition: Returns true if searchItem is found in
// the binary tree; otherwise, returns
// false.
virtual void insert(const elemType& insertItem) = 0;
//Function to insert insertItem in the binary tree.
//Postcondition: If there is no node in the binary tree
// that has the same info as insertItem, a
// node with the info insertItem is created
// and inserted in the binary search tree.
virtual void deleteNode(const elemType& deleteItem) = 0;
//Function to delete deleteItem from the binary tree
//Postcondition: If a node with the same info as
// deleteItem is found, it is deleted from
// the binary tree.
// If the binary tree is empty or
// deleteItem is not in the binary tree,
// an appropriate message is printed.
binaryTreeType(const binaryTreeType<elemType>& otherTree);
//Copy constructor
binaryTreeType();
//Default constructor
~binaryTreeType();
//Destructor
private:
void copyTree(nodeType<elemType>* &copiedTreeRoot,
nodeType<elemType>* otherTreeRoot);
//Makes a copy of the binary tree to which
//otherTreeRoot points.
//Postcondition: The pointer copiedTreeRoot points to
// the root of the copied binary tree.
void destroy(nodeType<elemType>* &p);
//Function to destroy the binary tree to which p points.
//Postcondition: Memory space occupied by each node, in
// the binary tree to which p points, is
// deallocated.
// p = NULL;
void inorder(nodeType<elemType> *p) const;
//Function to do an inorder traversal of the binary
//tree to which p points.
//Postcondition: Nodes of the binary tree, to which p
// points, are printed in inorder sequence.
void preorder(nodeType<elemType> *p) const;
//Function to do a preorder traversal of the binary
//tree to which p points.
//Postcondition: Nodes of the binary tree, to which p
// points, are printed in preorder
// sequence.
void postorder(nodeType<elemType> *p) const;
//Function to do a postorder traversal of the binary
//tree to which p points.
//Postcondition: Nodes of the binary tree, to which p
// points, are printed in postorder
// sequence.
int height(nodeType<elemType> *p) const;
//Function to determine the height of the binary tree
//to which p points.
//Postcondition: Height of the binary tree to which
// p points is returned.
int max(int x, int y) const;
//Function to determine the larger of x and y.
//Postcondition: Returns the larger of x and y.
int nodeCount(nodeType<elemType> *p) const;
//Function to determine the number of nodes in
//the binary tree to which p points.
//Postcondition: The number of nodes in the binary
// tree to which p points is returned.
int leavesCount(nodeType<elemType> *p) const;
//Function to determine the number of leaves in
//the binary tree to which p points
//Postcondition: The number of leaves in the binary
// tree to which p points is returned.
};
//Definition of member functions
template <class elemType>
binaryTreeType<elemType>::binaryTreeType()
{
root = NULL;
}
template <class elemType>
bool binaryTreeType<elemType>::isEmpty() const
{
return (root == NULL);
}
template <class elemType>
void binaryTreeType<elemType>::inorderTraversal() const
{
inorder(root);
}
template <class elemType>
void binaryTreeType<elemType>::preorderTraversal() const
{
preorder(root);
}
template <class elemType>
void binaryTreeType<elemType>::postorderTraversal() const
{
postorder(root);
}
template <class elemType>
int binaryTreeType<elemType>::treeHeight() const
{
return height(root);
}
template <class elemType>
int binaryTreeType<elemType>::treeNodeCount() const
{
return nodeCount(root);
}
template <class elemType>
int binaryTreeType<elemType>::treeLeavesCount() const
{
return leavesCount(root);
}
template <class elemType>
void binaryTreeType<elemType>::copyTree
(nodeType<elemType>* &copiedTreeRoot,
nodeType<elemType>* otherTreeRoot)
{
if (otherTreeRoot == NULL)
copiedTreeRoot = NULL;
else
{
copiedTreeRoot = new nodeType<elemType>;
copiedTreeRoot->info = otherTreeRoot->info;
copyTree(copiedTreeRoot->lLink, otherTreeRoot->lLink);
copyTree(copiedTreeRoot->rLink, otherTreeRoot->rLink);
}
} //end copyTree
template <class elemType>
void binaryTreeType<elemType>::inorder
(nodeType<elemType> *p) const
{
if (p != NULL)
{
inorder(p->lLink);
cout << p->info << " ";
inorder(p->rLink);
}
}
template <class elemType>
void binaryTreeType<elemType>::preorder
(nodeType<elemType> *p) const
{
if (p != NULL)
{
cout << p->info << " ";
preorder(p->lLink);
preorder(p->rLink);
}
}
template <class elemType>
void binaryTreeType<elemType>::postorder
(nodeType<elemType> *p) const
{
if (p != NULL)
{
postorder(p->lLink);
postorder(p->rLink);
cout << p->info << " ";
}
}
//Overload the assignment operator
template <class elemType>
const binaryTreeType<elemType>& binaryTreeType<elemType>::
operator=(const binaryTreeType<elemType>& otherTree)
{
if (this != &otherTree) //avoid self-copy
{
if (root != NULL) //if the binary tree is not empty,
//destroy the binary tree
destroy(root);
if (otherTree.root == NULL) //otherTree is empty
root = NULL;
else
copyTree(root, otherTree.root);
}//end else
return *this;
}
template <class elemType>
void binaryTreeType<elemType>::destroy(nodeType<elemType>* &p)
{
if (p != NULL)
{
destroy(p->lLink);
destroy(p->rLink);
delete p;
p = NULL;
}
}
template <class elemType>
void binaryTreeType<elemType>::destroyTree()
{
destroy(root);
}
//copy constructor
template <class elemType>
binaryTreeType<elemType>::binaryTreeType
(const binaryTreeType<elemType>& otherTree)
{
if (otherTree.root == NULL) //otherTree is empty
root = NULL;
else
copyTree(root, otherTree.root);
}
//Destructor
template <class elemType>
binaryTreeType<elemType>::~binaryTreeType()
{
destroy(root);
}
template<class elemType>
int binaryTreeType<elemType>::height
(nodeType<elemType> *p) const
{
if (p == NULL)
return 0;
else
return 1 + max(height(p->lLink), height(p->rLink));
}
template <class elemType>
int binaryTreeType<elemType>::max(int x, int y) const
{
if (x >= y)
return x;
else
return y;
}
template <class elemType>
int binaryTreeType<elemType>::nodeCount(nodeType<elemType> *p) const
{
if (p == nullptr)
return 0;
else
return 1 + nodeCount(p->lLink) + nodeCount(p->rLink);
}
template <class elemType>
int binaryTreeType<elemType>::leavesCount(nodeType<elemType> *p) const
{
if (p->lLink != nullptr && p->rLink != nullptr)
return 0 + leavesCount(p->lLink) + leavesCount(p->rLink);
else
return 1;
}
#endif
经过几个小时修改我的代码（感觉 运行 一遍又一遍地撞到墙上）我偶然发现了解决方案。虽然这个解决方案可能是我自己的问题所独有的，但我认为最好 post 它会更好，以防有人需要它。
void binaryExpressionTree::buildExpressionTree(string pfxExpression)
{
stack<nodeType<string>*> tree;
char* expression = new char[pfxExpression.length() +1];
strcpy(expression, pfxExpression.c_str());
char delim[] = " ";
char *token;
double num;
token = strtok(expression, delim);
do
{
if (isdigit(token[0]))
{
nodeType<string> *newNode;
newNode = new nodeType<string>; //Create new node
newNode->info = string(token); //Convert token to string and assign to info field
newNode->lLink = nullptr; //Make pointers for each branch nullptr
newNode->rLink = nullptr;
tree.push(newNode); //Push node onto the stack
}//end if
else if (token[0] == '+' || token[0] == '-' || token[0] == '*' || token[0] == '/')
{
nodeType<string> *newNode;
newNode = new nodeType<string>; //Create new node
newNode->info = string(token); //Set string of i to i+1 character in array to the info field
newNode->lLink = nullptr; //Make pointers for each branch nullptr
newNode->rLink = nullptr;
if (!tree.empty())
{
newNode->rLink = tree.top();
tree.pop();
if (!tree.empty())
{
newNode->lLink = tree.top();
tree.pop();
tree.push(newNode);
}
else
cout << "Error - stack is empty; not enough operands." << endl;
}// end if
else
cout << "Error - stack is empty; not enough operands." << endl;
}//end else if
else
cout << "Error - unsupported token." << endl;
}
while ((token = strtok(NULL, delim)) != NULL);
if (!tree.empty())
{
root = tree.top();
tree.pop();
if (!tree.empty())
{
root = nullptr;
cout << "Error - stack not empty after popping; clearing the tree." << endl;
}
}
}//end buildExpressionTree()
首先，由于@user4581301，我按照指示返回并注意到一些我以前没有注意到的东西。我的教授要求我们使用 strok 来标记字符数组。即使在更改了我的大部分功能代码之后，我的程序仍然产生了分段错误。
接下来，我在该网站上搜索了很多 post 以寻找类似的问题和答案，但几乎没有运气。我重新阅读了我原来 post 上的评论，并注意到另一个用户 @darcamo 也指出了另一个问题。我使用堆栈对象树作为指针而不是指针堆栈的对象。一旦我在 stack<nodeType<string>*> *tree 中的 tree 之前删除了额外的 * 我的代码 运行 没有问题，甚至从该函数输出正确的评估到输出文件（谢天谢地，我我不确定今晚是否可以设法调试另一个功能）。
说了这么多，再次感谢指出错误并提出其他解决方案的用户（虽然我自己不会用）
我有一个作业要将 postfix 表达式从 txt 文档转换为二叉树，然后计算该表达式。基础 class 是为我完成的，因此我不会将其包含在我的代码片段中。我正在使用和 getline() 逐行读取文件并将每个分配给一个字符串变量，然后传递给我的派生 class。然而，我正在努力解决的部分是将该字符串转换为 char 数组（因为分配要求我们这样做），然后使用该数组来确定将每个索引值添加到树上的位置。我认为问题是文本文档使用的数字大于 9（例如：35），我不知道如何在我的代码中说明这一点，所以我不断收到分段错误。无论如何，我将 post 下面的一些代码，如有任何帮助、解释或参考，我将不胜感激。
主要功能：
int main()
{
ifstream inFile;
ofstream outFile;
string pfx;
binaryExpressionTree tree;
inFile.open("RpnData.txt");
outFile.open("RpnDataOut.txt");
do
{
tree.destroyTree();
getline(inFile, pfx);
tree.buildExpressionTree(pfx);
outFile << tree.evaluateExpressionTree() << endl;
}
while (inFile);
}
我的头文件 class:
#ifndef EXPRESSIONTREE_H
#define EXPRESSIONTREE_H
#include "binaryTree.h"
class binaryExpressionTree : public binaryTreeType<string>
{
public:
void buildExpressionTree(string);
//Function to build the binary expression tree using a postfix string as a parameter
//Precondition: Must read a string as a parameter
//Postcondition: Will convert the string to a binary tree
double evaluateExpressionTree();
//Function to evaluate the expression tree
//Postcondition: Recursively calls the private function to evaluate the expression tree
bool search(const string&) const;
//Function to search for a string in the tree
//Precondition: Must have the address of a string to search for
//Postcondition: Returns true if string is found in the tree and false otherwise
void insert(const string&);
//Function to insert a string at the end of a branch on the tree
//Precondition: Must have the address of a string to insert
//Postcondition: Inserts the string at the end of a branch
void deleteNode(const string&);
//Function to delete one node (containing the string provided as a parameter) of the tree
//Precondition: Must have the address of a string to delete
//Postcondition: Deletes the string from the tree
private:
double evaluateExpressionTree(nodeType<string>*);
//Private function to evaluate the expression tree
//Precondition: Must have a pointer to a nodeType on the tree
//Postcondition: Returns the value of the postfix expression
};
#endif
产生问题的代码：
void binaryExpressionTree::buildExpressionTree(string pfxExpression)
{
stack<nodeType<string>*> *tree;
char* expression = new char[pfxExpression.length() +1];
strcpy(expression, pfxExpression.c_str());
for (int i = 0; i < pfxExpression.length(); i++)
{
if ((expression[i] >= 'a' && expression[i] <= 'z') || (expression[i] >= 'A' && expression[i] <= 'Z') || (expression[i] >= '0' && expression[i] <= '9'))
{
nodeType<string> *newNode;
newNode = new nodeType<string>; //Create new node
newNode->info = string(expression[i], expression[i+1]); //Set string of i to i+1 character in array to the info field
newNode->lLink = nullptr; //Make pointers for each branch nullptr
newNode->rLink = nullptr;
tree->push(newNode); //Push node onto the stack
//Through the use of cout statements, I have found that the error lies on the line above
}//end if
以下是在文本文件中找到的表达式：
35 27 + 3 *
23 30 15 * /
34 24 12 7 / * + 23 -
3 7 + 14 *
以下来自赋值说明本身，作为 buildExpressionTree() 成员函数的算法。如果格式不对，我深表歉意，我尽量让它更易读。
Here is the algorithm for building the expression tree:
Initialize a stack of pointers to binary tree nodes
Get a postfix expression (this will be an input to the evaluateExpressionTree function)
// This line did not really make sense to me since evaluate() takes no parameters
Convert the string to a character array (include <cstring>)
// This is the wording that led me to believe we are supposed to convert it
//to a char array
For each token in the expression:
If token is a number:
Create a node
Convert the token from a character array to a string
Store the string in the info field
Push the new node onto the stack
else if token is an operator:
Create a node and store the operator in the info field
If stack is not empty:
Use top() to get a reference to the node at the top of the stack
Store the reference in the rLink field of the new node.
Use pop() to remove the node from the stack
If stack is not empty:
Use top() to get a reference to the node at the top of the stack
Store the reference in the lLink field of the new node
Use pop() to remove the node from the stack
Push the new node back onto the stack
else:
Error – Stack is empty
else:
Error – Stack is empty
else:
Error – unsupported token
Get the next token
//This ends the for loop
if stack is not empty:
Pop the expression tree from the stack and store in root
If stack is not empty:
There was an error, set root back to null
最后，我将包含基础 class。需要挖掘的东西很多，我的教授没有把头文件和实现文件分开。
//Header File Binary Search Tree
#ifndef H_binaryTree
#define H_binaryTree
#include <iostream>
using namespace std;
//Definition of the Node
template <class elemType>
struct nodeType
{
elemType info;
nodeType<elemType> *lLink;
nodeType<elemType> *rLink;
};
//Definition of the class
template <class elemType>
class binaryTreeType
{
protected:
nodeType<elemType> *root;
public:
const binaryTreeType<elemType>& operator=
(const binaryTreeType<elemType>&);
//Overload the assignment operator.
bool isEmpty() const;
//Function to determine whether the binary tree is empty.
//Postcondition: Returns true if the binary tree is empty;
// otherwise, returns false.
void inorderTraversal() const;
//Function to do an inorder traversal of the binary tree.
//Postcondition: Nodes are printed in inorder sequence.
void preorderTraversal() const;
//Function to do a preorder traversal of the binary tree.
//Postcondition: Nodes are printed in preorder sequence.
void postorderTraversal() const;
//Function to do a postorder traversal of the binary tree.
//Postcondition: Nodes are printed in postorder sequence.
int treeHeight() const;
//Function to determine the height of a binary tree.
//Postcondition: Returns the height of the binary tree.
int treeNodeCount() const;
//Function to determine the number of nodes in a
//binary tree.
//Postcondition: Returns the number of nodes in the
// binary tree.
int treeLeavesCount() const;
//Function to determine the number of leaves in a
//binary tree.
//Postcondition: Returns the number of leaves in the
// binary tree.
void destroyTree();
//Function to destroy the binary tree.
//Postcondition: Memory space occupied by each node
// is deallocated.
// root = NULL;
virtual bool search(const elemType& searchItem) const = 0;
//Function to determine if searchItem is in the binary
//tree.
//Postcondition: Returns true if searchItem is found in
// the binary tree; otherwise, returns
// false.
virtual void insert(const elemType& insertItem) = 0;
//Function to insert insertItem in the binary tree.
//Postcondition: If there is no node in the binary tree
// that has the same info as insertItem, a
// node with the info insertItem is created
// and inserted in the binary search tree.
virtual void deleteNode(const elemType& deleteItem) = 0;
//Function to delete deleteItem from the binary tree
//Postcondition: If a node with the same info as
// deleteItem is found, it is deleted from
// the binary tree.
// If the binary tree is empty or
// deleteItem is not in the binary tree,
// an appropriate message is printed.
binaryTreeType(const binaryTreeType<elemType>& otherTree);
//Copy constructor
binaryTreeType();
//Default constructor
~binaryTreeType();
//Destructor
private:
void copyTree(nodeType<elemType>* &copiedTreeRoot,
nodeType<elemType>* otherTreeRoot);
//Makes a copy of the binary tree to which
//otherTreeRoot points.
//Postcondition: The pointer copiedTreeRoot points to
// the root of the copied binary tree.
void destroy(nodeType<elemType>* &p);
//Function to destroy the binary tree to which p points.
//Postcondition: Memory space occupied by each node, in
// the binary tree to which p points, is
// deallocated.
// p = NULL;
void inorder(nodeType<elemType> *p) const;
//Function to do an inorder traversal of the binary
//tree to which p points.
//Postcondition: Nodes of the binary tree, to which p
// points, are printed in inorder sequence.
void preorder(nodeType<elemType> *p) const;
//Function to do a preorder traversal of the binary
//tree to which p points.
//Postcondition: Nodes of the binary tree, to which p
// points, are printed in preorder
// sequence.
void postorder(nodeType<elemType> *p) const;
//Function to do a postorder traversal of the binary
//tree to which p points.
//Postcondition: Nodes of the binary tree, to which p
// points, are printed in postorder
// sequence.
int height(nodeType<elemType> *p) const;
//Function to determine the height of the binary tree
//to which p points.
//Postcondition: Height of the binary tree to which
// p points is returned.
int max(int x, int y) const;
//Function to determine the larger of x and y.
//Postcondition: Returns the larger of x and y.
int nodeCount(nodeType<elemType> *p) const;
//Function to determine the number of nodes in
//the binary tree to which p points.
//Postcondition: The number of nodes in the binary
// tree to which p points is returned.
int leavesCount(nodeType<elemType> *p) const;
//Function to determine the number of leaves in
//the binary tree to which p points
//Postcondition: The number of leaves in the binary
// tree to which p points is returned.
};
//Definition of member functions
template <class elemType>
binaryTreeType<elemType>::binaryTreeType()
{
root = NULL;
}
template <class elemType>
bool binaryTreeType<elemType>::isEmpty() const
{
return (root == NULL);
}
template <class elemType>
void binaryTreeType<elemType>::inorderTraversal() const
{
inorder(root);
}
template <class elemType>
void binaryTreeType<elemType>::preorderTraversal() const
{
preorder(root);
}
template <class elemType>
void binaryTreeType<elemType>::postorderTraversal() const
{
postorder(root);
}
template <class elemType>
int binaryTreeType<elemType>::treeHeight() const
{
return height(root);
}
template <class elemType>
int binaryTreeType<elemType>::treeNodeCount() const
{
return nodeCount(root);
}
template <class elemType>
int binaryTreeType<elemType>::treeLeavesCount() const
{
return leavesCount(root);
}
template <class elemType>
void binaryTreeType<elemType>::copyTree
(nodeType<elemType>* &copiedTreeRoot,
nodeType<elemType>* otherTreeRoot)
{
if (otherTreeRoot == NULL)
copiedTreeRoot = NULL;
else
{
copiedTreeRoot = new nodeType<elemType>;
copiedTreeRoot->info = otherTreeRoot->info;
copyTree(copiedTreeRoot->lLink, otherTreeRoot->lLink);
copyTree(copiedTreeRoot->rLink, otherTreeRoot->rLink);
}
} //end copyTree
template <class elemType>
void binaryTreeType<elemType>::inorder
(nodeType<elemType> *p) const
{
if (p != NULL)
{
inorder(p->lLink);
cout << p->info << " ";
inorder(p->rLink);
}
}
template <class elemType>
void binaryTreeType<elemType>::preorder
(nodeType<elemType> *p) const
{
if (p != NULL)
{
cout << p->info << " ";
preorder(p->lLink);
preorder(p->rLink);
}
}
template <class elemType>
void binaryTreeType<elemType>::postorder
(nodeType<elemType> *p) const
{
if (p != NULL)
{
postorder(p->lLink);
postorder(p->rLink);
cout << p->info << " ";
}
}
//Overload the assignment operator
template <class elemType>
const binaryTreeType<elemType>& binaryTreeType<elemType>::
operator=(const binaryTreeType<elemType>& otherTree)
{
if (this != &otherTree) //avoid self-copy
{
if (root != NULL) //if the binary tree is not empty,
//destroy the binary tree
destroy(root);
if (otherTree.root == NULL) //otherTree is empty
root = NULL;
else
copyTree(root, otherTree.root);
}//end else
return *this;
}
template <class elemType>
void binaryTreeType<elemType>::destroy(nodeType<elemType>* &p)
{
if (p != NULL)
{
destroy(p->lLink);
destroy(p->rLink);
delete p;
p = NULL;
}
}
template <class elemType>
void binaryTreeType<elemType>::destroyTree()
{
destroy(root);
}
//copy constructor
template <class elemType>
binaryTreeType<elemType>::binaryTreeType
(const binaryTreeType<elemType>& otherTree)
{
if (otherTree.root == NULL) //otherTree is empty
root = NULL;
else
copyTree(root, otherTree.root);
}
//Destructor
template <class elemType>
binaryTreeType<elemType>::~binaryTreeType()
{
destroy(root);
}
template<class elemType>
int binaryTreeType<elemType>::height
(nodeType<elemType> *p) const
{
if (p == NULL)
return 0;
else
return 1 + max(height(p->lLink), height(p->rLink));
}
template <class elemType>
int binaryTreeType<elemType>::max(int x, int y) const
{
if (x >= y)
return x;
else
return y;
}
template <class elemType>
int binaryTreeType<elemType>::nodeCount(nodeType<elemType> *p) const
{
if (p == nullptr)
return 0;
else
return 1 + nodeCount(p->lLink) + nodeCount(p->rLink);
}
template <class elemType>
int binaryTreeType<elemType>::leavesCount(nodeType<elemType> *p) const
{
if (p->lLink != nullptr && p->rLink != nullptr)
return 0 + leavesCount(p->lLink) + leavesCount(p->rLink);
else
return 1;
}
#endif
经过几个小时修改我的代码（感觉 运行 一遍又一遍地撞到墙上）我偶然发现了解决方案。虽然这个解决方案可能是我自己的问题所独有的，但我认为最好 post 它会更好，以防有人需要它。
void binaryExpressionTree::buildExpressionTree(string pfxExpression)
{
stack<nodeType<string>*> tree;
char* expression = new char[pfxExpression.length() +1];
strcpy(expression, pfxExpression.c_str());
char delim[] = " ";
char *token;
double num;
token = strtok(expression, delim);
do
{
if (isdigit(token[0]))
{
nodeType<string> *newNode;
newNode = new nodeType<string>; //Create new node
newNode->info = string(token); //Convert token to string and assign to info field
newNode->lLink = nullptr; //Make pointers for each branch nullptr
newNode->rLink = nullptr;
tree.push(newNode); //Push node onto the stack
}//end if
else if (token[0] == '+' || token[0] == '-' || token[0] == '*' || token[0] == '/')
{
nodeType<string> *newNode;
newNode = new nodeType<string>; //Create new node
newNode->info = string(token); //Set string of i to i+1 character in array to the info field
newNode->lLink = nullptr; //Make pointers for each branch nullptr
newNode->rLink = nullptr;
if (!tree.empty())
{
newNode->rLink = tree.top();
tree.pop();
if (!tree.empty())
{
newNode->lLink = tree.top();
tree.pop();
tree.push(newNode);
}
else
cout << "Error - stack is empty; not enough operands." << endl;
}// end if
else
cout << "Error - stack is empty; not enough operands." << endl;
}//end else if
else
cout << "Error - unsupported token." << endl;
}
while ((token = strtok(NULL, delim)) != NULL);
if (!tree.empty())
{
root = tree.top();
tree.pop();
if (!tree.empty())
{
root = nullptr;
cout << "Error - stack not empty after popping; clearing the tree." << endl;
}
}
}//end buildExpressionTree()
首先，由于@user4581301，我按照指示返回并注意到一些我以前没有注意到的东西。我的教授要求我们使用 strok 来标记字符数组。即使在更改了我的大部分功能代码之后，我的程序仍然产生了分段错误。
接下来，我在该网站上搜索了很多 post 以寻找类似的问题和答案，但几乎没有运气。我重新阅读了我原来 post 上的评论，并注意到另一个用户 @darcamo 也指出了另一个问题。我使用堆栈对象树作为指针而不是指针堆栈的对象。一旦我在 stack<nodeType<string>*> *tree 中的 tree 之前删除了额外的 * 我的代码 运行 没有问题，甚至从该函数输出正确的评估到输出文件（谢天谢地，我我不确定今晚是否可以设法调试另一个功能）。
说了这么多，再次感谢指出错误并提出其他解决方案的用户（虽然我自己不会用）