先序遍历
思路：先根节点->左子树->右子树；
二叉树如下图：
二叉树遍历算法
/**
* TreeSearch 简要描述
* <p> TODO:描述该类职责 </p>
*
* @author ckmike
* @version 1.0
* @date 18-12-6 下午10:13
* @copyright ckmike
**/
public class TreeSearch {
// 节点数据结构
class TreeNode{
private String value = null;
private TreeNode leftchildren = null;
private TreeNode rightchildre = null;
public TreeNode(String value, TreeNode leftchildren, TreeNode rightchildre) {
this.value = value;
this.leftchildren = leftchildren;
this.rightchildre = rightchildre;
}
public TreeNode(String value) {
this.value = value;
}
public void setValue(String value) {
this.value = value;
}
public void setLeftchildren(TreeNode leftchildren) {
this.leftchildren = leftchildren;
}
public void setRightchildre(TreeNode rightchildre) {
this.rightchildre = rightchildre;
}
public String getValue() {
return value;
}
public TreeNode getLeftchildren() {
return leftchildren;
}
public TreeNode getRightchildre() {
return rightchildre;
}
}
public TreeNode getTargetTree() {
// 叶子节点
TreeNode G = new TreeNode("G");
TreeNode D = new TreeNode("D");
TreeNode E = new TreeNode("E",G,null);
TreeNode B = new TreeNode("B",D,E);
TreeNode H = new TreeNode("H");
TreeNode I = new TreeNode("I");
TreeNode F = new TreeNode("F",H,I);
TreeNode C = new TreeNode("C",null,F);
// 构造根节点
TreeNode root = new TreeNode("A",B,C);
return root;
}
// 先序遍历二叉树
public void preorderVistTreeNode(TreeNode node){
if(null != node){
System.out.print(node.value);
if(null != node.leftchildren){
preorderVistTreeNode(node.leftchildren);
}
if(null != node.rightchildre){
preorderVistTreeNode(node.rightchildre);
}
}
}
public static void main(String[] args) {
TreeSearch treeSearch = new TreeSearch();
TreeNode tree= treeSearch.getTargetTree();
treeSearch.preorderVistTreeNode(tree);
}
}
二叉树遍历算法
先序遍历结果：ABDEGCFHI
中序遍历
思路：先左子树->根节点->右子树；
// 中序遍历
public void inorderVistTreeNode(TreeNode node){
if(null != node){
if(null != node.leftchildren){
inorderVistTreeNode(node.leftchildren);
}
System.out.print(node.value);
if(null != node.rightchildre){
inorderVistTreeNode(node.rightchildre);
}
}
}
public static void main(String[] args) {
TreeSearch treeSearch = new TreeSearch();
TreeNode tree= treeSearch.getTargetTree();
System.out.print("中序遍历:");
treeSearch.inorderVistTreeNode(tree);
}
二叉树遍历算法
中序遍历结果:DBGEACHFI
后序遍历
思路：先左子树->右子树->根节点；
// 后序遍历
public void postorderVistTreeNode(TreeNode node){
if(null != node){
if(null != node.leftchildren){
postorderVistTreeNode(node.leftchildren);
}
if(null != node.rightchildre){
postorderVistTreeNode(node.rightchildre);
}
System.out.print(node.value);
}
}
public static void main(String[] args) {
TreeSearch treeSearch = new TreeSearch();
TreeNode tree= treeSearch.getTargetTree();
System.out.print("后序遍历:");
treeSearch.postorderVistTreeNode(tree);
}
二叉树遍历算法
后序遍历结果：DGEBHIFCA
层序遍历
思路：先根节点，然后第二层，第三层，依次往下走，（同层节点从左往右输出）;
// 层序遍历
public void levelorderVistTreeNode(TreeNode node){
if(null != node){
LinkedList<TreeNode> list = new LinkedList<TreeNode>();
list.add(node);
TreeNode currentNode;
while (!list.isEmpty()){
currentNode = list.poll();
System.out.print(currentNode.value);
if(null != currentNode.leftchildren){
list.add(currentNode.leftchildren);
}
if(null != currentNode.rightchildre){
list.add(currentNode.rightchildre);
}
}
}
}
public static void main(String[] args) {
TreeSearch treeSearch = new TreeSearch();
TreeNode tree= treeSearch.getTargetTree();
System.out.print("层序遍历:");
treeSearch.levelorderVistTreeNode(tree);
}
二叉树遍历算法
层序遍历：ABCDEFGHI
这里要注意一点就是层序遍历二叉树，是非递归的队列实现的，就是利用队列的先进先出（FIFO）实现的。那么写到这里就把先序遍历、中序遍历、后序遍历、层序遍历二叉树的算法都写完了，是不是很简单。如果有兴趣可以想想有没有不用递归实现先、中、后序遍历的算法，用你熟悉的语言编写出来，写出来了记得分享出来哟。
©著作权归作者所有：来自51CTO博客作者刺激乐天派的原创作品，如需转载，请注明出处，否则将追究法律责任