[算法] 二叉树

Mar 19, 2020

0x01、遍历

0x011、深度遍历

0x0111、前序遍历

根结点 —> 左子树 —> 右子树(根左右)
[13 8 1 6 11 17 15 25 22 27]

遍历节点时,再不为nil时,先输出根节点,再遍历左节点(把它作为一个新的节点,根节点),循环输出,直到最后一个节点的左节点为nil,遍历右节点(还是作为一个根节点),循环输出

0x0112、中序遍历

左子树—> 根结点 —> 右子树 (左根右)
[1 6 8 11 13 15 17 22 25 27]

同上,只是顺序不一样,还是每次遍历一个节点时把它当成根节点思考

0x0113、后序遍历

左子树 —> 右子树 —> 根结点 (左右根)
[6 1 11 8 15 22 27 25 17 13]

原理同上


递归
每个节点(包含根左右)作为一个Item,每个Item的节点又作为一个Item(除根节点)对其做递归执行

栈的遍历 (代码只写了中序遍历)
还是每个节点(包含根左右)作为一个Item,根据遍历顺序(前/中/后序)暂时不用的放到栈中,循环遍历下个Item,直到Item为空,那取出栈中的最后一个,遍历其另一个子节点

code地址

算法二叉树

UDP协议

comments powered by Disqus