二叉树的Java实现

阳光穿透心脏的1/2处 2022-07-24 03:16 137阅读 0赞

以如图所示的二叉树为例创建二叉树并实现二叉树的遍历（先序遍历、中序遍历、后序遍历）  
![二叉树][20160511205031158]

/** * 部分代码来自于http://ocaicai.iteye.com/blog/1047397 */
    public class BinaryTree { 
    
        /** * 内部类，Node用于存储数据 * @author */
        private static class Node{ 
            Node leftChild;  
            Node rightChild;  
            int data;  
    
            Node(int Data) {  
                leftChild = null;  
                rightChild = null;  
                this.data = Data;  
            }
        }
    
        /** * 创建一个二叉树 * @return */
        private static Node createBinaryTree(){
            Node node1=new Node(1);
            Node node2=new Node(2);
            Node node3=new Node(3);
            Node node4=new Node(4);
    
            node1.leftChild=node2;
            node1.rightChild=node3;
            node3.leftChild=node4;
    
            return node1;
        }
    
        /** * 先序遍历 * @param node * 结果应该是 1 2 3 4 */
        private static void preOrderTraversal(Node node){
            if(node==null){
                return;
            }
            System.out.println(node.data);
            preOrderTraversal(node.leftChild);
            preOrderTraversal(node.rightChild);
        }
    
        /** * 中序遍历 * @param node * 结果应该是 2 1 4 3 */
        private static void inOrderTraversal(Node node){
            if(node==null){
                return;
            }
            inOrderTraversal(node.leftChild);
            System.out.println(node.data);
            inOrderTraversal(node.rightChild);
        }
    
        /** * 后序遍历 * @param node * 结果应该是 2 4 3 1 */
        private static void postOrderTraverse(Node node){
            if(node==null){
                return;
            }
            inOrderTraversal(node.leftChild);
            inOrderTraversal(node.rightChild);
            System.out.println(node.data);
        }
    
        public static void main(String[] args) {
            Node node=createBinaryTree();
            preOrderTraversal(node);
            inOrderTraversal(node);
            postOrderTraverse(node);
        }
    }

[20160511205031158]: /images/20220722/c9265fc0749b43d3817a9563af0cab80.png