1697: 数据结构-二叉链表存储的二叉树

//二叉树的前序、中序递归遍历与先序生成
#include <bits/stdc++.h>
using namespace std;

typedef struct TNode *PtrToTNode;
typedef PtrToTNode BinTree;

typedef char ElementType;

struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

//二叉树的先序递归遍历
void PreorderTraversal(BinTree BT){
    if(BT){
        printf("%c ",BT->Data);
        PreorderTraversal(BT->Left);
        PreorderTraversal(BT->Right);
    }
}
//二叉树的中序递归遍历
void InOrderTraversal(BinTree BT){
    if(BT){
        InOrderTraversal(BT->Left);
        printf("%c ",BT->Data);
        InOrderTraversal(BT->Right);
    }
}

BinTree CreateBinTreeNode(ElementType X){
    BinTree node = (BinTree)malloc(sizeof(struct TNode));
    node->Data = X;
    node->Left = NULL;
    node->Right = NULL;
    return node;
}

BinTree PreCreateBinTree(){
    ElementType X;
    scanf("%c",&X);
    if(X==' '){
        return NULL;
    }
    else{
        BinTree BT = CreateBinTreeNode(X);
        BT->Left = PreCreateBinTree();
        BT->Right = PreCreateBinTree();
        return BT;
    }
}

//释放二叉树所有结点内存
void FreeBinTree(BinTree BT){
    if(BT){
        BinTree BTL=BT->Left,BTR=BT->Right;
        free(BT);
        BT = NULL;
        FreeBinTree(BTL);
        FreeBinTree(BTR);
    }
}

int main(){
    BinTree BT = PreCreateBinTree();

    PreorderTraversal(BT);
    cout << endl;
    InOrderTraversal(BT);
    cout << endl;
    InOrderTraversal(BT);

    FreeBinTree(BT);

    return 0;
}