遍历二叉树:
L:左 D:根 R:右
DLR-先根遍历
LDR-中序遍历
LRD-后序遍历
要求:给一棵二叉树,写出它的三种遍历顺序
根据先序,中序序列画出二叉树;根据中序,后序序列画出二叉树(上面的反推)
算法:根据递归
先序遍历:
Status PreOrderTraverse(BiTree T){
if(T==NULL) return OK;
else{
visit(T);//输出该结点的数据域
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
中序遍历:
Status InOrderTraverse(BiTree T){
if(T==NULL) return OK;
else{
PreOrderTraverse(T->lchild);
visit(T);//输出该结点的数据域
PreOrderTraverse(T->rchild);
}
}
后序遍历:
Status InOrderTraverse(BiTree T){
if(T==NULL) return OK;
else{
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
visit(T);//输出该结点的数据域
}
}
时间,空间复杂度: O(n)
标签:Status,遍历,中序,PreOrderTraverse,二叉树,NULL,线索 From: https://www.cnblogs.com/2-3-7/p/16906419.html