二叉树

二叉树

无序数组: 查找删除慢,大小固定
有序数组:插入慢 删除幔
链表:查找慢,插入和删除慢

树的相关概念:
树: 由边连接着节点而构成

根: 树顶端的节点称为根,一棵树只有一个根
父节点:每个节点(除了跟) 都恰好有一条边线上连接到另外一个节点,上面的这个节点就是下面的这个节点的父节点

子节点:每个节点 都可能有一条边线下连接到另外一个节点,下面的这个节点就是上面的这个节点的子节点

叶节点:没有子节点的节点称为叶节点

子树:每个节点都可以作为"子树"根,它和它多有的子孙节点都含在子树中

二叉树是非平衡树,树中每个节点下面,最多有两个子节点,他的每一个节点,左子节点比该节点小,右子节点比该节点大.

二叉树的查找:速度是非常快的

二叉树的插入:插入节点和当前节点比较,小放左边,大放右边

二叉树的删除:先找到要删除的节点,
如果该节点有两个子节点,节点删除,右子树最左边的节点代替原来删除的节点
如果该节点只有左子节点,节点删除,左子节点代替原来删除的节点
如果该节点只有右子节点,节点删除,右子节点代替原来删除的节点
如果该节点没有子节点,直接删除.

package com.test.tree;


import java.util.Stack;  

public class BinaryTree {  
  private Node root;  
  public BinaryTree(){  
      root = null;  
  }  
    
  public void insert(int iData,double dData){  
      Node newNode = new Node();  
      newNode.setiData(iData);  
      newNode.setdData(dData);  
      if(root == null){//空树  
          root = newNode;  
      }else{  
          Node current = root;  
          Node parent;  
          while(true){  
              parent = current;  
              if(iData<current.getiData()){//往左边找  
                  current = current.getLeftChild();  
                  if(current==null){//左边的为空了,插入newNode  
                      parent.setLeftChild(newNode);  
                      return;  
                  }  
              }else{//否则往右边找  
                  current = current.getRightChild();  
                  if(current == null){//右边为空了,插入newNode  
                      parent.setRightChild(newNode);  
                      return;  
                  }  
              }  
          }  
      }  
  }  
    
  public boolean delete(int key){  
      Node current = root;  
      Node parent = root;  
      boolean isLeftChild = true;  
      while(current.getiData() != key){//找到要删除的节点current  
          parent = current;  
          if(key<current.getiData()){  
              isLeftChild = true;  
              current = current.getLeftChild();  
          }else{  
              isLeftChild = false;  
              current = current.getRightChild();  
          }  
          if(current ==null) return false;//没有找到要删除的节点,返回false,删除失败  
      }  
      if(current.getLeftChild() == null && current.getRightChild()==null){//current没有子节点,直接删除  
          if(current ==root)root = null;  
          else if(isLeftChild){  
              parent.setLeftChild(null);  
          }else{  
              parent.setRightChild(null);  
          }  
      }else if(current.getRightChild() == null){//要删除的节点只有左子节点  
          if(current == root ) root = current.getLeftChild();  
          else if(isLeftChild) parent.setLeftChild(current.getLeftChild());  
          else parent.setRightChild(current.getLeftChild());  
      }else if (current.getLeftChild() == null){//要删除的节点只有右节点  
          if(current == root ) root = current.getRightChild();  
          else if(isLeftChild) parent.setLeftChild(current.getRightChild());  
          else parent.setRightChild(current.getRightChild());  
      }else{//要删除的节点有两个子节点,current右边子树的最左边的那个节点替换current  
          Node replace = getReplace(current);  
          if(current == root) root = replace;  
          else if(isLeftChild) parent.setLeftChild(replace);  
          else parent.setRightChild(replace);  
          replace.setLeftChild(current.getLeftChild());  
      }  
      return true;  
  }  

  private Node getReplace(Node delNode) {  
      Node replaceParent = delNode;  
      Node replace = delNode;  
      Node current = delNode.getRightChild();  
      while(current != null){//找到要删除节点右边子树的最左边的那个节点  
          replaceParent = replace;  
          replace = current;  
          current = current.getLeftChild();  
      }  
      if(replace != delNode.getRightChild()){  
          replaceParent.setLeftChild(replace.getRightChild());  
          replace.setRightChild(delNode.getRightChild());  
      }  
      return replace;  
  }  
    
  public Node find(int key){  
      Node current = root;  
      while(current.getiData() != key){  
          if(key<current.getiData()){  
              current = current.getLeftChild();  
          }else{  
              current = current.getRightChild();  
          }  
          if(current == null) return null;  
      }  
      return current;  
  }  
    
  public void traverses(int traverseType){//从左到右,从下到上  
      switch(traverseType){  
      case 1://从上至下,从左到右  
          System.out.println("\n Preorder traversal:");  
          preOrder(root); 
          System.out.println();
          break;  
      case 2://从下至上,从左到右  
          System.out.println("\n Inorder traversal:");  
          inOrder(root); 
          System.out.println();
          break;  
      case 3://从下至上,从右到左  
          System.out.println("\n Postorder traversal:");  
          postOrder(root); 
          System.out.println();
          break;  
      }  
  }  

  private void postOrder(Node localRoot) {//从下至上,从右到左  
      if(localRoot!=null){  
          postOrder(localRoot.getRightChild());  
          postOrder(localRoot.getLeftChild());  
          System.out.print(localRoot.getiData()+" ");  
      }  
        
  }  

  private void inOrder(Node localRoot) {//从下至上,从左到右  
      if(localRoot != null){  
          inOrder(localRoot.getLeftChild());  
          System.out.print(localRoot.getiData()+" ");  
          inOrder(localRoot.getRightChild());  
      }  
        
  }  

  private void preOrder(Node localRoot) {//从上至下,从左到右  
      if(localRoot!=null){  
          System.out.print(localRoot.getiData()+" ");  
          preOrder(localRoot.getLeftChild());  
          preOrder(localRoot.getRightChild());  
      }  
  }  
    
  public void displayTree(){  
      Stack<Node> globalStack = new Stack<Node>();  
      globalStack.push(root);  
      int nBlanks =32;  
      boolean isRowEmpty = false;  
      System.out.println("----------------------------------------------------------------");  
      while(isRowEmpty == false){  
          Stack<Node> localStack = new Stack<Node>();  
          isRowEmpty = true;  
          for(int j=0;j<nBlanks;j++){  
        	  for(j=0;j<nBlanks-2; j++){  
                  System.out.print(" ");  
              }   
              while(globalStack.isEmpty()==false){  
                  Node temp= (Node)globalStack.pop();  
                  if(temp!=null){  
                      System.out.print(temp.getiData());  
                      localStack.push(temp.getLeftChild());  
                      localStack.push(temp.getRightChild());  
                      if(temp.getLeftChild()!=null || temp.getRightChild()!=null){  
                          isRowEmpty = false;  
                      }  
                  }else{  
                      System.out.print("**");  
                      localStack.push(null);  
                      localStack.push(null);  
                  }  
                  for(j=0;j<nBlanks*2-2; j++){  
                      System.out.print(" ");  
                  }  
              }//while end  
              System.out.println();  
              nBlanks/=2;  
              while(localStack.isEmpty()==false){  
                  globalStack.push(localStack.pop());  
              }  
          }  
          System.out.println(".............................................................");  
      }  
  }  
}  

package com.test.tree;
public class Node {  
    private int iData;  
    private double dData;  
    private Node leftChild;  
    private Node rightChild;  
      
    public void display(){  
        System.out.println(toString());  
    }  
      
      
    /** 
     * @return the iData 
     */  
    public int getiData() {  
        return iData;  
    }  
  
  
    /** 
     * @param iData the iData to set 
     */  
    public void setiData(int iData) {  
        this.iData = iData;  
    }  
  
  
    /** 
     * @return the dData 
     */  
    public double getdData() {  
        return dData;  
    }  
  
  
    /** 
     * @param dData the dData to set 
     */  
    public void setdData(double dData) {  
        this.dData = dData;  
    }  
  
  
  
  
  
    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;
	}


	@Override
	public String toString() {
		return "Node [iData=" + iData + ", dData=" + dData + ", leftChild="
				+ leftChild + ", rightChild=" + rightChild + "]";
	}

package com.test.tree;

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
  
public class BinaryTreeTest {  
      
    public static String getString()throws IOException{  
        InputStreamReader is = new InputStreamReader(System.in);  
        BufferedReader br =  new BufferedReader(is);  
        return br.readLine();  
    }  
      
    public static char getChar()throws IOException{  
        return getString().charAt(0);  
    }  
    public static int getInt()throws IOException{  
        return Integer.parseInt(getString());  
    }  
    /** 
     * @param args 
     * @throws IOException  
     */  
    public static void main(String[] args) throws IOException {  
        int value;  
        BinaryTree t = new BinaryTree();  
        int nodeNumber = 10;
        for(int i=0;i<nodeNumber;i++){
        	int iData = (int)(Math.random()*(100-10)+10);//10-100 random data
        	t.insert(iData, 1.5d);
        }
       
  
        while(true){  
            System.out.print("Enter first letter of show, insert, find,delete or traverse:");  
            char choice = getChar();  
            switch(choice){  
            case 's'://display  
                t.displayTree();  
                break;  
            case 'i'://insert  
                System.out.print("Enter value to insert:");  
                value =  getInt();  
                t.insert(value, 9.9d);  
                break;  
            case 'f'://find  
                System.out.print("Enter value to find:");  
                value =  getInt();  
                Node found = t.find(value);  
                if(found!=null){  
                    System.out.print("found:");  
                    found.display();  
                    System.out.println();  
                }else{  
                    System.out.println("could not find "+value);  
                }  
                break;  
            case 'd'://delete  
                System.out.print("Enter value to delete:");  
                value =  getInt();  
                boolean result = t.delete(value);  
                if(result){  
                    System.out.println("delete successful");  
                }else{  
                    System.out.println("delete failed");  
                }  
                break;  
            case 't':  
                System.out.print("Enter traverse type 1,2 or 3:");  
                value = getInt();  
                t.traverses(value);  
                break;  
            default:  
                System.out.println("Invalid input");  
            }  
        }  
    }  
  
}