二叉树遍历(Java实现)

时间:2021-05-28 10:09:21

二叉树遍历(Java实现) 

 

主要是二叉树的遍历,包括递归遍历和非递归遍历



  1. import java.util.ArrayDeque;  
  2. import java.util.ArrayList;  
  3. import java.util.List;  
  4. import java.util.Queue;  
  5.   
  6. public class BinaryNode<T> {  
  7.     /**  
  8.      * 泛型BinaryNode类  
  9.      */  
  10.     public T item;  
  11.       
  12.     public BinaryNode<T> left,right;//左右子树  
  13.       
  14.     public BinaryNode(T item)  
  15.     {  
  16.         this.item = item;  
  17.         left = right = null;  
  18.     }     
  19.     public BinaryNode (T item, BinaryNode<T> left, BinaryNode<T> right)  
  20.     {  
  21.         this.item = item;  
  22.         this.left = left;  
  23.         this.right = right;  
  24.     }  
  25.   
  26.     public T getNodeValue() {  
  27.         return item;  
  28.     }  
  29.     public void setNodeValue(T item) {  
  30.         this.item = item;  
  31.     }  
  32.     public BinaryNode<T> getLeft() {  
  33.         return left;  
  34.     }  
  35.     public void setLeft(BinaryNode<T> left) {  
  36.         this.left = left;  
  37.     }  
  38.     public BinaryNode<T> getRight() {  
  39.         return right;  
  40.     }  
  41.     public void setRight(BinaryNode<T> right) {  
  42.         this.right = right;  
  43.     }  
  44.       
  45.     //判断是否为叶子  
  46.     public boolean isLeaf(){  
  47.         return (left==null)&&(right==null);  
  48.     }  
  49.       
  50.     //前序遍历二叉树(递归)  
  51.     public List<BinaryNode<T>> toStringPreorder(BinaryNode<T> node){  
  52.         List<BinaryNode<T>list=new ArrayList<BinaryNode<T>>();  
  53.         list.add(node);  
  54.         if (node.left!=null) {  
  55.             list.addAll(toStringPreorder(node.left));  
  56.         }  
  57.         if (node.right!=null) {  
  58.             list.addAll(toStringPreorder(node.right));  
  59.         }  
  60.         return list;  
  61.     }  
  62.     //前序遍历二叉树(非递归)  
  63.     public List<BinaryNode<T>> toStringPreorderNoRec(BinaryNode<T> node){  
  64.         List<BinaryNode<T>list=new ArrayList<BinaryNode<T>>();  
  65.         ArrayDeque<BinaryNode<T>stack=new ArrayDeque<BinaryNode<T>>();  
  66.         while ((node!=null)||!stack.isEmpty()) {  
  67.             if (node!=null) {  
  68.                 list.add(node);  
  69.                 stack.push(node);  
  70.                 node=node.left;  
  71.             } else {  
  72.                 node=stack.peek();            
  73.                 stack.pop();  
  74.                 node=node.right;  
  75.             }  
  76.         }         
  77.         return list;  
  78.     }  
  79.       
  80.     //中序遍历二叉树  
  81.     public List<BinaryNode<T>> toStringInorder(BinaryNode<T> node){  
  82.         List<BinaryNode<T>list=new ArrayList<BinaryNode<T>>();  
  83.         if (node.left!=null) {  
  84.             list.addAll(toStringPreorder(node.left));  
  85.         }  
  86.         list.add(node);  
  87.         if (node.right!=null) {  
  88.             list.addAll(toStringPreorder(node.right));  
  89.         }  
  90.         return list;  
  91.     }  
  92.     //中序遍历二叉树(非递归)  
  93.     public List<BinaryNode<T>> toStringInorderNoRec(BinaryNode<T> node){  
  94.         List<BinaryNode<T>list=new ArrayList<BinaryNode<T>>();  
  95.         ArrayDeque<BinaryNode<T>stack=new ArrayDeque<BinaryNode<T>>();  
  96.         while ((node!=null)||!stack.isEmpty()) {  
  97.             if (node!=null) {                 
  98.                 stack.push(node);  
  99.                 node=node.left;  
  100.             } else {  
  101.                 node=stack.peek();  
  102.                 list.add(node);  
  103.                 stack.pop();  
  104.                 node=node.right;  
  105.             }  
  106.         }         
  107.         return list;  
  108.     }  
  109.       
  110.     //后序遍历二叉树  
  111.     public String toStringPostorder(){  
  112.         String result="";  
  113.         if (left!=null) {  
  114.             result += left.toStringPostorder();  
  115.         }         
  116.         if (right!=null) {  
  117.             result += right.toStringPostorder();  
  118.         }  
  119.         result += item;  
  120.         return result;  
  121.     }  
  122.     //后序遍历二叉树(非递归)  
  123.     /**  
  124.      * 先遍历树的逆后序遍历(根、右、左),在翻转逆后序遍历就是后序遍历二叉树(左、右、根)  
  125.      * @return result栈  
  126.      */  
  127.     public ArrayDeque<BinaryNode<T>> toStringPostorderNoRec(BinaryNode<T> node){  
  128.         ArrayDeque<BinaryNode<T>stack=new ArrayDeque<BinaryNode<T>>();  
  129.         ArrayDeque<BinaryNode<T>result=new ArrayDeque<BinaryNode<T>>();  
  130.         while ((node!=null)||!stack.isEmpty()) {  
  131.             if (node!=null) {  
  132.                 result.push(node);  
  133.                 stack.push(node);  
  134.                 node=node.right;  
  135.             } else {  
  136.                 node=stack.peek();  
  137.                 stack.pop();  
  138.                 node=node.left;  
  139.             }  
  140.         }         
  141.         return result;  
  142.     }  
  143.     //后序遍历二叉树2(非递归)  
  144.     /**  
  145.      * 要保证根结点在左孩子和右孩子访问之后才能访问,因此对于任一结点P,先将其入栈。如果P不存在左孩子和右孩子,则可以直接访问它;  
  146.      * 或者P存在左孩子或者右孩子,但是其左孩子和右孩子都已被访问过了,则同样可以直接访问该结点。若非上述两种情况,  
  147.      * 则将P的右孩子和左孩子依次入栈,这样就保证了每次取栈顶元素的时候,左孩子在右孩子前面被访问,左孩子和右孩子都在根结点前面被访问。  
  148.      * @return result栈  
  149.      */  
  150.     public ArrayList<BinaryNode<T>> toStringPostorderNoRec2(BinaryNode<T> root){  
  151.         ArrayDeque<BinaryNode<T>stack=new ArrayDeque<BinaryNode<T>>();  
  152.         ArrayList<BinaryNode<T>result=new ArrayList<BinaryNode<T>>();  
  153.         BinaryNode<T> curr;//当前栈顶指针  
  154.         BinaryNode<Tpre=null;//前一次访问节点  
  155.         stack.push(root);  
  156.         while (!stack.isEmpty()) {  
  157.             curr=stack.peek();  
  158.             if ((curr.left==null&&curr.right==null)||(pre!=null&&(pre==curr.left||pre==curr.right))) {  
  159.                 result.add(curr);//输出结果  
  160.                 stack.pop();  
  161.                 pre=curr;  
  162.             } else {  
  163.                 if (curr.right!=null) {  
  164.                     stack.push(curr.right);  
  165.                 }   
  166.                 if (curr.left!=null) {  
  167.                     stack.push(curr.left);  
  168.                 }  
  169.             }  
  170.         }         
  171.         return result;  
  172.     }  
  173.       
  174.     //层序遍历(广度优先遍历)  
  175.     public List<BinaryNode<T>> toStringLevelOrder(){  
  176.         List<BinaryNode<T>list=new ArrayList<BinaryNode<T>>();  
  177.         Queue<BinaryNode<T>queue=new ArrayDeque<BinaryNode<T>>();  
  178.         queue.offer(this);//root  
  179.         while (!(queue.isEmpty())) {  
  180.             list.add(queue.peek());  
  181.             BinaryNode<Tnode=queue.poll();            
  182.             if (node.left != null) {  
  183.                 queue.offer(node.left);  
  184.             }  
  185.             if (node.right != null) {  
  186.                 queue.offer(node.right);  
  187.             }  
  188.         }  
  189.         return list;  
  190.     }  
  191.       
  192. }