利用先序扩展序列建立二叉树

题目

• 先序扩展序列是指用特定的字符表示空子树。这里用‘#’表示二叉树为空。
• 现给出一个字符串为二叉树的线序扩展序列，要求建立一棵二叉树。

思路

• 定义二叉树
• 初始化二叉树

定义二叉树

• C定义二叉树

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode
{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

• C++定义二叉树

typedef struct TNode{
    char Data;
    TNode* Left;
    TNode* Right;
}*BinTree;

初始化二叉树

• 下面给出两个函数，一个带参，一个不带参。

BinTree CreateBinTree()
{
    BinTree BT;
    BT = (BinTree)malloc(sizeof(struct TNode));
    ElementType ch;
    scanf("%c",&ch);
    if(ch == '#'){
        BT = NULL;
        return BT;
    }
    BT->Data = ch;
    BinTree LBT, RBT;
    LBT = CreatBinTree();
    RBT = CreatBinTree();
    BT->Left = LBT;
    BT->Right = RBT;
    return BT;
}

//主函数中：
int main(){
	……
	BinTree BT;
	CreateBinTree(&BT);	//注意：这里有个取地址符
	……
}

void CreateBinTree(BinTree *BT){	//注意传的参数
    char ch;
    cin >> ch;
    if(ch == '#')   *BT = NULL;
    else{
        *BT = (BinTree)malloc(sizeof(TNode));
        (*BT)->data = ch;
        CreateBinTree(&((*BT)->Left));
        CreateBinTree(&((*BT)->Right));
    }
    return;
}