在C ++中将三元表达式转换为二叉树

在本教程中，我们将讨论将三元表达式转换为二叉树的程序。

为此，我们将提供一个三元表达式。我们的任务是根据可能的各种路径（选择），以二叉树的形式转换给定的表达式。

示例

#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