二叉树遍历

2024-01-02 18:18:01

#include<iostream>
#include<stack>
#include<string>

using namespace std;

struct TreeNode
{
? ? char data;
? ? TreeNode* leftChild;
? ? TreeNode* rightChild;
};

TreeNode* createTreeNode(const char* str)
{
? ? stack<TreeNode*> s;
? ? TreeNode* root = nullptr;
? ? TreeNode* currentNode = nullptr;
? ? bool isleftChild = false;

? ? for(int i = 0; str[i] != '\0'; i++)
? ? {
? ? ? ? char ch = str[i];

? ? ? ? switch(ch)
? ? ? ? {
? ? ? ? ? ? case '{':
? ? ? ? ? ? ? ? s.push(currentNode);
? ? ? ? ? ? ? ? isleftChild = true;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? case ',':
? ? ? ? ? ? ? ? isleftChild = false;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? case '}':
? ? ? ? ? ? ? ? s.pop();
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? default:
? ? ? ? ? ? ? ? currentNode = new TreeNode();
? ? ? ? ? ? ? ? currentNode->data = ch;

? ? ? ? ? ? ? ? if(root == nullptr)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? root = currentNode;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? if(isleftChild)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? s.top()->leftChild = currentNode;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? s.top()->rightChild = currentNode;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? break;
? ? ? ? }
? ? }

? ? return root;
}

void inOrderTraversal(TreeNode* root)
{
? ? if(root == nullptr)
? ? {
? ? ? ? return;
? ? }
? ? else
? ? {
? ? ? ? inOrderTraversal(root->leftChild);
? ? ? ? cout << root->data << " ";
? ? ? ? inOrderTraversal(root->rightChild);
? ? }
}

int main()
{
? ? string inputStr;
? ? getline(cin, inputStr);

? ? TreeNode* root = createTreeNode(inputStr.c_str());

? ? inOrderTraversal(root);

? ? cout << endl;

? ? return 0;
}
?

文章来源:https://blog.csdn.net/xlfdlbx/article/details/135344473
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。