二叉树

一些关于二叉树的简单操作

创建节点

/**
 * 构造一个二叉树节点
 *
 */
public class BinaryNode<T> {

    private T data;                 // 数据域
    public BinaryNode<T> lchild;    // 左孩子
    public BinaryNode<T> rchild;    // 右孩子
    
    public BinaryNode() {
        lchild = rchild = null;
    }
    
    public BinaryNode(T data) {
        this(data, null, null);
    }

    public BinaryNode(T data, BinaryNode<T> lchild, BinaryNode<T> rchild) {
        this.data = data;
        this.lchild = lchild;
        this.rchild = rchild;
    }
    
    
    
    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    // 查看节点的数据
    public void visit() {
        System.out.println(this.data + " ");
    }
}

简单操作

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 *          A
 * 
 *      B       C 
 *  D       E       F
 * ##       ##      ##      ABD##E##CF##
 * 二叉树 前中后遍历
 *
 */
public class BinaryTree {

    private BinaryNode<String> root;

    /**
     * 初始化根节点
     */
    public BinaryTree() {
        root = new BinaryNode<String>("A");
    }

    /**
     * 直接构造二叉树
     */
    public void createTree() {
        BinaryNode<String> NodeB = new BinaryNode<String>("B");
        BinaryNode<String> NodeC = new BinaryNode<String>("C");
        BinaryNode<String> NodeD = new BinaryNode<String>("D");
        BinaryNode<String> NodeE = new BinaryNode<String>("E");
        BinaryNode<String> NodeF = new BinaryNode<String>("F");
        root.lchild = NodeB;
        root.rchild = NodeC;
        NodeB.lchild = NodeD;
        NodeB.rchild = NodeE;
        NodeC.rchild = NodeF;
    }

    /**
     * 求二叉树的高度
     * 
     * @param Tree
     * @return
     */
    public int getHeight(BinaryNode<String> node) {
        if (node == null) {
            return 0;
        } else {
            int i = getHeight(node.lchild);
            int j = getHeight(node.rchild);
            return (i > j) ? i + 1 : j + 1;
        }
    }

    /**
     * 求二叉树的节点数
     * 
     * @param Tree
     * @return
     */
    public int getSize(BinaryNode<String> node) {
        if (node == null) {
            return 0;
        } else {
            return 1 + getSize(node.lchild) + getSize(node.rchild);
        }
    }
    
    /**
     * 前序遍历     根 左 右
     */
    public void preOrderTree(BinaryNode<String> node) {
        if(node == null) {
            return;
        } else {
            System.out.print(node.getData() + " ");
            preOrderTree(node.lchild);
            preOrderTree(node.rchild);
        }
    }
    
    /**
     * 后序遍历      左 右 根
     */
    public void postOrderTree(BinaryNode<String> node) {
        if(node == null) {
            return;
        } else {
            postOrderTree(node.lchild);
            postOrderTree(node.rchild);
            System.out.print(node.getData() + " ");
        }
    }
    
    /**
     * 中序遍历  左  根  右
     */
    public void inOrderTree(BinaryNode<String> node) {
        if(node == null) {
            return;
        } else {
            inOrderTree(node.lchild);
            System.out.print(node.getData() + " ");
            inOrderTree(node.rchild);
        }
    }

    
    /**
     * 非递归前序遍历
     * 
     */
    
    public void nonRecPreOrderTree(BinaryNode<String> node) {
        if(node == null) {
            return;
        }
        Stack<BinaryNode<String>> stack = new Stack<BinaryNode<String>>();
        stack.push(node);
        while(!stack.isEmpty()) {
            BinaryNode<String> n = stack.pop();
            if(n == null) {
                continue;
            }
            System.out.print(n.getData()+" ");
            stack.push(n.rchild);
            stack.push(n.lchild);
        }
    }
    
    /**
     * 前序递归的方式创建二叉树
     * @param list
     */
    public void  createBinaryTree(List<String> list){
        createBinaryTreePro(list.size(), list);
    }
    
    /**
     * 
     * @param size
     * @param list
     * @return
     */
    private BinaryNode<String> createBinaryTreePro(int size, List<String> list) {
        // 如果list为空就返回
        if(list.size() == 0) {
            return null;
        }
        // 获取第一个元素
        String nodeData = list.get(0);
        int index = size - list.size();         // index是用来判断是否为根节点的计数器
        BinaryNode<String> node = new BinaryNode<String>(nodeData);     // 创建一个节点
        if(nodeData.equals("#")) {              // 如果nodeData为"#"(还可以是其他字符串), 则node就为null,不存在       
            node = null;                        
            list.remove(0);                     // 同时移除该元素
            return node;                        // 返回空
        }
        if(index == 0) {                        // 如果index为0,那么该节点就是根节点
            root = node;                        // 把node赋值给root
        }
        
        list.remove(0);                         // 在list中移除该元素
        node.lchild = createBinaryTreePro(size, list);
        node.rchild = createBinaryTreePro(size, list);
        
        return node;
    }

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
//      binaryTree.createTree();
//      int height = binaryTree.getHeight(binaryTree.root);
//      System.out.println("TreeHeight: " + height);
//      int size = binaryTree.getSize(binaryTree.root);
//      System.out.println("TreeSize: " + size);
//      System.out.print("preOrder: ");
//      binaryTree.preOrderTree(binaryTree.root);
//      System.out.println();
//      System.out.print("inOrder: ");
//      binaryTree.inOrderTree(binaryTree.root);
//      System.out.println();
//      System.out.print("postOrder: ");
//      binaryTree.postOrderTree(binaryTree.root);
//      System.out.println();
//      ABD##E##CF##
        List<String> list = new ArrayList<String>();
        String[] data = {"A","B","D", "#","#","E","#","#","C","F","#","#"};
        for(String x: data) {
            list.add(x);
        }
        binaryTree.createBinaryTree(list);
        binaryTree.nonRecPreOrderTree(binaryTree.root);
    }
}