JAVA采取递归构建并且遍历二叉树

下面是一维数组存储结构示意图
由上面来看这个一维数组存储结构很简单，这里是一颗完全二叉树所以在一维数组里面没有造成内存的浪费。但是如果不是一个完全或者满二叉树的话，并且仍然采取顺序存储结构的话就会造成大量的内存单元浪费，因为我们必须给二叉树添上一些虚构的不存在的结点，这是资源浪费一方面。另一方面是如果这棵二叉树存在大量的插入和删除等操作就会出现运算的不方便，因为我们插入或者删除一个结点就会造成大量的其他结点的移动。所以基于以上等各方面的原因，对于一般的二叉树而言我们都采用的是链式存储结构。
2、链式存储结构
由于在二叉树每个结点都最多有两个孩子，所以一般来说每个链结点都有三个域，分别是左孩子指针域、数据域、右孩子指针域。结构图如下：







3、二叉树的运算

遍历二叉树是二叉树中的一个重要运算，同时也是二叉树其他运算的基础。二叉树的遍历大致可以分为三种遍历方式，主要是根据二叉树的遍历顺序来区分。

访问根结点

按前序遍历根结点的右孩子树
按中序遍历根结点的左孩子树

按中序遍历根结点的右孩子树

后序遍历

按后序遍历根结点的右孩子树[/size]





[size=10.5000pt; font-family: '宋体';]package com.bes.bintree.test;

public class Node {

    private Node leftChild ;
    private Node rightChild;
    private int data;
    
    public Node(){
    }
    
    public Node(int data){
        this.data = 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 int getData() {
        return data;
    }
    public void setData(int data) {
         this.data = data;
    }
    

    
}

package com.bes.bintree.test;

import java.util.Scanner;


public class CreateTree {
    static int array[] = {23,10,0,88,0,0,15,0,34,0,0,0};
    
    public static void main(String args[]) {
        Node node = null;
        Scanner scanner = new Scanner(System.in);
        node = createTreeNode(node, scanner);
        System.out.println("中序遍历");
        inOrder(node);
        System.out.println("前序遍历");
        preOrder(node);
        System.out.println("后序遍历");
        postOrder(node);
    }
    /**
     * 构建二叉树
     * @param node
     * @param scanner
     * @return
     */
    private static Node createTreeNode(Node node,Scanner scanner) {
        int data = scanner.nextInt();
        if (data == 0) {
            return null;
        }else {
            node = new Node(data);
            node.setLeftChild(createTreeNode(node.getLeftChild(), scanner));
            node.setRightChild(createTreeNode(node.getRightChild(),scanner));
        }
        return node;
    }
    
    /**
     * 中序遍历
     * @param node
     */
    private static void inOrder(Node node) {
        if (node != null) {
            inOrder(node.getLeftChild());
            System.out.println(node.getData());
            inOrder(node.getRightChild());
        }
    }
    
    /**
     * 前序遍历
     * @param node
     */
    private static void preOrder(Node node) {
        if(node != null) {
            System.out.println(node.getData());
            preOrder(node.getLeftChild());
            preOrder(node.getRightChild());
        }
    }
    /**
     * 后序遍历
     * @param node
     */
    private static void postOrder(Node node) {
        if (node != null) {
            postOrder(node.getLeftChild());
            postOrder(node.getRightChild());
            System.out.println(node.getData());
        }
    }
}

[/size]
[/align]

评论

1 楼 生活的聆听者 2014-11-02  

欢迎大家提出意见，谢谢~~