二叉树及其应用--二叉树创建

给定二叉树的数据类型如下

typedef char Element;
struct Node
{
    Element data;
    struct Node *lchild;
    struct Node *rchild;
};
typedef struct Node BTNode;
typedef struct Node * BTree;
           

二叉树创建I

完成BTree Create_BTree(char s[])函数，该函数由字符串s创建一颗二叉树，其中字符串s是仅由’(‘，’)’，’,’以及大小写字符构成的二叉树的广义表表示，如A(B(D,),C(E,F(,H)))，字符串s以’\0’结尾。

BTree NewNode(Element x)
{
    BTree p=(BTree)malloc(sizeof(BTNode));
    p‐>data=x;
    p‐>lchild=NULL;
    p‐>rchild=NULL;
    return p;
}
BTree Create_BTree(char s[])
{
    int i,k,top;
    BTree path[N],p;
    k=;
    top=‐;
    for(i=;s[i]!='\0';i++)
    {
        switch(s[i])
        { 
        case '(':
            path[++top]=p;
            k=;
            break;
        case ',':
            k=;
            break;
        case ')':
            top‐‐;
            break;
        } 
        if(isalpha(s[i]))
        {
            p=NewNode(s[i]);
            if(k==)
                path[top]‐>lchild=p;
            else if(k==)
                path[top]‐>rchild=p;
        }
    } 
    return path[];
}
           

二叉树创建II

完成BTree Create_BTree(char s[],int left,int right)函数，该函数由字符串s(从s[left]到s[right])创建一颗二叉树，其中字符串s是仅由‘(’、‘)’、‘,’以及大小写字符构成的二叉树的广义表表示，如A(B(D,),C(E,F(,H)))，字符串s以’\0’结尾。

int find(char s[],int left,int right)
{
    int k=;
    int i;
    for(i=left;i<=right;i++)
    {
        if(s[i]==','&&k==1)
            return i;
        if(s[i]=='(')
            k++;
        else if(s[i]==')')
            k‐‐;
    } 
    return left;
}
BTree NewNode(Element x)
{
    BTree p=(BTree)malloc(sizeof(BTNode));
    p‐>data=x;
    p‐>lchild=NULL;
    p‐>rchild=NULL;
    return p;
}
BTree Create_BTree(char s[],int left,int right)
{
    int mid;
    if(left>right)
        return NULL;
    BTree p=NewNode(s[left]);
    mid=find(s,left,right);
    p‐>lchild=Create_BTree(s,left+,mid‐);
    p‐>rchild=Create_BTree(s,mid+,right‐);
    return p;
}
           

二叉树创建III

给出二叉树的先序遍历输出(空结点用’.’)表示，请构造二叉树，并按中序遍历的顺序输出二叉树的结点。

输入说明：

一行仅由‘.’与大小写字符构成的字符串，该字符串表示二叉树的前序遍历输出，其中’.’表示空结点，字符串长度不超过100。

输出说明：

在单独一行中按中序遍历的顺序输出二叉树的结点，空结点不输出。

输入样列：

ABD…C..

输出样列：

DBAC

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <cctype>
using namespace std;
#define N 100
typedef char Element;
struct Node
{
    Element data;
    struct Node *lchild;
    struct Node *rchild;
};
typedef struct Node BTNode;
typedef struct Node * BTree;
BTree Create_BTree();
BTree NewNode(Element x);
void Pre_Order(BTree root);
int main()
{
    BTree root;
    root=Create_BTree();
    Pre_Order(root);
    printf("\n");
    return ;
}
BTree NewNode(Element x)
{
    BTree p=(BTree)malloc(sizeof(BTNode));
    p‐>data=x;
    p‐>lchild=NULL;
    p‐>rchild=NULL;
    return p;
}
BTree Create_BTree()
{
    BTree root;
    char c;
    c=getchar();
    if(c=='.')
        return NULL;
    root=NewNode(c);
    root‐>lchild=Create_BTree();
    root‐>rchild=Create_BTree();
    return root;
}
void Pre_Order(BTree root)
{
    if(root!=NULL)
    {
        Pre_Order(root‐>lchild);
        printf("%c",root‐>data);
        Pre_Order(root‐>rchild);
    }
}