首页 > 编程语言 > 详细

排序二叉树的基本操作

时间:2017-02-02 22:47:15      阅读:297      评论:0      收藏:0      [点我收藏+]

描述

二叉树的构建、插入新的结点、树的先中后序以及层序四种遍历

 

代码

import java.util.LinkedList;
import java.util.Queue;

class Node{
    public int data;
    public Node left;
    public Node right;
    public Node(int data){
        this.data=data;
        this.left=null;
        this.right=null;
    }
}

public class BinaryTree {
    private Node root;
    public BinaryTree(){
        root=null;
    }
    /*
    * 插入到排序二叉树
    * */
    public void insert(int data){
        Node newNode=new Node(data);
        if(root==null){
            root=newNode;
            return;
        }
        Node node=root;
        Node parent;
        while(true){
            parent=node;
            if(data<node.data){
                node=node.left;
                if(node==null){
                    parent.left=newNode;
                    return;
                }
            }else{
                node=node.right;
                if(node==null){
                    parent.right=newNode;
                    return;
                }
            }
        }
    }
    /*
    * 将数值输入构建二叉树
    * */
    public void buildTree(int[] data){
        for(int i=0;i<data.length;i++){
            insert(data[i]);
        }
    }
    /*
    * 先序遍历
    * */
    public void preOrder(){
        preOrder(root);
    }
    public void preOrder(Node node){
        if(node==null) return;
        System.out.print(node.data+" ");
        preOrder(node.left);
        preOrder(node.right);
    }

    /*
    * 中序遍历
    * */
    public void inOrder(){
        inOrder(root);
    }
    public void inOrder(Node node){
        if(node==null) return;
        preOrder(node.left);
        System.out.print(node.data+" ");
        preOrder(node.right);
    }

    /*
    * 后序遍历
    * */
    public void postOrder(){
        postOrder(root);
    }
    public void postOrder(Node node){
        if(node==null) return;
        preOrder(node.left);
        preOrder(node.right);
        System.out.print(node.data+" ");
    }
    /*
    * 层序遍历
    * */
    public void layerTranverse(){
        Node node = root;
        Queue<Node> queque=new LinkedList<Node>();
        queque.add(root);
        while(!queque.isEmpty()){
            node=queque.poll();
            System.out.print(node.data+" ");
            if(node.left!=null) queque.add(node.left);
            if(node.right!=null) queque.add(node.right);
        }
    }

    public static void main(String[] args) {
        BinaryTree bitree=new BinaryTree();
        int[] data={2,8,7,4,9,3,1,6,7,5};
        bitree.buildTree(data);
        System.out.print("二叉树的先序遍历:");
        bitree.preOrder();
        System.out.println();
        System.out.print("二叉树的中序遍历:");
        bitree.inOrder();
        System.out.println();
        System.out.print("二叉树的后序遍历:");
        bitree.postOrder();
        System.out.println();
        System.out.print("二叉树的层序遍历:");
        bitree.layerTranverse();
        System.out.println();
    }
}

 

排序二叉树的基本操作

原文:http://www.cnblogs.com/zadomn0920/p/6361730.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!