java构建二叉树和二叉树的遍历-白红宇

java构建二叉树和二叉树的遍历

阅读量：6291 次

发布时间：2019-06-22

本文共 5322 字，大约阅读时间需要 17 分钟。

2  public class BinaryTreeNode { 3     private int data; 4     private BinaryTreeNode left; 5     private BinaryTreeNode right; 6      7     public BinaryTreeNode() {} 8  9     public BinaryTreeNode(int data, BinaryTreeNode left, BinaryTreeNode right) {10         super();11         this.data = data;12         this.left = left;13         this.right = right;14     }15 16     public int getData() {17         return data;18     }19 20     public void setData(int data) {21         this.data = data;22     }23 24     public BinaryTreeNode getLeft() {25         return left;26     }27 28     public void setLeft(BinaryTreeNode left) {29         this.left = left;30     }31 32     public BinaryTreeNode getRight() {33         return right;34     }35 36     public void setRight(BinaryTreeNode right) {37         this.right = right;38     }39 }

前序递归遍历算法：访问根结点-->递归遍历根结点的左子树-->递归遍历根结点的右子树

中序递归遍历算法：递归遍历根结点的左子树-->访问根结点-->递归遍历根结点的右子树

后序递归遍历算法：递归遍历根结点的左子树-->递归遍历根结点的右子树-->访问根结点

1 import com.ccut.aaron.stack.LinkedStack;  2   3 public class BinaryTree {  4     //前序遍历递归的方式  5     public void preOrder(BinaryTreeNode root){  6         if(null!=root){  7             System.out.print(root.getData()+"\t");  8             preOrder(root.getLeft());  9             preOrder(root.getRight()); 10         } 11     } 12      13     //前序遍历非递归的方式 14     public void preOrderNonRecursive(BinaryTreeNode root){ 15         Stack
     
       stack=new Stack
      
       (); 16         while(true){ 17             while(root!=null){ 18                 System.out.print(root.getData()+"\t"); 19                 stack.push(root); 20                 root=root.getLeft(); 21             } 22             if(stack.isEmpty()) break; 23             root=stack.pop(); 24             root=root.getRight(); 25         } 26     } 27      28     //中序遍历采用递归的方式 29     public void inOrder(BinaryTreeNode root){ 30         if(null!=root){ 31             inOrder(root.getLeft()); 32             System.out.print(root.getData()+"\t"); 33             inOrder(root.getRight()); 34         } 35     } 36      37     //中序遍历采用非递归的方式 38     public void inOrderNonRecursive(BinaryTreeNode root){ 39         Stack
       
         stack=new Stack
        
         (); 40         while(true){ 41             while(root!=null){ 42                 stack.push(root); 43                 root=root.getLeft(); 44             } 45             if(stack.isEmpty())break; 46             root=stack.pop(); 47             System.out.print(root.getData()+"\t"); 48             root=root.getRight(); 49         } 50     } 51      52     //后序遍历采用递归的方式 53     public void postOrder(BinaryTreeNode root){ 54         if(root!=null){ 55             postOrder(root.getLeft()); 56             postOrder(root.getRight()); 57             System.out.print(root.getData()+"\t"); 58         } 59     } 60      61     //后序遍历采用非递归的方式 62     public void postOrderNonRecursive(BinaryTreeNode root){ 63         Stack
         
           stack=new Stack
          
           (); 64 while(true){ 65 if(root!=null){ 66 stack.push(root); 67 root=root.getLeft(); 68 }else{ 69 if(stack.isEmpty()) return; 70 71 if(null==stack.lastElement().getRight()){ 72 root=stack.pop(); 73 System.out.print(root.getData()+"\t"); 74 while(root==stack.lastElement().getRight()){ 75 System.out.print(stack.lastElement().getData()+"\t"); 76 root=stack.pop(); 77 if(stack.isEmpty()){ 78 break; 79 } 80 } 81 } 82 83 if(!stack.isEmpty()) 84 root=stack.lastElement().getRight(); 85 else 86 root=null; 87 } 88 } 89 } 90 91 //层序遍历 92 public void levelOrder(BinaryTreeNode root){ 93 BinaryTreeNode temp; 94 Queue
           
             queue=new LinkedList
            
             (); 95 queue.offer(root); 96 while(!queue.isEmpty()){ 97 temp=queue.poll(); 98 System.out.print(temp.getData()+"\t"); 99 if(null!=temp.getLeft()) 100 queue.offer(temp.getLeft());101 if(null!=temp.getRight()){102 queue.offer(temp.getRight());103 }104 }105 }106 107 public static void main(String[] args) {108 BinaryTreeNode node10=new BinaryTreeNode(10,null,null);109 BinaryTreeNode node8=new BinaryTreeNode(8,null,null);110 BinaryTreeNode node9=new BinaryTreeNode(9,null,node10);111 BinaryTreeNode node4=new BinaryTreeNode(4,null,null);112 BinaryTreeNode node5=new BinaryTreeNode(5,node8,node9);113 BinaryTreeNode node6=new BinaryTreeNode(6,null,null);114 BinaryTreeNode node7=new BinaryTreeNode(7,null,null);115 BinaryTreeNode node2=new BinaryTreeNode(2,node4,node5);116 BinaryTreeNode node3=new BinaryTreeNode(3,node6,node7);117 BinaryTreeNode node1=new BinaryTreeNode(1,node2,node3);118 119 BinaryTree tree=new BinaryTree();120 //采用递归的方式进行遍历121 System.out.println("-----前序遍历------");122 tree.preOrder(node1);123 System.out.println();124 //采用非递归的方式遍历125 tree.preOrderNonRecursive(node1);126 System.out.println();127 128 129 //采用递归的方式进行遍历130 System.out.println("-----中序遍历------");131 tree.inOrder(node1);132 System.out.println();133 //采用非递归的方式遍历134 tree.inOrderNonRecursive(node1);135 System.out.println();136 137 //采用递归的方式进行遍历138 System.out.println("-----后序遍历------");139 tree.postOrder(node1);140 System.out.println();141 //采用非递归的方式遍历142 tree.postOrderNonRecursive(node1);143 System.out.println();144 145 //采用递归的方式进行遍历146 System.out.println("-----层序遍历------");147 tree.levelOrder(node1);148 System.out.println();149 }150 }