image.png
image.png
image.png
时间效率:O(n) //每个结点只访问一次
空间效率:O(n) //栈占用的最大辅助空间
代码
Status PreOrderTraverse(BiTree T){
if(T==NULL) return OK;
else{
cout<<T->data;
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
Status InOrderTraverse(BiTree T){
if(T==NULL) return OK;
else{
InOrderTraverse(T->lchild);
cout<<T->data;
InOrderTraverse(T->rchild);
}
}
Status PostOrderTraverse(BiTree T){
if(T==NULL) return OK;
else{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data;
}
}
b58f8c5494eef01fb1192796e0fe9925bc317d57.jpg
首先 观察这个二叉树
可见是这样的：1.以B为根节点的左子树 A根节点 以C为根节点的右子树
2.以D为根节点的左子树 B根节点 以E为根节点的右子树
3.以G为根节点的左子树 D根节点 以H为根节点的右子树
4.以K为根节点的左子树 C根节点 以F为根节点的右子树
5.以I为根节点的左子树 F根节点 右子树为空
6.左子树为空 I根节点 以J为根节点的右子树
接下来可以进行遍历了：
前序遍历 是 根 左子树 右子树：
即先是跟节点A 然后遍历 B子树 遍历完B子树后 再遍历C子树 即最后答案为：
ABDGHECKFIJ
中序遍历为 左子树 根 右子树
先遍历 B子树 遍历完了 再是A节点 然后是右子树 答案为：
GDHBEAKCIJF
后序遍历是 左子树 右子树 根
答案为：
GHDEBKJIFCA
image.png
试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。
答：
DLR：A B D F J G K C E H I L M
LDR: B FJ D G KAC H E LI M
LRD：J F K G D B H L M I E C A
