树4-树的确定与#号创建

只有中序遍历不能确定一个树

确定树的方法

中序遍历确定左右区域,而先序和后序确定实际位置

二叉树的#创建

二叉树结点

typedef struct BinaryNode{
    char ch;
    struct BinaryNode *lChild;
    struct BinaryNode *rChild;
} BinaryNode;

二叉树遍历

void Recursion(BinaryNode *root){
    if(root==NULL) return;
    cout << root->ch;
    Recursion(root->lChild);
    Recursion(root->rChild);
}

创建树

BinaryNode* CreateBinaryTree(){
    //清空缓冲区
    fflush(stdin);
    char ch;
    cout << "输入ch:" ;
    cin >> ch;
    //当ch为空时, 退出创建
    BinaryNode *node;
    // BinaryNode  *lChild, *rChild;

    if(ch=='#'){ //#表示当前结点为NULL
        node = NULL; 
    }else{
        // lChild = CreateBinaryTree();
        // rChild = CreateBinaryTree();
        node = (BinaryNode*)malloc(sizeof(BinaryNode));
        node->ch = ch;
        node->lChild = CreateBinaryTree();
        node->rChild = CreateBinaryTree();
    }

    return node;
}

测试

int main(void){
    //创建树
    BinaryNode *root = CreateBinaryTree();
    //递归遍历
    Recursion(root);
    cout << endl;
    
    // ABCD##P###QH###

    system("pause");
    return 0;
}