数据结构5——二叉树（1）

1：二叉树的建立

二叉树的建立有两种模式：（1）：首先设计二叉树的结点类，然后在此基础上，用static成员函数实现二叉树的具体操作。

　　　　　　　　　　　　（2）：设计二叉树的结点类，然后在二叉树的结点类的基础上设计二叉树类。

 1 /*
 2  * 定义一个二叉树的结点类
 3  */
 4 public class BinTreeNode {
 5     private BinTreeNode leftChild;
 6     private BinTreeNode rightChild;
 7     private Object data;
 8     
 9     public BinTreeNode(){
10         leftChild=null;
11         rightChild=null;
12     }
13     
14     public BinTreeNode(BinTreeNode left, BinTreeNode right,Object Idata){
15         leftChild=left;
16         rightChild=right;
17         data=Idata;
18     }
19 
20     public BinTreeNode getLeftChild() {
21         return leftChild;
22     }
23 
24     public BinTreeNode getRightChild() {
25         return rightChild;
26     }
27 
28     public Object getData() {
29         return data;
30     }
31 }

设计完了二叉树的结点类之后，在二叉树的结点类的基础上用static成员函数实现二叉树的具体操作。

包括二叉树的生成，二叉树的打印，二叉树的遍历，在二叉树中查找元素。

(1）首先在二叉树结点类的基础上构建二叉树。结构如上图所示：

先构造一个方法用于获得二叉树的结点类

//获得一个二叉树结点的类
    public static BinTreeNode getTreeNode(Object item, BinTreeNode left, BinTreeNode right){
        //构造一个二叉树
        BinTreeNode temp=new BinTreeNode(left, right, item);
        return temp;
    }

//在结点类的基础上构造一个二叉树
    public static BinTreeNode makeTree(){
        BinTreeNode a,b,c,d,e,f,g,h;
        
        g=getTreeNode(new Character('G'), null, null);
        d=getTreeNode(new Character('D'), null, g);
        b=getTreeNode(new Character('B'), d, null);
        e=getTreeNode(new Character('E'), null, null);
        f=getTreeNode(new Character('F'), null, null);
        c=getTreeNode(new Character('C'), e, f);
        return getTreeNode(new Character('A'), b, c);
    }

（2）打印一棵二叉树

 1 //打印二叉树，主要将纵向的二叉树横过来，基本的思维是先打印右子树，根节点，左子树
 2     public static void printBiTree(BinTreeNode root, int level){
 3         if (root!=null) {
 4             //根节点root的level+1层开始输出右子树，不断的递归调用
 5             printBiTree(root.getRightChild(), level+1);
 6             
 7             if (level!=0) {
 8                 for(int i=0; i<6*(level-1); i++){
 9                     System.out.print(" ");
10                 }
11                 System.out.print("---");
12             }
13             System.out.println(root.getData());         //输出结点数据元素的值
14             
15             //根节点root的level+1层开始输出左二叉树，不断的递归调用
16             printBiTree(root.getLeftChild(), level+1);
17         }
18     }

（3）：查找二叉树中的某个元素

 1 //定义一个方法在二叉树中查找某个(x)元素
 2     public static BinTreeNode search(BinTreeNode t,Object x){
 3         
 4         BinTreeNode temp;
 5         if (t==null) return null;                //查询失败
 6         if (t.getData().equals(x)) return t;     //查找成功返回某个子二叉树
 7         
 8         //在左子树寻找元素
 9         if(t.getLeftChild()!=null){
10             temp=search(t.getLeftChild(), x);
11             if (temp!=null) return temp;
12         }
13         //在右子树中寻找元素
14         if(t.getRightChild()!=null){
15             temp=search(t.getRightChild(), x);
16             if (temp!=null) return temp;
17         }    
18         return null;        //查询失败的出口
19     }

（5）：实现二叉树中最重要的遍历，用递归的方法实现。当然后面肯定有非递归的方法。

首先需要定义一个访问二叉树结点的方法

1 /*
2  * 定义一个类用于打印输出每个结点
3  */
4 public class Visit {
5     public void print(Object item){
6         System.out.print(item+" ");
7     }
8 }

/*
 * 定义一个用于遍历二叉树的类
 */
public class BinTraverse {
    
    //前序遍历
    public static void preOrder(BinTreeNode t, Visit v){
            //如果是非递归的方法遍历二叉树，此时这里面的if 还能用if吗？
        if (t!=null) {
            v.print(t.getData());
            preOrder(t.getLeftChild(), v);
            preOrder(t.getRightChild(), v);
        }
    }
    
    //中序遍历
    public static void inOrder(BinTreeNode t, Visit v){
        if (t!=null) {
            inOrder(t.getLeftChild(), v);
            v.print(t.getData());
            inOrder(t.getRightChild() , v);
        }
    }
    
    //后序遍历
    public static void postOrder(BinTreeNode t, Visit v){
        if (t!=null) {
            postOrder(t.getLeftChild(), v);
            postOrder(t.getRightChild(), v);
            v.print(t.getData());
        }
    }
    
    //层序遍历,层序遍历的基本原理是，每遍历一个根节点则进去左右两个孩子节点
    //逻辑类似于队列，先进先出
    public static void levelOrder(BinTreeNode t, Visit v) throws Exception{
        LinQueue lq=new LinQueue();　　　　　　　　　　　　　　　　　　//这里面需要链式队列的类型
        
        if (t==null)  return;
        BinTreeNode curr;
        lq.append(t);
        while (lq.notEmpty()) {
            curr=(BinTreeNode) lq.delete();            //从队列中删除根节点，并且将队列转化为二叉树的一个结点
            v.print(curr.getData());                //并且输出该节点的值
            //将左右结点分别插入到队列中
            if (curr.getLeftChild()!=null) 
                lq.append(curr.getLeftChild());
            if (curr.getRightChild()!=null) 
                lq.append(curr.getRightChild());
        }
    }
}

 1     /*
 2      * main函数 
 3      */
 4     public static void main(String[] args) {
 5         BinTreeNode root1;
 6         BinTreeNode temp2;
 7         
 8         Visit v=new Visit();
 9         
10         root1=makeTree();
11         System.out.println("二叉树为： ");
12         printBiTree(root1, 0);
13         System.out.println();
14         
15         
16         System.out.println("前序遍历节点序列为：");
17         BinTraverse.preOrder(root1, v);
18         System.out.println();
19         
20         System.out.println("中序遍历节点序列为：");
21         BinTraverse.inOrder(root1, v);
22         System.out.println();
23         
24         System.out.println("后序遍历节点序列为：");
25         BinTraverse.postOrder(root1, v);
26         System.out.println();
27         
28         
29         //查找某个元素
30         temp2=search(root1, new Character('F'));
31         if (temp2!=null) {
32             System.out.println("查到该节点的数据元素为： "+temp2.getData());
33         }
34         else{
35             System.out.println("查找失败！");
36         }

**************上面说道二叉树的建立，有两种方法，下面实现第二种方便生成二叉树，在结点的基础之上建立二叉树的类。**********

（1）二叉树结点类

 1 /*
 2  * 定义一个二叉树的结点类
 3  */
 4 public class BinTreeNode {
 5     private BinTreeNode leftChild;
 6     private BinTreeNode rightChild;
 7     private Object data;
 8     
 9     public BinTreeNode(){
10         leftChild=null;
11         rightChild=null;
12     }
13     
14     public BinTreeNode(BinTreeNode left, BinTreeNode right,Object Idata){
15         leftChild=left;
16         rightChild=right;
17         data=Idata;
18     }
19 
20     public BinTreeNode getLeftChild() {
21         return leftChild;
22     }
23 
24     public BinTreeNode getRightChild() {
25         return rightChild;
26     }
27 
28     public Object getData() {
29         return data;
30     }
31 }

在二叉树结点类的基础上实现二叉树

 1 /*
 2  * 先在二叉树结点类的基础上，设计二叉树类
 3  */
 4 public class BinTree {
 5     private BinTreeNode root;                //根指针
 6     
 7     
 8     //前序遍历
 9     public void preOrder(BinTreeNode t, Visit s){
10         if (t!=null) {
11             s.print(t.getData());
12             preOrder(t.getLeftChild(), s);
13             preOrder(t.getRightChild(), s);
14         }
15     }
16     
17     //中序遍历
18     public void inOrder(BinTreeNode t, Visit s){
19         if (t!=null) {
20             inOrder(t.getLeftChild(), s);
21             s.print(t.getData());
22             inOrder(t.getRightChild(), s);
23         }
24     }
25     
26     //后序遍历
27     public void postOrder(BinTreeNode t, Visit s){
28         if (t!=null) {
29             postOrder(t.getLeftChild(), s);
30             postOrder(t.getRightChild(), s);
31             s.print(t.getData());
32         }
33     }
34     
35     //构造函数用于初始化root结点
36             public BinTree(){
37                 root= null;
38             }
39             
40             //构造函数用于处理一个二叉树
41             public BinTree( BinTree left, BinTree right,Object item){
42                 BinTreeNode leftNode;
43                 BinTreeNode rightNode;
44                 
45                 if (left==null) {
46                     leftNode=null;
47                 }else{
48                     leftNode=left.root;　　　　　　　　        //让左子树获得左子树的结点
49                 }
50                 
51                 if (right==null) {
52                     rightNode=null;
53                 }else{
54                     rightNode=right.root;
55                 }
56                 
57                 root=new BinTreeNode(leftNode, rightNode, item);
58                 
59             }    
60     
61     //前序遍历 在二叉树类遍历的基础上，调用二叉树结点遍历方法还是让二叉树结点类实现递归作用，因为最终遍历的都是书的结点
62     public void preOrder(Visit vs){
63         preOrder(root, vs);
64     }
65     
66     //中序遍历
67     public void inOrder(Visit vs){
68         inOrder(root, vs);
69     }
70     
71     //后序遍历
72     public void postOrder(Visit vs){
73         postOrder(root, vs);
74     }
75 }

写一个测试类，包括二叉树的建立，以及二叉树的遍历。

 1 public static void main(String[] args) {
 2         
 3         //构造第二种方法的二叉树
 4         BinTree g=new BinTree(null, null, new Character('G'));
 5         BinTree d=new BinTree(null, g, new Character('D'));
 6         BinTree b=new BinTree(d, null, new Character('B'));
 7         BinTree e=new BinTree(null, null, new Character('E'));
 8         BinTree f=new BinTree(null, null, new Character('F'));
 9         BinTree c=new BinTree(e, f, new Character('C'));
10         BinTree a=new BinTree(b, c, new Character('A'));
11         
12         
13         Visit v=new Visit();
14         
15         System.out.print("前序遍历结点序列为：");
16         a.preOrder(v);
17         System.out.println();
18         
19         System.out.print("中序遍历结点序列为：");
20         a.inOrder(v);
21         System.out.println();
22         
23         System.out.print("后序遍历结点序列为：");
24         a.postOrder(v);
25         System.out.println();
26     }

大体的实现就是这样，还是感叹一句啊，在能够完全理解的情况下还是要多敲代码啊！！！！

No more talking,show me coding!!

下一节：非递归的二叉树遍历。