在本教程中,我们将讨论将三元表达式转换为二叉树的程序。
为此,我们将提供一个三元表达式。我们的任务是根据可能的各种路径(选择),以二叉树的形式转换给定的表达式。
#include<bits/stdc++.h> using namespace std; //树的节点结构 struct Node { char data; Node *left, *right; }; //创建新节点 Node *newNode(char Data){ Node *new_node = new Node; new_node->data = Data; new_node->left = new_node->right = NULL; return new_node; } //将三元表达式转换为二叉树 Node *convertExpression(string str, int & i){ //存储当前字符 Node * root =newNode(str[i]); //如果是最后一个字符,则返回基本情况 if(i==str.length()-1) return root; i++; //如果下一个字符是“?”, //然后将有当前节点的子树 if(str[i]=='?'){ //跳过“?” i++; root->left = convertExpression(str,i); //跳过':'字符 i++; root->right = convertExpression(str,i); return root; } else return root; } //打印二叉树 void display_tree( Node *root){ if (!root) return ; cout << root->data <<" "; display_tree(root->left); display_tree(root->right); } int main(){ string expression = "a?b?c:d:e"; int i=0; Node *root = convertExpression(expression, i); display_tree(root) ; return 0; }
输出结果
a b c d e