数据拾遗之二叉树的基本操作(java实现)

页面导航:首页 > 软件编程 > Java编程 > 数据拾遗之二叉树的基本操作(java实现)

数据拾遗之二叉树的基本操作(java实现)

来源: 作者: 时间:2016-01-18 15:52 【

总结了一下二叉树的基本操作,包括先序遍历、中序遍历、后序遍历的递归形式和非递归形式(栈实现),以及层次遍历(队列实现)等。主要代码import java util Queue;import java util Stack;

总结了一下二叉树的基本操作,包括先序遍历、中序遍历、后序遍历的递归形式和非递归形式(栈实现),以及层次遍历(队列实现)等。

主要代码

import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * 简单的二叉树构造
 * 
 * @author xdsjs
 * @param 
 *
 */
public class BinTree {

    private BinNode rootNode;// 根节点

    public BinTree() {
    }

    public BinTree(BinNode rootNode) {
        this.rootNode = rootNode;
    }

    /**
     * 得到整棵树的高度
     * 
     * @return
     */
    public int getHeight() {
        return getHeight(rootNode);
    }

    /**
     * 利用递归得到某一结点的高度
     * 
     * @param binNode
     *            目标结点
     * @return
     */
    public int getHeight(BinNode binNode) {
        if (binNode == null)
            return 0;
        int i = getHeight(binNode.getLeftNode());
        int j = getHeight(binNode.getRightNode());
        return i < j ? j + 1 : i + 1;
    }

    /**
     * 递归得到整棵树的size(即结点数)
     * 
     * @return
     */
    public int getSize() {
        return getSize(rootNode);
    }

    /**
     * 得到某一子树的size(即结点数)
     * 
     * @param binNode
     * @return
     */
    public int getSize(BinNode binNode) {
        if (binNode == null)
            return 0;
        return 1 + getSize(binNode.getLeftNode()) + getSize(binNode.getRightNode());
    }

    /**
     * 判断二叉树是否为空树
     * 
     * @return
     */
    public boolean isEmpty() {
        return rootNode == null;
    }

    /**
     * 得到整棵树下某一结点的双亲结点
     * 
     * @param binNode
     *            某一结点
     * @return
     */
    public BinNode getParent(BinNode binNode) {
        return (binNode == null || binNode == rootNode) ? null : getParent(rootNode, binNode);
    }

    /**
     * 递归得到某子树下某结点的双亲结点
     * 
     * @param subTree
     *            某子树
     * @param binNode
     *            某结点
     * @return
     */
    public BinNode getParent(BinNode subTree, BinNode binNode) {
        if (subTree == null || binNode == null || subTree == binNode || binNode == rootNode)
            return null;
        if (subTree.getLeftNode() == binNode || subTree.getRightNode() == binNode)
            return subTree;
        BinNode b;
        if (getParent((b = subTree.getLeftNode()), binNode) != null)
            return b;
        return getParent(subTree.getRightNode(), binNode);
    }

    /**
     * 得到某一结点的左孩子结点
     * 
     * @param binNode
     * @return
     */
    public BinNode getLeftBinNode(BinNode binNode) {
        return (binNode == null) ? null : binNode.getLeftNode();
    }

    /**
     * 得到某一结点的右孩子结点
     * 
     * @param binNode
     * @return
     */
    public BinNode getRightBinNode(BinNode binNode) {
        return (binNode == null) ? null : binNode.getRightNode();
    }

    public BinNode getRoot() {
        return this.rootNode;
    }

    /**
     * 删除整棵树
     */
    public void deleteTree() {
        deleteTree(rootNode);
    }

    /**
     * 删除某子树(同时将其左右子树全部删除)
     * 
     * @param binNode
     */
    public void deleteTree(BinNode binNode) {
        if (binNode == null)
            return;
        deleteTree(binNode.getLeftNode());
        deleteTree(binNode.getRightNode());
        binNode = null;
    }

    /**
     * 访问某结点
     * 
     * @param subTree
     */
    public void visted(BinNode subTree) {
        System.out.println(--name: + subTree.getData());
    }

    /**
     * 先序遍历(递归形式)
     * 
     * @param subTree
     */
    public void preOrderTraverse(BinNode subTree) {
        if (subTree == null)
            return;
        visted(subTree);
        preOrderTraverse(subTree.getLeftNode());
        preOrderTraverse(subTree.getRightNode());
    }

    /**
     * 中序遍历(递归形式)
     * 
     * @param subTree
     */
    public void middleOrderTraverse(BinNode subTree) {
        if (subTree == null)
            return;
        middleOrderTraverse(subTree.getLeftNode());
        visted(subTree);
        middleOrderTraverse(subTree.getRightNode());
    }

    /**
     * 后序遍历(递归形式)
     * 
     * @param subTree
     */
    public void postOrderTraverse(BinNode subTree) {
        if (subTree == null)
            return;
        postOrderTraverse(subTree.getLeftNode());
        postOrderTraverse(subTree.getRightNode());
        visted(subTree);
    }

    /**
     * 先序遍历(非递归形式,效率更高)
     * 
     * @param subTree
     */
    public void nrPreOrderTraverse(BinNode subTree) {
        if (subTree == null)
            return;
        Stack> stack = new Stack<>();
        while (true) {
            while (subTree != null) {
                visted(subTree);
                stack.push(subTree);
                subTree = subTree.getLeftNode();
            }
            if (stack.isEmpty())
                break;
            subTree = stack.pop();
            subTree = subTree.getRightNode();
        }
    }

    /**
     * 中序遍历(非递归形式)
     * 
     * @param subTree
     */
    public void nrMiddleOrderTraverse(BinNode subTree) {
        if (subTree == null)
            return;
        Stack> stack = new Stack<>();
        while (true) {
            while (subTree != null) {
                stack.push(subTree);
                subTree = subTree.getLeftNode();
            }
            if (stack.isEmpty())
                break;
            subTree = stack.pop();
            visted(subTree);
            subTree = subTree.getRightNode();
        }
    }

    /**
     * 后序遍历(非递归)
     * 
     * @param subTree
     */
    public void nrPostOrderTraverse(BinNode subTree) {
        if (subTree == null)
            return;
        Stack> stack = new Stack<>();
        BinNode lastNode = null;// 表示最近一次访问的节点
        while (true) {
            while (subTree != null) {
                stack.push(subTree);
                subTree = subTree.getLeftNode();
            }
            if (stack.isEmpty())
                break;
            subTree = stack.peek();
            if (subTree.getRightNode() == null || subTree.getRightNode() == lastNode) {
                visted(subTree);
                subTree = stack.pop();
                lastNode = subTree;
                subTree = null;
            } else {
                subTree = subTree.getRightNode();
            }
        }
    }

    /**
     * 层次遍历(队列实现)
     * 
     * @param subTree
     */
    public void levelTraverse(BinNode subTree) {
        if (subTree == null)
            return;
        Queue> queue = new LinkedBlockingQueue<>();
        queue.add(subTree);
        while (!queue.isEmpty()) {
            BinNode binNode = queue.poll();
            if (binNode != null) {
                visted(binNode);
                if (binNode.getLeftNode() != null)
                    queue.add(binNode.getLeftNode());
                if (binNode.getRightNode() != null)
                    queue.add(binNode.getRightNode());
            }
        }
    }

    public static void main(String[] args) {
        BinTree binTree = new BinTree<>(new BinNode(A));
        /**
         * 创建一棵二叉树
         * 
         *
         *  
         *           A 
         *     B          C 
         *  D     E            F
         * 
* */ BinNode rootNode = binTree.getRoot(); BinNode nodeB = new BinNode<>(B); BinNode nodeC = new BinNode<>(C); BinNode nodeD = new BinNode<>(D); BinNode nodeE = new BinNode<>(E); BinNode nodeF = new BinNode<>(F); rootNode.setLeftNode(nodeB); rootNode.setRightNode(nodeC); nodeB.setLeftNode(nodeD); nodeB.setRightNode(nodeE); nodeC.setRightNode(nodeF); System.out.println(*******先序遍历(递归形式)*******); binTree.preOrderTraverse(rootNode); System.out.println(*******中序遍历(递归形式)*******); binTree.middleOrderTraverse(rootNode); System.out.println(*******后序遍历(递归形式)*******); binTree.postOrderTraverse(rootNode); System.out.println(*******先序遍历(非递归形式)*******); binTree.nrPreOrderTraverse(rootNode); System.out.println(*******中序遍历(非递归形式)*******); binTree.nrMiddleOrderTraverse(rootNode); System.out.println(*******后序遍历(非递归形式)*******); binTree.nrPostOrderTraverse(rootNode); System.out.println(*******层次遍历(队列实现)*******); binTree.levelTraverse(rootNode); System.out.println(**********我是分割线**********); System.out.println(该二叉树的高度为: + binTree.getHeight()); System.out.println(该二叉树的size为: + binTree.getSize()); } }
/**
 * 表示树节点的类
 * 
 * @author xdsjs
 *
 * @param 
 *            结点数据域类型
 */
public class BinNode {

    private BinNode leftNode;// 左结点
    private BinNode rightNode;// 右结点
    private T dataValue;// 数据域

    public BinNode() {
    }

    public BinNode(T dataValue) {
        super();
        this.dataValue = dataValue;
    }

    public BinNode(BinNode leftNode, BinNode rightNode, T dataValue) {
        this.leftNode = leftNode;
        this.rightNode = rightNode;
        this.dataValue = dataValue;
    }

    public BinNode getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(BinNode leftNode) {
        this.leftNode = leftNode;
    }

    public BinNode getRightNode() {
        return rightNode;
    }

    public void setRightNode(BinNode rightNode) {
        this.rightNode = rightNode;
    }

    public T getData() {
        return dataValue;
    }

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

}

 

Tags:

文章评论

最 近 更 新
热 点 排 行
Js与CSS工具
代码转换工具

<