二叉树

一、二叉树的概念

二叉树是保存数据的一种结构，二叉树由节点组成，每一个节点有一个或者两个或者零个子节点，子节点又分为左子节点和右子节点，一般习惯让左子节点比右子节点下。比如说一个数组中的元素就可以按照二叉树结构进行保存
DEMO:将数组元素保存到二叉树中
{32,10,9,78,23,15,90,85,100}

此时数组的元素以二叉树的结构进行保存，取数据的时候就可以升序或者降序获取了。如果以升序取得数组的元素的过程：
先找到树的根节点32，判断根节点是否有左节点。
{9,10,15,23,32,78,85,90,100}

二叉树排序

内部类
内部类就是在一个类中再定义一个类，主要目的是方便内部类直接访问外部类的私有属性、其次内部类是不希望其他类直接访问的，是他的外部类服务的。
DEMO：内部类访问外部类的私有属性

package com.sun.test;
public class Outer {
	 //这是外部类的私有属性
    private  Integer   age=20;
    //定义一个内部类
    public   class  Inner{
    	 //访问外部类的私有属性
    	 public void  fun() {
    		 System.out.println("年龄是："+age);
    	 }
    }
}

package com.sun.test;
public class Test {
	 public static void main(String[] args) {
		   new Outer().new Inner().fun();
	 } 
}

年龄是：20
发现了可以在内部类中直接访问外部类的私有属性。
二叉树排序
需要先将数组的元素按照二叉树的方法是存储，之后再按照升序或者降序的方式重新取得元素

lass  BinaryTree{  //这是二叉树的外部类
       private  Node    root;//表示树的根节点
       private  int   count;//统计有多少个节点
       private  int  foot;//表示下标（脚标）
       private   int  []  reData;//新的数组，保存的是已经排序号的元素。
       //定义一个内部类表示节点
       private  class  Node{
            private  int  data;
            private  Node  left;//左子节点的引用
            private   Node right;//右子节点的引用
            public  Node(int  data){
                this.data=data;
            }
            //添加节点
           public  void  addNode(Node newNode){
                 if(newNode.data<this.data){
                      if(this.left==null){
                          this.left=newNode ;
                      }else{
                          this.left.addNode(newNode);
                      }
                 }else{
                      if(this.right==null){
                          this.right=newNode;
                      }else{
                          this.right.addNode(newNode);
                      }
                 }
           }
           //将二叉树中的节点的保存到数组中（内部类中方法）
           public void toArrayNode(){
                if(this.left!=null){
                    this.left.toArrayNode();
                }
                BinaryTree.this.reData[foot++]=this.data;
                if(this.right!=null){
                    this.right.toArrayNode();
                }
           }
       }
       //以下是外部类中增加数据的方法
      public  void  add(int  data){
          Node  newNode=new Node(data);
          if(this.root==null){
              this.root=newNode;
          }else{
              this.root.addNode(newNode);
          }
          count++;
      }
    /**
     * 将数组保存到二叉树中 之后再按照升序后返回
     * @param arr 原始的数组
     * @return
     */
      public   int  []  toArray(int []  arr){
            //把原始的数组中的元素按照节点的方式保存到二叉树中
            for(int temp:arr){
                  this.add(temp);
            }
            if(this.root==null){
                return null;
            }
            this.foot=0;//重新初始化下标，因为可能多次调用
            this.reData  =new int[count];
            this.root.toArrayNode();
            return   this.reData;
      }
}
public class Test {
    public static void main(String[] args) {
        int  arr[]= {32,10,9,78,23,15,90,85,100};
        BinaryTree  binaryTree=new BinaryTree();
        int  newArr[]=binaryTree.toArray(arr);
        for(int temp:newArr){
            System.out.print("  " +temp);
        }
    }
}

二叉树

一、二叉树的概念

二叉树排序

相关推荐