Java中二叉树的建立和各种遍历实例代码

这是个常见的面试题，比如说通过二叉树的先序和中序遍历，得到二叉树的层序遍历等问题

先序+中序->建树

假设现在有个二叉树，如下：

此时遍历顺序是：

preorder: gdafemhz 
inorder: adefghmz 
postorder: aefdhzmg

现在给出先序(preorder)和中序(inorder)，建立一颗二叉树
或者给出中序(inorder)和后序(postorder), 建立二叉树，其实是一样的

树节点的定义:

class tree{
	char val;
	tree left;
	tree right;
	tree(char val, tree left, tree right){
		this.val = val;
		this.left = left;
		this.right = right;
	}
	tree(){
	}
	tree(char val){
		this.val = val;
		this.left = null;
		this.right =null;
	}
}

建树:

public static tree buildtree(char[] preorder, char[] inorder){
	//preorder是先序序列
	//inorder是中序序列
	if(preorder == null || preorder.length == 0){
		return null;
	}
	tree root = new tree(preorder[0]);
	//找到inorder中的root的位置
	int inorderindex = 0;
	for (char i = 0; i < inorder.length; i++){
		if(inorder[i] == root.val){
			inorderindex = i;
		}
	}
	//preorder的左子树和右子树部分
	char[] preorderleft = arrays.copyofrange(preorder, 1, 1+inorderindex);
	char[] preorderright = arrays.copyofrange(preorder, 1+inorderindex, preorder.length);
	//inorder的左子树和右子树部分
	char[] inorderleft = arrays.copyofrange(inorder, 0, inorderindex);
	char[] inorderright = arrays.copyofrange(inorder, inorderindex+1, inorder.length);
	//递归建立左子树和右子树
	tree leftchild = buildtree(preorderleft, inorderleft);
	tree rightchild = buildtree(preorderright, inorderright);
	root.left = leftchild;
	root.right = rightchild;
	return root;
}

中序+后序去建树其实是一样的，此处不写了

各种遍历

后序遍历

public static void postorderprint(tree root){
    //后续遍历
    //左右根
    if(root.left != null){
      postorderprint(root.left);
    }
    if(root.right != null){
      postorderprint(root.right);
    }
    system.out.print(root.val + " ");
  }

举一反三，先序和中序是一样的，此处不写了

层序遍历

可以用一个队列queue，初始先把root节点加入到队列，当队列不为空的时候取队列头的节点node，打印node的节点值，如果node的左右孩子不为空将左右孩子加入到队列中即可

public static void layerorderprint(tree root){
    if(root == null){
      return;
    }
    //层序遍历
    queue<tree> qe = new linkedlist<tree>();
    qe.add(root);
    while(!qe.isempty()){
      tree node = qe.poll();
      system.out.print(node.val + " ");
      if(node.left != null){
        qe.add(node.left);
      }
      if(node.right != null){
        qe.add(node.right);
      }
    }
  }

深度优先和广度优先

其实就是换个说法而已，深度优先不就是先序遍历嘛，广度优先就是层序遍历

public static void deepfirstprint(tree root){
    //深度优先遍历等价于先序遍历
    //所以可以直接使用先序遍历
    if(root == null){
      return;
    }
    system.out.print(root.val + " ");
    if(root.left != null){
      deepfirstprint(root.left);
    }
    if(root.right != null){
      deepfirstprint(root.right);
    }
  }

public static void deepfirstprintnonerec(tree root){
    //深度优先遍历的非递归形式
    if(root == null){
      return;
    }
    stack<tree> st = new stack<tree>();
    st.add(root);
    while(!st.isempty()){
      tree node = st.pop();
      system.out.print(node.val + " ");
      //栈是后进先出的
      //先加右孩子后加左孩子
      if(node.right != null){
        st.add(node.right);
      }
      if(node.left != null){
        st.add(node.left);
      }
    }
  }

main函数：

public static void main(string[] args) {
    char[] preorder = "gdafemhz".tochararray();
    char[] inorder = "adefghmz".tochararray();
    tree root = main.buildtree(preorder, inorder);
//   main.postorderprint(root); //后序遍历
//   main.layerorderprint(root); //层序遍历
//   main.deepfirstprint(root); //深度优先遍历
//   main.deepfirstprintnonerec(root); //深度优先遍历的非递归版本
  }

总结

以上就是本文关于java中二叉树的建立和各种遍历实例代码的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站：

《java编程求二叉树的镜像两种方法介绍》

《java语言描述二叉树的深度和宽度》

《java二叉树路径和代码示例》

如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！