1、参考书本算法5.3编写构建二叉链表，元素类型为整数。 void createtree(BiTree &T) { } 2、参考书本算法分别编写二叉树的三种遍历算法。 void inorder(BiTree T) { } void preorder(BiTree T) { } void postorder(BiTree T) { } 3、根据二叉树中序遍历的非递归算法，在二叉树t查找值为x的元素，若找到且其左子树为空，则将值为y的元素插入成为其左孩子，否则若其右孩子为空，则将y插入成为其右孩子。插入失败，返回值为0，否则返回值为1。

1、参考书本算法5.3编写构建二叉链表，元素类型为整数。

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void createtree(BiTree &T) {
    int d;
    scanf("%d", &d);
    if (d == -1) {
        T = NULL;
    } else {
        T = (BiTree)malloc(sizeof(BiTNode));
        T->data = d;
        createtree(T->lchild);
        createtree(T->rchild);
    }
}

2、参考书本算法分别编写二叉树的三种遍历算法。

void inorder(BiTree T) {
    if (T) {
        inorder(T->lchild);
        printf("%d ", T->data);
        inorder(T->rchild);
    }
}

void preorder(BiTree T) {
    if (T) {
        printf("%d ", T->data);
        preorder(T->lchild);
        preorder(T->rchild);
    }
}

void postorder(BiTree T) {
    if (T) {
        postorder(T->lchild);
        postorder(T->rchild);
        printf("%d ", T->data);
    }
}

3、根据二叉树中序遍历的非递归算法，在二叉树t查找值为x的元素，若找到且其左子树为空，则将值为y的元素插入成为其左孩子，否则若其右孩子为空，则将y插入成为其右孩子。插入失败，返回值为0，否则返回值为1。

int insert_node(BiTree t, int x, int y) {
    stack<BiTree> s;
    BiTree p = t, q = NULL;
    while (p || !s.empty()) {
        while (p) {
            s.push(p);
            p = p->lchild;
        }
        if (!s.empty()) {
            p = s.top();
            s.pop();
            if (p->data == x) {
                if (!p->lchild) {
                    p->lchild = new BiTNode;
                    p->lchild->data = y;
                    p->lchild->lchild = p->lchild->rchild = NULL;
                    return 1;
                } else if (!p->rchild) {
                    p->rchild = new BiTNode;
                    p->rchild->data = y;
                    p->rchild->lchild = p->rchild->rchild = NULL;
                    return 1;
                } else {
                    return 0;
                }
            }
            q = p;
            p = p->rchild;
        }
    }
    return 0;
}