如何学习数据结构[3]

对于总结共性问题上这里举一小个例子(呵呵我当初总结出这个并且和kaoyancom斑竹一具讨论确定后三天就在年交大第一题考出类似东东）比如树的遍历不管是递归还是非递归也不管是线索树还是头结点有父母信息的树它的遍历其实就是一个寻找到遍历的第一个结点然后再寻找它的后继结点的过程我们归纳到此处就可以试着总结一下三种遍历的后继结点是哪个有几种情况

对于前序遍历它的后继如下

（）若有左孩子则后继是左孩子

（）若无左孩子有右孩子则后继是右孩子

（）若既无左孩子又无右孩子则是一片叶子再讨论

（a）若是其父母的左孩子且父母有右孩子则后继是父母的右孩子

（b）若是其父母的左孩子且父母无右孩子

（c）若是其父母的右孩子

bc都表示这是某个节点的左子树前序遍历的最后一个节点则需要找第一个有右子树的左祖先（定义左祖先即找第一个使得当前节点在这个祖先的左子树上）然后后继就是这个祖先的右孩子

[] [] [] []