二叉树基础知识总结 - CSDN博客

二叉树遍历分析

 简单二叉树遍历，可分为：先序，中序，后序。

 先序： 1.访问根结点；2.访问左子树；3.访问右子树

中序：1.访问左子树； 2.访问根结点； 3.访问右子树

原则：1访问左子树。【先访问左子树中的左子树，再访问左子树中的右子树。】直到访问到叶子结点后输出。

2输出根。

3访问右子树。【先访问右子树中的左子树，再访问右子树中的右子树。】直到访问到叶子结点后输出。

 后序：1.访问左子树

　　　  2.访问右子树

          3.访问根

1访问左子树。【先访问左子树中的左子树，再访问左子树中的右子树】。直到访问到叶子结点后输出。

2访问右子树。【先访问右子树中的左子树，再访问右子树中的右子树】。直到访问到叶子结点后输出。

3再返回访问根，并输出。

具体步骤：

  先访问A的左子树。再访问左子树中的左子树。【即：A的左子树为B，再访问B的左子树D。D没有左右子树，输出D。】，然后访问左子树中的右子树。【即：访问B的右子树F，F还有左子树，再访问F的左子树E，E没有左右子树。输出E。再输出F，再输出B。】。

  然后访问A的右子树。再访问右子树中的左子树。【即：A的右子树为C，再访问C的左子树G。G还有右子树H，输出H。再输出G，再输出G】，然后访问右子树中的右子树。【即：访问C的右子树I，I没有左右子树，输出I。在输出C。再输出A。】。

  所以，后序遍历输出结果为：（D E F B）（H G I C）A

插入节点

插入的节点是叶子节点；