二叉树相关问题

文章目录

1. 构建二叉树

typedef struct BiTNode{
    int  data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//先序建立二叉树
BiTree CreateBiTree(){
    int ch;
    BiTree T;
    scanf("%d",&ch);
    if(ch==-1)T=NULL;//输入-1表示该节点为空
    else{
        T = (BiTree)malloc(sizeof(BiTNode));//分配节点空间
        T->data = ch;
        T->lchild = CreateBiTree();//创建左子树
        T->rchild = CreateBiTree();//创建右子树
    }
    return T;//返回根节点
}

1. 二叉树遍历。
   前序遍历，中序遍历，后序遍历是根据访问根节点的顺序命名的。

前序遍历：根，左，右

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

中序遍历：左，根，右

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

后序遍历：左，右，根

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