二叉樹及其應用--二叉樹建立

給定二叉樹的資料類型如下

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);
    }
}