知识总览：

什么是遍历：

按照某种次序把所有节点都访问一遍

 

 二叉树的遍历-分支节点逐层展开法(会这个就行)：

先序(根)遍历：根左右   中序(根)遍历：左根右     后序(根)遍历：左右根

分支节点逐层展开法：先把节点按照先中后遍历顺序写上，再依次对非叶子节点进行展开

如下第5张图：先序遍历

1.按照根左右遍历顺序为A      B     C

2.B、C为非叶子节点，把B、C按照先序遍历再展开即B->B作为根是BDE，C作为根展开为CF，则目前序列为ABDECF

3.再看D、E、F是否为叶子节点，不是叶子节点的再次展开，即把D节点展开即D作为根是DG即序列为ABDGECF

代码： 

先序遍历代码

在根节点不为空的情况下，根据根左右的顺序，依次访问根节点，递归访问左子树、右子树节点

如下第二张图：先访问根节点即T=A，然后A不为空则visit(A)访问A，函数调用栈记录当前执行方法的相关信息如参数和执行行数，然后PreOrder递归访问A的左子树B，即T=B，B不为空访问B，然后再递归访问B的左子树即T=D，D不为空访问D再递归访问D的左子树，此时D的左子树为空则在下一轮循环中直接退出，即在函数调用栈中在T=NULL后然后马上弹出栈，即在T=NULL这一轮中执行到了126行，先把这一轮方法执行完，即弹出后即PreOrder(T->lchild)执行完后继续执行127行代码即PreOrder(T->rchild)开始PreOrder执行D的右子树即T=G每调用一次函数就压一次栈，即T=D时调用PreOrder(T->rchild)127行代码，然后G不为空访问G，T=G时再执行PreOrder(T->lchild)126行代码，再压栈一次，此时T=G的左子树=NULL，此时T=null弹出栈，现在执行到T=G的126行代码，再执行T=G的127行代码即执行T=G的右子树=NULL，则T==NULL弹出，此时T=G执行完弹出，然后执行T=D 127行代码已经执行结束，则弹出，则到T==B 126行代码该执行T==B 127行代码，即T==B的右子树=E，然后E不为空访问E，执行T==E 126行代码压栈，此时T== E的左子树==NUll为空弹出，则该执行T==E 127行代码压栈，此时T== E的右子树==NUll为空弹出，则到T==E 127行代码此时该轮函数执行完弹出，则函数调用栈中剩余T==A 126行代码则该执行T==A 127行代码，即T==A的右子树=C，C不为空访问C，执行T==C 126行代码压栈，即T==C的左子树==F，F不为空访问F执行T==F 126行代码压栈，即T==F的左子树==Null为空栈弹出，然后函数调用栈顶部为T==F 126行代码，则该执行T==F 127行代码即压栈，T==F的右子树==NUll为空栈弹出，则此时调用栈中T==F 127行代码整个方法执行结束栈弹出，调用栈剩T==C 126行代码则该执行T==C 127行代码压栈，即T==C的右子树==NULL则为空栈弹出，剩余T==C 127行即该轮执行结束弹出，调用栈剩T==A 127行代码即该轮执行结束弹出，即函数调用栈为空执行结束

中序遍历代码

在根节点不为空的情况下，根据左根右顺序，递归访问左子树，访问根节点，递归访问右子树节点

后序遍历代码 

在根节点不为空的情况下，根据左右根顺序，递归访问左子树、右子树，再访问根节点

求树的深度-应用

可以先序遍历左子树深度，再先序遍历右子树深度，然后求这俩的最大深度再加1即为树的深度

 

知识回顾：

 

。。。。。。。。。。。。