Java实现二叉树先序、中序、后序遍历(递归与非递归)及层次遍历
程序员文章站
2022-06-17 17:52:20
...
Java中一切皆对象,采用TreeNode类封装节点,代码如下:
class TreeNode{
char val;//data域
TreeNode left;//左孩子
TreeNode right;//右孩子
public TreeNode(char val){
this.val = val;
}
}
图1
先序遍历
操作: 如果二叉树为空树,什么也不做;否则:
(1)、访问根节点。
(2)、先序遍历左子树。
(3)、先序遍历右子树。
图1二叉树的先序遍历结果为:A,B,C,D,E,F
递归遍历:
/**先序遍历
*
* @param root 根节点
* @param sb 用于拼接节点的值
*/
public void preorder(TreeNode root,StringBuilder sb){
if(root != null){
sb.append(root.val);//访问根节点
preorder(root.left,sb);//先序遍历左子树
preorder(root.right,sb);//先序遍历右子树
}
}
非递归遍历:
/**先序遍历
*
* @param root 根节点
* @param sb 用于拼接节点的值
*/
public void preorder(TreeNode root,StringBuilder sb){
if(root != null){
Deque<TreeNode> stack = new ArrayDeque<>();
stack.addLast(root);//根节点先入栈
while(!stack.isEmpty()){
TreeNode tn = stack.removeLast();
sb.append(tn.val);//访问节点
if(tn.right != null) stack.addLast(tn.right);//右节点存在,右节点先入栈
if(tn.left != null) stack.addLast(tn.left);//左节点存在,左节点后入栈
}
}
}
中序遍历
操作: 如果二叉树为空树,什么也不做;否则:
(1)、中序遍历左子树。
(2)、访问根节点。
(3)、中序遍历右子树。
图1二叉树的中序遍历结果为:C,B,D,A,E,F
递归遍历:
/**中序遍历
*
* @param root 根节点
* @param sb 用于拼接节点的值
*/
public void inorder(TreeNode root,StringBuilder sb){
if(root != null){
inorder(root.left,sb);//中序遍历左子树
sb.append(root.val);//访问根节点
inorder(root.right,sb);//中序遍历右子树
}
}
非递归遍历:
/**中序遍历
*
* @param root 根节点
* @param sb 用于拼接节点的值
*/
public void inorder(TreeNode root,StringBuilder sb){
if(root != null){
Deque<TreeNode> stack = new ArrayDeque<>();
while (!stack.isEmpty() || root !=null){
while (root != null){
stack.addLast(root);
root = root.left;
}
if(!stack.isEmpty()){
root = stack.removeLast();
sb.append(root.val);
root = root.right;
}
}
}
}
后序遍历
操作: 如果二叉树为空树,什么也不做;否则:
(1)、后序遍历左子树。
(2)、后序遍历右子树。
(3)、访问根节点。
图1二叉树的后序遍历结果为:C,D,B,F,E,A
递归遍历:
/**后序遍历
*
* @param root 根节点
* @param sb 用于拼接节点的值
*/
public void postorder(TreeNode root,StringBuilder sb){
if(root != null){
inorder(root.left,sb);//后序遍历左子树
inorder(root.right,sb);//后序遍历右子树
sb.append(root.val);//访问根节点
}
}
非递归遍历:
/**后序遍历
*
* @param root 根节点
* @param sb 用于拼接节点的值
*/
public void postorder(TreeNode root,StringBuilder sb){
if(root != null){
Deque<TreeNode> stack = new ArrayDeque<>();
stack.addLast(root);
while (!stack.isEmpty()){
root = stack.removeLast();
sb.append(root.val);
//注意这里跟先序遍历相反,最后的结果需对sb逆序输出即sb.reverse()
if(root.left != null) stack.addLast(root.left);
if (root.right != null) stack.addLast(root.right);
}
}
}
层次遍历
操作: 建立一个循环队列,先将二叉树头节点入队列,然后出队列,访问该节点,如果它有左子树,则将左子树入队列,如果它有右子树,则将右子树入队列。然后出队列,对出队节点访问,如此反复,直到队列为空为止。
图1二叉树的层次遍历结果为:A,B,E,C,D,F
代码:
/**层次遍历
*
* @param root 根节点
* @param sb 用于拼接节点的值
*/
public void level(TreeNode root,StringBuilder sb){
if(root != null){
Deque<TreeNode> que = new ArrayDeque<>();
que.addLast(root);//先将根节点入队列
while (!que.isEmpty()){
root = que.removeFirst();//出队列
sb.append(root.val);//访问该节点
if (root.left != null) que.addLast(root.left);//左子树存在,入队列
if (root.right != null) que.addLast(root.right);//右子树存在,入队列
}
}
}
推荐阅读
-
Python实现二叉树前序、中序、后序及层次遍历示例代码
-
PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例
-
二叉树遍历 前序遍历 后序遍历 中序遍历 非递归前序遍历 二叉树遍历非递归
-
JavaScript实现二叉树的先序、中序及后序遍历方法详解
-
左神算法:分别用递归和非递归方式实现二叉树先序、中序和后序遍历(Java版)
-
二分搜索树 BST 前序\中序\后序(递归和非递归实现)和层序遍历
-
PYTHON实现二叉树的层次遍历,先序遍历,中序遍历,后序遍历
-
PHP基于非递归算法实现先序、中序及后序遍历二叉树操作示例
-
Java实现二叉树先序、中序、后序遍历(递归与非递归)及层次遍历
-
JAVA 实现二叉树建立和先序,中序和后序遍历(递归与非递归)