基础知识补充内容 - 图文

3、 线性链表元素的删除：在线性链表中删除包含x的结点

（1） 在线性链表中寻找包含元素x的前一个结点，设结点

号为q

（2） 将结点q后的结点p从线性链表中删除，即让结点q

的指针指向包含x的结点p的指针指向的结点。经过上述两步后，线性链表如图b所示

（3） 将包含元素x的结点p送回可利用栈，经过这一步后，

要利用栈的状态如图c所示，此时线性链表的删除运算完成。

二叉树的遍历

二叉树的三种遍历方式：先序遍历、中序遍历、后序遍历 先序：

始终执行以下步骤，

1、访问根节点 2、遍历左子树 3、遍历右子树 中序：

始终执行以下步骤， 1、遍历左子树 2、访问根节点 3、遍历右子树 后序：

始终执行以下步骤， 1、遍历左子树 2、遍历右子树 3、访问根节点

“始终”：为什么要说“始终”执行呢？因为二叉树的每一个子树又可以看成是一个新的二叉树，遍历步骤、方式都保持一样，所以应该“始终”执行同样的操作，我们也应该始终把它看成一棵新的二叉树。 一些技巧：

1、先序遍历第一个元素一定是根节点

2、中序遍历中，任何一个元素的前一个元素一定在二叉树中它的左边，比如D在G前面，则D在G左边 3、后序遍历最后一个元素一定是根节点

4、先、中、后意思是说访问根节点的先后顺序，而且始终从左往右，从上往下

A B C

先序遍历为：ABC 中序遍历为：BAC 后序遍历为：BCA

A B C D E F G

先序遍历为：ABDECFG 中序遍历为：DBEAFCG 后序遍历为：AEBFGCA

a b e c d f 前序遍历：abcdef 中序遍历：cbdaef 后序遍历：cdbfea

A B D G E C F

先序遍历为：ABDGCEF 中序遍历为：DGBAECF 后序遍历为：GDBEFCA

前序遍历结果为 a b d e h i c f g 中序遍历结果为 d b h e i a f c g 后序遍历结果为 d h i e b f g c a

F C E A D G B H P

前序遍历结果为 FCADBEGHP 中序遍历结果为 ACBDFEHGP