1. Python实现

  1. class TreeNode:
  2.     def __init__(self, x):
  3.         self.val = x
  4.         self.left = None
  5.         self.right = None
  7. class Solution:
  8.     def __init__(self):
  9.         self.res = []
  11.     # 先序遍历
  12.     def getPreOrder(self, root):
  13.         # 递归法
  14.         def preOrderRec(root):
  15.             if not root:
  16.                 return None
  17.             # 根左右
  18.             self.res.append(root.val)
  19.             preOrderRec(root.left)
  20.             preOrderRec(root.right)
  22.         # 迭代法
  23.         # 1) 弹出打印
  24.         # 2) 如有右，压入右
  25.         # 3) 如有左，压入左
  26.         def preOrderIter(root):
  27.             if not root: self.res = []
  29.             stack = [root]
  30.             while stack:
  31.                 root = stack.pop()
  32.                 self.res.append(root.val)
  33.                 if root.right: stack.append(root.right)
  34.                 if root.left: stack.append(root.left)
  36.         # preOrderRec(root)
  37.         preOrderIter(root)
  39.     # 后续遍历
  40.     def getPostOrder(self, root):
  41.         def postOrderRec(root):
  42.             if not root:
  43.                 return None
  45.             postOrderRec(root.left)
  46.             postOrderRec(root.right)
  47.             self.res.append(root.val)
  49.         # 迭代法
  50.         # 1) 弹出打印
  51.         # 2) 如有左，压入、左
  52.         # 3) 如有右，压入右
  53.         def postOrderIter(root):
  54.             if not root: self.res = []
  56.             stack = [root]
  57.             while stack:
  58.                 self.res.append(root.val)
  59.                 root = stack.pop()
  60.                 if root.left: stack.append(root.left)
  61.                 if root.right: stack.append(root.right)
  64.         # postOrderRec(root)   
  65.         postOrderIter(root)
  67.     # 中序遍历
  68.     def getInOrder(self, root):
  69.         def inOrderRec(root):
  70.             if not root:
  71.                 return None
  73.             inOrderRec(root.left)
  74.             self.res.append(root.val)
  75.             inOrderRec(root.right)
  77.         # 迭代法
  78.         # 1) 整条左边界入栈
  79.         # 2) 如果 1) 无法进行，弹出打印
  80.         # 3) 右边界入栈
  81.         def inOrderIter(root):
  82.             if not root: self.res = []
  84.             stack = []
  85.             while stack or root:
  86.                 if root:
  87.                     stack.append(root)
  88.                     root = root.left
  89.                 else:
  90.                     node = stack.pop()
  91.                     self.res.append(node.val)
  92.                     root = node.right
  94.         # inOrderRec(root)
  95.         inOrderIter(root)
  98.     # 层序遍历
  99.     def bfs(self, root):
  100.         if not root: self.res = []
  102.         queue = [root]
  103.         while queue:
  104.             nextLayer = []
  105.             for node in queue:
  106.                 self.res.append(node.val)
  107.                 if node.left:
  108.                     nextLayer.append(node.left)
  109.                 if node.right:
  110.                     nextLayer.append(node.right)
  112.             queue = nextLayer
  115. if __name__ == "__main__":
  117.     node1 = TreeNode('A')
  118.     node2 = TreeNode('B')
  119.     node3 = TreeNode('C')
  120.     node4 = TreeNode('D')
  121.     node5 = TreeNode('E')
  122.     node6 = TreeNode('F')
  123.     node7 = TreeNode('G')
  124.     node8 = TreeNode('H')
  125.     node9 = TreeNode('I')
  127.     node1.left = node2
  128.     node1.right = node3
  129.     node2.left = node4
  130.     node2.right = node5
  131.     node3.left = node6
  132.     node3.right = node7 
  133.     node4.left = node8
  134.     node4.right = node9
  136.     s = Solution()
  137.     s.getPreOrder(node1)
  138.     print (s.res) # ['A', 'B', 'D', 'H', 'I', 'E', 'C', 'F', 'G']
  140.     # s.getInOrder(node1)
  141.     # print (s.res) # ['H', 'D', 'I', 'B', 'E', 'A', 'F', 'C', 'G']
  143.     # s.getPostOrder(node1)
  144.     # print (s.res[::-1]) # ['H', 'I', 'D', 'E', 'B', 'F', 'G', 'C', 'A']
  146.     # s.bfs(node1)
  147.     # print (s.res) # ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']

2. Java实现

  1. import java.util.*;
  3. /**
  4.  * @Author dyliang
  5.  * @Date 2020/10/7 21:22
  6.  * @Version 1.0
  7.  */
  8. public class BinaryTree {
  9.     public static void main(String[] args) {
  10.         TreeNode root = new TreeNode(1);
  11.         root.left = new TreeNode(2);
  12.         root.right = new TreeNode(3);
  13.         root.left.left = new TreeNode(4);
  14.         root.left.right = new TreeNode(5);
  15.         root.left.left.left = new TreeNode(8);
  16.         root.left.left.right = new TreeNode(9);
  17.         root.right.left = new TreeNode(6);
  18.         root.right.right = new TreeNode(7);
  20.         System.out.println("---------recursive---------");
  21.         preOrderRecur(root);
  22.         System.out.println();
  23.         System.out.println("---------------------");
  24.         inOrderRecur(root);
  25.         System.out.println();
  26.         System.out.println("---------------------");
  27.         postOrderRecur(root);
  28.         System.out.println();
  29.         System.out.println("---------Iteration---------");
  30.         preOrderIter(root);
  31.         System.out.println();
  32.         System.out.println("---------------------");
  33.         inOrderIter(root);
  34.         System.out.println();
  35.         System.out.println("---------------------");
  36.         postOrderIter(root);
  37.         System.out.println();
  38.         System.out.println("---------------------");
  39.         levelOrder(root);
  41.         /**
  42.          * ---------recursive---------
  43.          * 1 2 4 8 9 5 3 6 7
  44.          * ---------------------
  45.          * 8 4 9 2 5 1 6 3 7
  46.          * ---------------------
  47.          * 8 9 4 5 2 6 7 3 1
  48.          * ---------Iteration---------
  49.          * 1 2 4 8 9 5 3 6 7
  50.          * ---------------------
  51.          * 8 4 9 2 5 1 6 3 7
  52.          * ---------------------
  53.          * 8 9 4 5 2 6 7 3 1
  54.          * ---------------------
  55.          * 1 2 3 4 5 6 7 8 
  56.          */
  58.     }
  59.     public static class TreeNode{
  60.         int val;
  61.         TreeNode left;
  62.         TreeNode right;
  64.         public TreeNode(int val) {
  65.             this.val = val;
  66.         }
  68.         public TreeNode() {
  69.         }
  70.     }
  72.     /**
  73.      * 递归方式的先序遍历
  74.      * @param root
  75.      */
  76.     public static void preOrderRecur(TreeNode root){
  77.         if(root == null){
  78.             return;
  79.         }
  81.         System.out.print(root.val + " ");
  82.         preOrderRecur(root.left);
  83.         preOrderRecur(root.right);
  84.     }
  86.     /**
  87.      * 递归方式的中序遍历
  88.      * @param root
  89.      */
  90.     public static void inOrderRecur(TreeNode root){
  91.         if(root == null){
  92.             return;
  93.         }
  95.         inOrderRecur(root.left);
  96.         System.out.print(root.val + " ");
  97.         inOrderRecur(root.right);
  98.     }
  100.     /**
  101.      * 递归方式的后续遍历
  102.      * @param root
  103.      */
  104.     public static void postOrderRecur(TreeNode root){
  105.         if(root == null){
  106.             return;
  107.         }
  109.         postOrderRecur(root.left);
  110.         postOrderRecur(root.right);
  111.         System.out.print(root.val + " ");
  112.     }
  114.     /**
  115.      * 迭代方式的先序遍历
  116.      * @param root
  117.      */
  118.     public static void preOrderIter(TreeNode root){
  119.         if(root == null){
  120.             return;
  121.         }
  123.         Stack<TreeNode> stack = new Stack<>();
  124.         stack.push(root);
  125.         while(!stack.isEmpty()){
  126.             TreeNode node = stack.pop();
  127.             System.out.print(node.val + " ");
  128.             if(node.right != null){
  129.                 stack.push(node.right);
  130.             }
  131.             if(node.left != null){
  132.                 stack.push(node.left);
  133.             }
  134.         }
  135.     }
  137.     /**
  138.      * 迭代方式的后序遍历
  139.      * @param root
  140.      */
  141.     public static void postOrderIter(TreeNode root){
  142.         if(root == null){
  143.             return;
  144.         }
  146.         Stack<TreeNode> stack = new Stack<>();
  147.         List<Integer> list = new ArrayList<>();
  148.         stack.push(root);
  149.         while(!stack.isEmpty()){
  150.             TreeNode node = stack.pop();
  151.             list.add(node.val);
  152.             if(node.left != null){
  153.                 stack.push(node.left);
  154.             }
  155.             if(node.right != null) {
  156.                 stack.push(node.right);
  157.             }
  158.         }
  160.         Collections.reverse(list);
  161.         for (Integer i : list) {
  162.             System.out.print(i + " ");
  163.         }
  164.     }
  166.     /**
  167.      * 迭代方式的中序遍历
  168.      * @param root
  169.      */
  170.     public static void inOrderIter(TreeNode root){
  171.         if(root == null){
  172.             return;
  173.         }
  175.         Stack<TreeNode> stack = new Stack<>();
  176.         while (!stack.isEmpty() || root != null){
  177.             if(root != null){
  178.                 stack.push(root);
  179.                 root = root.left;
  180.             } else {
  181.                 root = stack.pop();
  182.                 System.out.print(root.val + " ");
  183.                 root = root.right;
  184.             }
  185.         }
  186.     }
  188.     /**
  189.      * 层序遍历
  190.      * @param root
  191.      */
  192.     public static void levelOrder(TreeNode root){
  193.         Queue<TreeNode> queue = new LinkedList<>();
  194.         queue.add(root);
  195.         while (!queue.isEmpty()){
  196.             Queue<TreeNode> next = new LinkedList<>();
  197.             for (TreeNode node : queue) {
  198.                 if(node != null){
  199.                     System.out.print(node.val + " ");
  200.                     if(root.left != null){
  201.                         next.add(node.left);
  202.                     }
  203.                     if(root.right != null){
  204.                         next.add(node.right);
  205.                     }
  206.                 }else{
  207.                     return;
  208.                 }
  209.             }
  210.             queue = next;
  211.         }
  212.     }
  213. }