表达式转换为二叉树

Problem statement:

问题陈述：

Given a string that contains ternary expressions. The expressions may be nested. You need to convert the given ternary expression to a binary Tree and return the root.

给定一个包含三元表达式的字符串。 表达式可以嵌套。 您需要将给定的三元表达式转换为二叉树并返回根 。

Example:

例：

Input:    a?b:c    Output:      a     / \    b   c    Input:    a?b?c:d:e    Output:        a       / \      b   e     / \    c   d

Solution:

解：

Ternary expression: In C, we are acquainted with the ternary expression. Ternary expressions are equivalent to the if-else statement in C.

三元表达式：在C语言中，我们熟悉三元表达式。 三元表达式等效于C语言中的if-else语句。

if(a)        b    else        c    a,b,c=statements/expressions    This if else statement is equivalent to a?b:c

Similarly, a ternary expression can be converted to a binary tree, where a will be the root, b will be the left child and c will be the right one. This small miniature can be expanded (followed) for nesting ternary expression.

类似地，三元表达式可以转换为二叉树，其中a将是根，b将是左子，而c将是右。 这个小的缩图可以扩展(跟随)以嵌套三元表达式。

The algorithm for constructing the binary tree from the ternary expression is:

从三元表达式构造二叉树的算法是：

Pre-requisite:

先决条件：

1. Ternary expression str

   三元表达海峡

2. Node* newNode(string str, index i) : Creates a new node with data value str[i]

   Node * newNode(string str，index i) ：创建一个新节点，其数据值为str [i]

Algorithm:

算法：

//recursive function to build the tree    FUNCTION convertExpression(string str, int& i)     1.  Create root referring to the current character(str[i]);    root =newNode(str,i); //create a node with element str[i]    2.  Increment i (index that point to current character);        //if i
    
     left=convertExpression(str,i); 	    //need to build right child recursively        root->right=convertExpression(str,i);     4.  return root;
    

Algorithm with example:

示例算法：

Tree nodes represented by their values onlyInput string (ternary expression)a?b:c-------------------------------------------------In main function we call convertExpression(str,0)convertExpression(str,0):root=newNode(str, 0); //root=ai=1; //incrementedi
    
     left=convertExpression(str,2);-------------------------------------------------convertExpression(str,2):root=newNode(str, 2); //root=bi=3; //incrementedi
     
      left=bi=4; //i++ step evaluatedroot->right=convertExpression(str,4)-------------------------------------------------convertExpression(str,4):root=newNode(str, 4); //root=ci=5; //incrementedI is not 
      
       right=creturn root;returns to mainbuilt tree:  a / \b   c
      
     
    

C++ implementation

C ++实现

#include 
    
     using namespace std;struct Node{
   	char data;	Node *left,*right;};//function to create nodeNode *newNode(char Data) {
   	Node *new_node = new Node;	new_node->data = Data;	new_node->left = new_node->right = NULL;	return new_node;}//function to traverse preordervoid preorder(Node *root){
    	if(root==NULL)		return;	cout<
     
      data<<" ";	preorder(root->left);	preorder(root->right);}//recursive function to build the treeNode *convertExpression(string str,int& i) {
   	Node* root=newNode(str[i]);	i++;	if(i
      
       left=convertExpression(str,i);		i++; //skipping ':' character		root->right=convertExpression(str,i);	}	return root;}int main(){
   	string str;		cout<<"Enter your expression\n";	cin>>str;		int i=0;	Node *root=convertExpression(str,i);	cout<<"Printing pre-order traversal of the tree...\n";	//pre-order traversal of the tree, 	//should be same with expressionthe 	preorder(root);	cout<
      
     
    

Output

输出量

First run:Enter your expressiona?b:cPrinting pre-order traversal of the tree...a b cSecond run:Enter your expressiona?b?c:e:dPrinting pre-order traversal of the tree...a b c e d

翻译自:

表达式转换为二叉树