二叉树的先序遍历、中序遍历、后序遍历

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