二叉树先序中序后序遍历怎么写,三种顺序有什么区别
回答
三种遍历只差“访问根结点”的时机:先序 根→左→右,中序 左→根→右,后序 左→右→根,左右子树内部同样递归套用同一顺序。递归写法里,三种只需挪动访问语句的位置,空结点直接返回是递归出口。每个结点恰好访问一次,时间 O(n),递归栈深度等于树高 h(单链状的树 h = n)。中序遍历二叉搜索树得到升序序列。非递归写法借助显式栈:中序是一路向左压栈,弹出时访问再转向右子树。
- 先序:void pre(Node* t) { if (!t) return; visit(t); pre(t->left); pre(t->right); }
- 中序:把 visit(t) 放到两次递归调用之间;后序:放到两次递归调用之后。
例:A 的左孩子是 B(B 的孩子为 D、E),右孩子是 C(C 只有右孩子 F)。已用程序核对:先序 A B D E C F;中序 D B E A C F;后序 D E B F C A。
依据:严蔚敏《数据结构》「树和二叉树」一章中的二叉树遍历定义。
相关官方导图:数据结构期末 · 线性表与树