ch6_e6_30.java

《java语言与面向对象程序设计题解及实验指导》源代码

public class ch6_e6_30  
{
    public static void main(String args[])
    {
        int[] dataIn = {49,45,80,11,18,106,55,251,91};//欲放入二叉树中的数据
        BinaryTree searchTree = new BinaryTree(dataIn[0]);  //创建二叉树

        for(int i=1;i<dataIn.length;i++)
            searchTree.insertToTree(dataIn[i]); //将数据加入到二叉树中
        System.out.print("按层遍历结果：");
        searchTree.layerOrderReview();
    }
}


class BinaryTree        //二叉树类
{
    TreeNode m_RootNode;    //根节点

    BinaryTree(int rootdata)//构造函数，创建二叉树及其根节点
    {
            m_RootNode = new TreeNode(rootdata);
    }
    void insertToTree(int newdata)//将一个新数据插入到二叉树中
    {
        m_RootNode.insertNode(newdata);
    }
    void layerOrderReview() //按层遍历
    {
        MyQueue queue = new MyQueue();
        TreeNode temp;
        
        queue.enQueue(m_RootNode);
        while(!queue.isEmpty())
        {
            temp = (TreeNode)(queue.deQueue());
            System.out.print(temp.getData() + "\t");
            if(temp.getLeftPoint()!=null)
                queue.enQueue(temp.getLeftPoint());
            if(temp.getRightPoint()!=null)
                queue.enQueue(temp.getRightPoint());
        }
    }
}

class TreeNode//二叉树的节点类
{
    TreeNode m_LeftPoint;  //左指针
    TreeNode m_RightPoint; //右指针
    private int m_Data;    //节点中的数据

    TreeNode(int newdata)//构造函数
    {
        m_Data = newdata;
        m_LeftPoint = null;
        m_RightPoint = null;
    }
    int getData()
    {
        return m_Data;
    }
    void setData(int newdata)
    {
        m_Data = newdata;
    }
    TreeNode getLeftPoint()
    {
        return m_LeftPoint;
    }
    TreeNode getRightPoint()
    {
        return m_RightPoint;
    }
    void insertNode(int newdata)
    {//使用递归方法将一个新节点插入在以当前节点为根节点的二叉树上
        if(newdata>=getData())
        {//将大于等于当前数据的新节点安排在右子树中
            if(m_RightPoint == null)
                m_RightPoint = new TreeNode(newdata);//递归头
            else
                m_RightPoint.insertNode(newdata);//递归调用
        }
        else
        {//将小于当前数据的新节点安排在左子树中
            if(m_LeftPoint == null)
                m_LeftPoint = new TreeNode(newdata);//递归头
            else
                m_LeftPoint.insertNode(newdata);//递归调用
        }
    }
}

class MyQueue  //定义队列类
{
    private LinkList myData;
    
    MyQueue()
    {
        myData = new LinkList();
    }
    
    void enQueue(Object data)
    {
        myData.insertAtEnd(data);
    }
    Object deQueue()
    {
        Node temp = myData.getFirstNode();

        if(temp==null)
            return null;
            
        Object obj = temp.getData();
        
        myData.setFirstNode(temp.getNext());
        temp = null;
        return obj;
    }
    boolean isEmpty()
    {
        if(myData.getFirstNode()==null)
            return true;
        else
            return false;
    }
}

class LinkList              //定义链表类
{
    Node m_FirstNode;       //链表中的第一个节点

    LinkList()          //构造函数1：建立空链表
    {
        m_FirstNode = null;
    }
    LinkList(Object data)      //构造函数2：建立只有一个节点的链表
    {
        m_FirstNode = new Node(data);
    }
    Node getFirstNode()
    {
        return m_FirstNode;
    }
    void setFirstNode(Node newHead)
    {
        m_FirstNode = newHead;
    }
    String visitAllNode()   //遍历链表的每个节点，将所有数据串成一个字符串
    {
        Node next = m_FirstNode;    //从第一个节点开始
        String s = "";
        while(next!=null)           //直到最后一个节点
        {
            s = s + next.getData() + ";  ";
            next = next.getNext();  //next指向下一个节点
        }
        return s;
    }
    void insertAtBegin(Object data)    //将数据data的节点插入在整个链表的前面
    {
        if(m_FirstNode == null)         //对于空链表，直接插入
            m_FirstNode = new Node(data);
        else            //把新节点插在第一个节点前面，并指向原来的第一节点
            m_FirstNode = new Node(data,m_FirstNode);
    }
    void insertAtEnd(Object data)   //将数据data节点插入在整个链表的最后面
    {
        Node next = m_FirstNode;
        
        if(next == null)
            m_FirstNode = new Node(data);
        else
        {
            while(next.getNext()!=null)
                next = next.getNext();
            next.setNext(new Node(data));
        }
    }
    void removeAll()                        //删除所有的节点，令链表为空
    {
        m_FirstNode = null;
    }
}//链表类定义结束

class Node 
{
    private Object m_Data;  //节点中保存的数据
    private Node m_Next;    //节点中的指针属性，指向下一个Node对象的对象引用

    Node(Object data)          //构造函数
    {
        m_Data = data;
        m_Next = null;
    }
    Node(Object data, Node next)
    {
        m_Data = data;
        m_Next = next;
    }
    void setData(Object data)  //修改节点中的数据
    {
        m_Data = data;
    }
    Object getData()           //获得节点中的数据
    {
        return m_Data;
    }
    void setNext(Node next)//指定指针指向的Node对象引用
    {
        m_Next = next;
    }
    Node getNext()      //获得节点中的指针指向的对象引用
    {
        return m_Next;
    }
}