java实现二叉树的遍历（递归和非递归）

刺骨的言语ヽ痛彻心扉 2022-05-30 07:20 274阅读 0赞

源码地址：
https://github.com/TimePickerWang/aimed-at-offer/blob/master/java%E6%BA%90%E7%A0%81/TreeInfo.java

现有一颗如下图所示的二叉树：

这里写图片描述

其遍历的各种方式如下：

这里写图片描述
这里写图片描述

构造一颗如下图所示的二叉树，用java实现其前序，中序，后序遍历

这里写图片描述

注意二叉树节点的定义如下：

  1. public class TreeNode {
  2.     int val;
  3.     TreeNode left;
  4.     TreeNode right;
  6.     TreeNode(int x) {
  7.         val = x;
  8.     }
  9. }

递归实现：

  1. // 用递归的方法进行先序遍历
  2.     public void qinaxuDigui(TreeNode treeNode) {
  3.         qianxuNumList.add(treeNode.val);
  4.         if (treeNode.left != null) {
  5.             qinaxuDigui(treeNode.left);
  6.         }
  7.         if (treeNode.right != null) {
  8.             qinaxuDigui(treeNode.right);
  9.         }
  10.     }
  12.     // 用递归的方法进行中序遍历
  13.     public void zhongxuDigui(TreeNode treeNode) {
  14.         if (treeNode.left != null) {
  15.             zhongxuDigui(treeNode.left);
  16.         }
  17.         zhongxuNumList.add(treeNode.val);
  18.         if (treeNode.right != null) {
  19.             zhongxuDigui(treeNode.right);
  20.         }
  21.     }
  23.     // 用递归的方法进行后序遍历
  24.     public void houxuDigui(TreeNode treeNode) {
  25.         if (treeNode.left != null) {
  26.             houxuDigui(treeNode.left);
  27.         }
  28.         if (treeNode.right != null) {
  29.             houxuDigui(treeNode.right);
  30.         }
  31.         houxuNumList.add(treeNode.val);
  32.     }

非递归实现：

  1. // 用非递归的方法进行先序遍历
  2.     public void qinaxuFeiDigui(TreeNode treeNode) {
  3.         Stack<TreeNode> stack = new Stack<TreeNode>();
  4.         while (treeNode != null || !stack.isEmpty()) {
  5.             while (treeNode != null) {
  6.                 qianxuNumList.add(treeNode.val);
  7.                 stack.push(treeNode);
  8.                 treeNode = treeNode.left;
  9.             }
  10.             if(!stack.isEmpty()){
  11.                 treeNode = stack.pop();
  12.                 treeNode = treeNode.right;
  13.             }
  14.         }
  15.     }
  17.     // 用非递归的方法进行中序遍历
  18.     public void zhongxuFeiDigui(TreeNode treeNode) {
  19.         Stack<TreeNode> stack = new Stack<TreeNode>();
  20.         while (treeNode != null || !stack.isEmpty()) {
  21.             while (treeNode != null) {
  22.                 stack.push(treeNode);
  23.                 treeNode = treeNode.left;
  24.             }
  25.             if (!stack.isEmpty()) {
  26.                 treeNode = stack.pop();
  27.                 zhongxuNumList.add(treeNode.val);
  28.                 treeNode = treeNode.right;
  29.             }
  30.         }
  31.     }
  33.     // 用非递归的方法进行后序遍历
  34.     public void houxuFeiDigui(TreeNode treeNode) {
  35.         Stack<TreeNode> stack = new Stack<TreeNode>();
  36.         while (treeNode != null || !stack.isEmpty()) {
  37.             while (treeNode != null) {
  38.                 stack.push(treeNode);
  39.                 treeNode = treeNode.left;
  40.             }
  41.             boolean tag = true;
  42.             TreeNode preNode = null;  // 前驱节点
  43.             while (!stack.isEmpty() && tag == true) {
  44.                 treeNode = stack.peek();
  45.                 if (treeNode.right == preNode) { // 之前访问的为空节点或是栈顶节点的右子节点
  46.                     treeNode = stack.pop();
  47.                     houxuNumList.add(treeNode.val);
  48.                     if (stack.isEmpty()) {
  49.                         return;
  50.                     } else {
  51.                         preNode = treeNode;
  52.                     }
  53.                 } else {
  54.                     treeNode = treeNode.right;
  55.                     tag = false;
  56.                 }
  57.             }
  58.         }
  59.     }

运行结果如下：

这里写图片描述

发表评论

表情：
评论列表 （有 0 条评论，274人围观）

还没有评论，来说两句吧...

相关阅读