posts - 13, comments - 7, trackbacks - 0, articles - 0

          數據結構中的樹

          Posted on 2008-10-24 00:06 eyejava 閱讀(286) 評論(0)  編輯  收藏
          package tree;

          /**
           * 結點數據
           * @author jiaqiang
           *
           */
          public class Node {
              private int key;
              private int data;
              private Node leftChild;
              private Node rightChild;
              
              public Node() {}
              
              public Node(int key, int data) {
                  this.key = key;
                  this.data = data;
              }

              public int getKey() {
                  return key;
              }

              public int getData() {
                  return data;
              }

              public Node getLeftChild() {
                  return leftChild;
              }

              public void setLeftChild(Node leftChild) {
                  this.leftChild = leftChild;
              }

              public Node getRightChild() {
                  return rightChild;
              }

              public void setRightChild(Node rightChild) {
                  this.rightChild = rightChild;
              }
              
              public void display() {
                  System.out.print(data + " ");
              }
          }

          -------------------
          package tree;

          /**
           * 二叉樹
           * @author jiaqiang
           *
           */
          public class Tree {
              private Node root;
              private int size;
              
              /**
               * 查找某個值
               * @param key   要查找的值
               * @return Node 查找到的結點
               */
              public Node find(int key) {
                  Node current = root;
              
                  while ((current!=null) && (current.getKey()!=key)) {
                      if (key < current.getKey()) {           //go left
                          current = current.getLeftChild();
                      } else {
                          current = current.getRightChild();  //go right
                      }
                      
                      if (current == null) {
                          return null;
                      }
                  }
                  
                  return current;
              }
              
              /**
               * 插入某個值
               * @param key
               * @param data
               */
              public void insert(int key, int data) {
                  Node newNode = new Node(key, data);
                  
                  if (root == null) {  //空樹
                      root = newNode;
                      size++;
                  } else {             //not empty tree
                      Node current = root;
                      Node parent;     //作為插入結點的父結點
                      
                      while (true) {
                          parent = current;
                          if (key < current.getKey()) {
                              current = current.getLeftChild();
                              if (current == null) {
                                  parent.setLeftChild(newNode);
                                  size++;
                                  return;
                              }
                          } //end if go left
                          else {
                              current = current.getRightChild();
                              if (current == null) {
                                  parent.setRightChild(newNode);
                                  size++;
                                  return;
                              }
                          } //end if go right
                      } // end while (true)
                  }
              } //end insert
              
              /**
               * 中序遍歷,該方法為輔助方法
               * @param Node localRoot
               */
              private void inOrder(Node localRoot) {
                  if (localRoot != null) {
                      inOrder(localRoot.getLeftChild());
                      localRoot.display();
                      inOrder(localRoot.getRightChild());
                  } else
                      return;
              }
              
              /**
               * 中序遍歷
               */
              public void inOrder() {
                  inOrder(root);
              }
              
              public int getSize() {
                  return size;
              }

              public static void main(String[] args) {
                  Tree tree = new Tree();
                  tree.insert(23, 23);
                  tree.insert(20, 20);
                  tree.insert(24, 24);
               
                  
                  System.out.println(tree.getSize());
                  tree.inOrder();
              }

          }



          只有注冊用戶登錄后才能發表評論。


          網站導航:
           
          主站蜘蛛池模板: 隆子县| 肇庆市| 贺州市| 吉林省| 朝阳市| 璧山县| 兰西县| 恩平市| 新龙县| 突泉县| 青田县| 沈阳市| 肥东县| 肇庆市| 那曲县| 甘孜县| 洞口县| 晋江市| 西林县| 宣汉县| 莲花县| 河东区| 仁布县| 浦城县| 台安县| 黄平县| 获嘉县| 昌平区| 长沙县| 新竹市| 芷江| 平和县| 西贡区| 会东县| 辽中县| 东阿县| 建始县| 青河县| 东乌珠穆沁旗| 千阳县| 日喀则市|