Posted by & filed under Uncategorized.

About Gu Zhenfei

Zhenfei Gu has written 44 post in this blog.

实现二叉树的增加、查找、删除、遍历

 

实现

 

结点类

  1. public class Node{
  2. int key;
  3. int data;
  4. Node lchild=null;
  5. Node rchild=null;
  6. public Node(int key,int data)
  7. {
  8.     this.key=key;
  9.     this.data=data;
  10. }
  11. }

二叉树类:

  1. public class BinaryTree {
  2.      Node root=null;
  3.      public void add(int key,int data)
  4.      {
  5.          Node node=new Node(key,data);
  6.          if (root==null)
  7.              root=node;
  8.          else
  9.          {
  10.              Node current=root;
  11.              Node pre=null;
  12.              while (true)
  13.              {
  14.                  if (key<current.key)
  15.                  {
  16.                      pre=current;
  17.                      current=current.lchild;
  18.                      if (current==null)
  19.                      {
  20.                          pre.lchild=node;
  21.                          break;
  22.                      }
  23.                  }
  24.                  else
  25.                  {   pre=current;
  26.                  current=current.rchild;
  27.                  if (current==null)
  28.                      {
  29.                      pre.rchild=node;
  30.                      break;
  31.                      }
  32.                  }
  33.              }
  34.          }
  35.      }
  36.      public Node findNode(int key)
  37.      {
  38.          Node current=root;
  39.          while (current!=null)
  40.          {
  41.              if (current.key==key)
  42.                  return current;
  43.              else if (key<current.key)
  44.                  current=current.lchild;
  45.              else current=current.rchild;
  46.          }
  47.          return null;
  48.      }
  49.      public int findElement(int key)
  50.      {
  51.          Node current=root;
  52.          while (current!=null)
  53.          {
  54.              if (current.key==key)
  55.                  return current.data;
  56.              else if (key<current.key)
  57.                  current=current.lchild;
  58.              else current=current.rchild;
  59.          }
  60.          return 0;
  61.      }
  62.      public boolean delete (int key)
  63.      {
  64.          Node current=root;
  65.          boolean isleftchild=false;
  66.          Node parent=root;
  67.          Node currentdouble=null;
  68.          while (current!=null)
  69.          {
  70.              if (root.key==key)
  71.              {
  72.                  root=null;
  73.                  return true;
  74.              }
  75.              if (current.key==key)
  76.              {
  77.                  //当前结点没有孩子,直接删除
  78.                  if (current.lchild==null && current.rchild==null)
  79.                  {
  80.                      if (isleftchild=true)
  81.                          parent.lchild=null;
  82.                      else parent.rchild=null;
  83.                      return true;
  84.                  }
  85.                 //当前结点没有左孩子,有右孩子
  86.                  if (current.lchild==null && current.rchild!=null)
  87.                  {
  88.                      if (isleftchild=true)
  89.                          parent.lchild=current.rchild;
  90.                      else parent.rchild=current.lchild;
  91.                      return true;
  92.                  }
  93.                     //当前结点没有右孩子,有左孩子
  94.                  if (current.lchild!=null && current.rchild==null)
  95.                  {
  96.                      if (isleftchild=true)
  97.                          parent.lchild=current.lchild;
  98.                      else parent.rchild=current.lchild;
  99.                      return true;
  100.                  }
  101.                  //右孩子,左孩子都有情况,将左孩子结点替换当前结点,当前结点的右孩子作为替换操作后子树中最右的一个结点
  102.                  if (current.lchild!=null && current.rchild!=null)
  103.                  {
  104.                      if (isleftchild=true)
  105.                          parent.lchild=current.lchild;
  106.                      else parent.rchild=current.lchild;
  107.                      currentdouble=current.lchild;
  108.                      Node rparent=null;
  109.                      while (currentdouble!=null)
  110.                      {
  111.                          rparent=currentdouble;
  112.                          currentdouble=currentdouble.rchild;
  113.                      }
  114.                      rparent.rchild=current.rchild;
  115.                     return true;
  116.                  }
  117.              }
  118.              else if (key<current.key)
  119.              {   parent=current;
  120.                  current=current.lchild;
  121.                  isleftchild=true;
  122.              }
  123.              else {
  124.                  parent=current;
  125.                  current=current.rchild;
  126.                  isleftchild=false;
  127.              }
  128.          }
  129.          return false;
  130.      }
  131.      //先序遍历
  132.      public void preorder(Node node)
  133.      {
  134.          if (node!=null)
  135.          {
  136.              System.out.println(node.data);
  137.              preorder(node.lchild);
  138.              preorder(node.rchild);
  139.          }
  140.      }
  141.      //中序遍历
  142.      public void midorder(Node node)
  143.      {
  144.          if (node!=null)
  145.          {
  146.              midorder(node.lchild);
  147.              System.out.println(node.data);
  148.              midorder(node.rchild);
  149.          }
  150.      }
  151.      //后序遍历
  152.      public void lastorder(Node node)
  153.      {
  154.          if (node!=null)
  155.          {
  156.              lastorder(node.lchild);
  157.              lastorder(node.rchild);
  158.              System.out.println(node.data);
  159.          }
  160.      }
  161. }

测试类

  1. public class Test {
  2.     public static void main(String[] args)
  3.     {
  4.         BinaryTree bt=new BinaryTree();
  5.         bt.add(100, 100);
  6.         bt.add(50, 50);
  7.         bt.add(150, 150);
  8.         bt.add(10, 10);
  9.         bt.add(60, 60);
  10.         bt.add(120, 120);
  11.         bt.add(180, 180);
  12.         System.out.println(bt.findElement(50));
  13.         System.out.println(bt.root.data);
  14.         bt.preorder(bt.root);
  15.         System.out.println(bt.root.key);
  16.         System.out.println(bt.delete(50));
  17.         bt.preorder(bt.root);
  18.     }
  19. }

Leave a Reply

  • (will not be published)