雪天，荆棘丛中，跪求，帮帮忙。

Question

1.设二叉树用链表存储表示，每个结点分为3个域：leftchild,data,rightchild.
请用java语言写一个程序，给出该二叉树的定义类（仅写出必要的数据成员和成员函数），并写出交换该二叉树的的每个结点的的左子女和右子女的算法。（假设data域为int型）菜鸟初学，考试题，请大家帮帮忙。祝大家心想事成，万事如意。

Answer 1

public class BinaryTreeNode //这是一个通用的结点对象
{ 
//定义
    BinaryTreeNode leftChild;
BinaryTreeNode rightSibling;
int data;  public BinaryTreeNode()
  {
   this(null,null,null);
  }  public BinaryTreeNode(int theData)
  {
   this(theData,null,null);
  }  public BinaryTreeNode(int theData,BinaryTreeNode left, BinaryTreeNode right)
  {
   data=theData;
   leftChild=left;
   rightSibling=right;
  }  public void setLeftChild(BinaryTreeNode newNode)//设置左孩子结点。
  {
    leftChild=newNode;
  }  public void setRightSibling(BinaryTreeNode newNode)//设置右兄弟结点。
  {
 rightSibling=newNode;
  }  public void setData(TagObject newData)//设置该结点的数值。
  {
    data=newData;
  }
  public int getData()//得到结点的值。
  {
     return data;
  }  public BinaryTreeNode getLeftChild() //返回左孩子结点
  {
     return leftChild;
  }   public BinaryTreeNode getRightSibling() //得到右兄弟结点
  {
     return rightSibling;
  }
}

Answer 2

public   void   setData(int newData)//设置该结点的数值。
    {
        data=newData;
    } 
---------------------------------------------------
不好意思，写错了。是int类型。

Answer 3

public class BinaryTree
{
//定义根结点和当前结点。
    private BinaryTreeNode root;
    private BinaryTreeNode cursor;
    BinaryTreeNode leftChild;
BinaryTreeNode rightSibling;  public BinaryTree() //创建一棵以结点newNode为根的树。
  {
     BinaryTreeNode newNode=new BinaryTreeNode();
  root=newNode;
  cursor=root;
  }  public BinaryTreeNode setRoot(BinaryTreeNode newNode) 
  {
   if(root!=null)
          root=newNode;
   return root;
  }  public BinaryTreeNode getRoot() //求树的根结点
  {
  if(root!=null)
     return root;
  return null;
  }  public boolean hasleftChild(BinaryTreeNode ownNode) // 判断结点ownNode是否有左孩子
  {
     return ownNode.getLeftChild()!=null;
  }  public boolean hasRightSibling(BinaryTreeNode ownNode) // 判断结点ownNode是否有右兄弟
  {
    return ownNode.getRightSibling()!=null;
  }
   public void preOrder(BinaryTreeNode localRoot) //遍历树
   {
   if(localRoot!=null)
{
localRoot.data.display();
preOrder(localRoot.leftChild);
preOrder(localRoot.rightSibling);
}
   }
   public  void clearBiTree() // 清空二叉树
  {
       root=null;
  }
}

Answer 4

 import   java.sql.*;   
    
    
    
  class   AVLNode   
  {   
      AVLNode(Comparable   theElement)   {   
          this(theElement,   null,   null);   
      }   
    
      AVLNode(Comparable   theElement,   AVLNode   lt,   AVLNode   rt)   {   
          element   =   theElement;   
          left   =   lt;   
          right   =   rt;   
          height   =   0;   
      }   
      public   AVLNode()   {   
      }   
    
      public   AVLNode(Connection   conn)   
      {   
    
      }   
    
      Comparable   element;   
      AVLNode   left;   
      AVLNode   right;   
      int   height;   
  }   
  public   class   AVLTree   
  {   
      public   Comparable   find(Comparable   ID)   {   
          return   elementAt(find(ID,   root));   
      }   
    
      public   Comparable   findMin()   {   
          return   elementAt(findMin(root));   
      }   
    
      public   Comparable   findMax()   {   
          return   elementAt(findMax(root));   
      }   
    
      public   Comparable   removeMax()   {   
          return   elementAt(removeMax(root));   
      }   
    
    
    
      public   void   insert(Comparable   ID)   {   
          root   =   insert(ID,   root);   
      }   
    
      public   void   remove(Comparable   ID)   {   
          root   =   remove(ID,   root);   
      }   
    
      private   AVLNode   root;   
      private   Comparable   elementAt(AVLNode   t)   {   
          return   t   ==   null   ?   null   :   t.element;   
      }   
    
      private   static   AVLNode   find(Comparable   ID,   AVLNode   t)   {   
          if   (t   ==   null)   
              return   null;   
          if   (ID.compareTo(t.element)   <   0)   
              return   find(ID,   t.left);   
          else   if   (ID.compareTo(t.element)   >   0)   
              return   find(ID,   t.right);   
          else   
              System.out.println(ID);   
          return   t;   
      }   
    
      private   static   AVLNode   findMin(AVLNode   t)   {   
          if   (t   ==   null)   
              return   null;   
          else   if   (t.left   ==   null)   
              return   t;   
          return   findMin(t.left);   
      }   
    
      private   static   AVLNode   findMax(AVLNode   t)   {   
          if   (t   ==   null)   
              return   null;   
          else   if   (t.right   ==   null)   
              return   t;   
          return   findMax(t.right);   
      }   
    
      private   static   AVLNode   removeMax(AVLNode   t)   {   
          if(t.right!=null)   
              t=removeMax(t.right);   
          else   
              t=t.left;   
          return   t;   
      }   
    
    
    
      private   static   int   height(AVLNode   t)   {   
          return   t   ==   null   ?   -1   :   t.height;   
      }   
    
      private   static   AVLNode   insert(Comparable   ID,   AVLNode   t)   {   
          if   (t   ==   null)   
              t   =   new   AVLNode(ID,   null,   null);   
          else   if   (ID.compareTo(t.element)   <   0)   {   
              t.left   =   insert(ID,   t.left);   
              if   (height(t.left)   -   height(t.right)   ==   2)   
                  if   (ID.compareTo(t.left.element)   <   0)   
                      t   =   rotateWithLeftChild(t);   
              else   
                  t   =   doubleWithLeftChild(t);   
          }   
          else   if   (ID.compareTo(t.element)   >   0)   {   
              t.right   =   insert(ID,   t.right);   
              if   (height(t.right)   -   height(t.left)   ==   2)   
                  if   (ID.compareTo(t.right.element)   >   0)   
                      t   =   rotateWithRightChild(t);   
              else   
                  t   =   doubleWithRightChild(t);   
          }   
          return   t;   
      }   
    
      private   static   AVLNode   rotateWithLeftChild(AVLNode   k2)   {   
          AVLNode   k1   =   k2.left;   
          k2.left   =   k1.right;   
          k1.right   =   k2;   
          return   k1;   
      }   
      private   static   AVLNode   rotateWithRightChild(AVLNode   k1)   
              {AVLNode   k2=k1.right;   
      k1.right=k2.left;   
      k2.left=k1;   
      return   k2;   
      }   
      private   static   AVLNode   doubleWithLeftChild(AVLNode   k3)   
              {k3.left=rotateWithRightChild(k3.left);   
      return   rotateWithLeftChild(k3);   
      }   
      private   static   AVLNode   doubleWithRightChild(AVLNode   k3)   
              {k3.right=rotateWithLeftChild(k3.right);   
      return   rotateWithRightChild(k3);   
      }   
      private   static   AVLNode   remove(Comparable   ID,   AVLNode   t)   {   
          if   (t   ==   null)   
              return   t;   
          else   if   (ID.compareTo(t.element)   <   0)   {   
              t.left   =   remove(ID,   t.left);   
              if   (height(t.right)   -   height(t.left)   ==   2)   
                  if   (height(t.right.left)   -   height(t.right.right)   ==   1)   
                      t   =   doubleWithRightChild(t);   
              else   
                  t   =   rotateWithRightChild(t);   
          }   
          else   if   (ID.compareTo(t.element)   >   0)   {   
              t.right   =   remove(ID,   t.right);   
              if   (height(t.left)   -   height(t.right)   ==   2)   
                  if   (height(t.left.right)   -   height(t.left.left)   ==   1)   
                      t   =   doubleWithLeftChild(t);   
              else   
                  t   =   rotateWithLeftChild(t);   
          }   
          else   if(t.left!=null&&t.right!=null)   
          {   
              t.element=findMax(t.left).element;   
              t.left=removeMax(t.left);   
          }   
          else   
              t=(t.left!=null)?t.left:t.right;   
          return   t;   
      }   
      private   static   void   inOrder(AVLNode   root)   {   
          if   (root   !=   null)   
          {   
              inOrder(root.left);   
              System.out.print(root.element);   
              inOrder(root.right);   
          }   
      }   
    
    
      public   void   save(Connection   conn   )   
      {   
    
      }   
      public   static   void   main(String[]   args)   throws   Exception   
      {java.util.Date   date1=new   java.util.Date();   
          String   ID[]={"46","15","20","35","28","58","18","50","54","60"};   
          AVLNode   root   =   new   AVLNode();   
          root.element=ID[0];   
          for(int   i=0;i<10;i++)   
          {   
              insert(ID[i],root);   
          }   
          inOrder(root);   
          find("15",root);   
          remove("20",root);   
          inOrder(root);   
            remove("46",root);   
            inOrder(root);   
        }   
  }   
这是一个平衡二叉树

Answer 5

import       java.sql.*;         
        
    class       AVLNode       
    {       
            AVLNode(Comparable       theElement)       {       
                    this(theElement,       null,       null);       
            }       
        
            AVLNode(Comparable       theElement,       AVLNode       lt,       AVLNode       rt)       {       
                    element       =       theElement;       
                    left       =       lt;       
                    right       =       rt;       
                    height       =       0;       
            }       
            public       AVLNode()       {      
            }       
        
            public       AVLNode(Connection       conn)       
            {       
        
            }       
        
            Comparable       element;       
            AVLNode       left;       
            AVLNode       right;       
            int       height;       
    }       
    public       class       AVLTree       
    {       
            public       Comparable       find(Comparable       ID)       {       
                    return       elementAt(find(ID,       root));       
            }       
        
            public       Comparable       findMin()       {       
                    return       elementAt(findMin(root));       
            }       
        
            public       Comparable       findMax()       {       
                    return       elementAt(findMax(root));       
            }       
        
            public       Comparable       removeMax()       {       
                    return       elementAt(removeMax(root));       
            }       
        
        
        
            public       void       insert(Comparable       ID)       {       
                    root       =       insert(ID,       root);       
            }       
        
            public       void       remove(Comparable       ID)       {       
                    root       =       remove(ID,       root);       
            }       
        
            private       AVLNode       root;       
            private       Comparable       elementAt(AVLNode       t)       {       
                    return       t       ==       null       ?       null       :       t.element;       
            }       
        
            private       static       AVLNode       find(Comparable       ID,       AVLNode       t)       {       
                    if       (t       ==       null)       
                            return       null;       
                    if       (ID.compareTo(t.element)       <       0)       
                            return       find(ID,       t.left);       
                    else       if       (ID.compareTo(t.element)       >       0)       
                            return       find(ID,       t.right);       
                    else       
                            System.out.println(ID);       
                    return       t;       
            }       
        
            private       static       AVLNode       findMin(AVLNode       t)       {       
                    if       (t       ==       null)       
                            return       null;       
                    else       if       (t.left       ==       null)       
                            return       t;       
                    return       findMin(t.left);       
            }       
        
            private       static       AVLNode       findMax(AVLNode       t)       {       
                    if       (t       ==       null)       
                            return       null;       
                    else       if       (t.right       ==       null)       
                            return       t;       
                    return       findMax(t.right);       
            }       
        
            private       static       AVLNode       removeMax(AVLNode       t)       {       
                    if(t.right!=null)       
                            t=removeMax(t.right);       
                    else       
                            t=t.left;       
                    return       t;       
            }       
        
        
        
            private       static       int       height(AVLNode       t)       {       
                    return       t       ==       null       ?       -1       :       t.height;       
            }       
        
            private       static       AVLNode       insert(Comparable       ID,       AVLNode       t)       {       
                    if       (t       ==       null)       
                            t       =       new       AVLNode(ID,       null,       null);       
                    else       if       (ID.compareTo(t.element)       <       0)       {       
                            t.left       =       insert(ID,       t.left);       
                            if       (height(t.left)       -       height(t.right)       ==       2)       
                                    if       (ID.compareTo(t.left.element)       <       0)       
                                            t       =       rotateWithLeftChild(t);       
                            else       
                                    t       =       doubleWithLeftChild(t);       
                    }       
                    else       if       (ID.compareTo(t.element)       >       0)       {       
                            t.right       =       insert(ID,       t.right);       
                            if       (height(t.right)       -       height(t.left)       ==       2)       
                                    if       (ID.compareTo(t.right.element)       >       0)       
                                            t       =       rotateWithRightChild(t);       
                            else       
                                    t       =       doubleWithRightChild(t);       
                    }       
                    return       t;       
            }       
        
            private       static       AVLNode       rotateWithLeftChild(AVLNode       k2)       {       
                    AVLNode       k1       =       k2.left;       
                    k2.left       =       k1.right;       
                    k1.right       =       k2;       
                    return       k1;       
            }       
            private       static       AVLNode       rotateWithRightChild(AVLNode       k1)       
                            {AVLNode       k2=k1.right;       
            k1.right=k2.left;       
            k2.left=k1;       
            return       k2;       
            }       
            private       static       AVLNode       doubleWithLeftChild(AVLNode       k3)       
                            {k3.left=rotateWithRightChild(k3.left);       
            return       rotateWithLeftChild(k3);       
            }       
            private       static       AVLNode       doubleWithRightChild(AVLNode       k3)       
                            {k3.right=rotateWithLeftChild(k3.right);       
            return       rotateWithRightChild(k3);       
            }       
                    
           赞成楼上的说法

Answer 6

图书馆去借一本数据结构java实现来看看就行了