数据结构--二叉树--按给定的表达式创建相应的二叉树

ゝ一纸荒年。 2022-08-24 11:42 131阅读 0赞

例如：已知表达式创建相应二叉树

已知表达式的先缀表示式：-\*+abc/de。

表达式 = （第一操作数）（运算符）（第二操作数）。把运算符当做根节点，第一、二操作数分别作为左右子树。

关键思想：如果为操作数则一定是根节点，左右指针不为空；如果为字符，一定是叶子节点，左右指针为空。

C语言实现：

/*加上空格字符的先序序列*/
     
    Status CreateBiTree(BiTree &T)
    {
       scanf(&ch);//扫描得到字符
       if(ch==' ') T=NULL;//如果字符为空，则根节点为空
       else {
             if (!T=(BiTNode *)malloc(sizeof(BiTNode)))//否则建立根节点
               exit(OVERFLOW);
               T->data = ch;//根节点数据域
               CreateBiTree(T->lchild);//构造左子树
               CreateBiTree(T->rchild);//构造右子树
             }
     return OK;
    }

C++实现：

//=============================================先序递归创建二叉树树  
    void CreateBiTree(BiTNode* &T){
        //按先序输入二叉树中结点的值（一个字符），空格字符代表空树，  
        //构造二叉树表表示二叉树T。  
        char ch;
        if ((ch = getchar()) == '#')
            T = NULL;//其中getchar（）为逐个读入标准库函数  
        else{
            T = new BiTNode;//产生新的子树  
            T->data = ch;//由getchar（）逐个读入来  
            CreateBiTree(T->lchild);//递归创建左子树  
            CreateBiTree(T->rchild);//递归创建右子树  
        }
    }//CreateTree

# [C++二叉树的前序建立与前中后遍历][C] #

思考：如果左子树不存在的情况，如何创建二叉树？

[C]: https://blog.csdn.net/cristina_song/article/details/78543077