频道栏目
首页 > 程序开发 > 移动开发 > 其他 > 正文
数据结构与算法之二叉树建立与遍历
2016-10-29 10:12:15         来源:chenliguan的博客  
收藏   我要投稿

1 概念

1 二叉树是一种非常重要的数据结构,它同时具有数组和链表各自的特点:它可以像数组一样快速查找,也可以像链表一样快速添加。但是他也有自己的缺点:删除操作复杂。

(1)二叉树:是每个结点最多有两个子树的有序树,在使用二叉树的时候,数据并不是随便插入到节点中的,一个节点的左子节点的关键值必须小于此节点,右子节点的关键值必须大于或者是等于此节点,所以又称二叉查找树、二叉排序树、二叉搜索树。

(2)完全二叉树:若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h层有叶子结点,并且叶子结点都是从左到右依次排布,这就是完全二叉树。

(3)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

(4) 深度——二叉树的层数,就是深度。

2 二叉树的特点总结:

(1)树执行查找、删除、插入的时间复杂度都是O(logN)

(2)遍历二叉树的方法包括前序、中序、后序

(3)非平衡树指的是根的左右两边的子节点的数量不一致

(4) 在非空二叉树中,第i层的结点总数不超过 , i>=1;

(5)深度为h的二叉树最多有个结点(h>=1),最少有h个结点;

(6)对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;

package Tree;

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

public class BinaryTree {

    private TreeNode root = null;
    public static String[] str;
    public static int count;

    public BinaryTree() {
        root = new TreeNode(1, "A");
    }

    /**
     * 构建二叉树 A B C D E F
     */
    public void createBinaryTree() {
        TreeNode nodeB = new TreeNode(2, "B");
        TreeNode nodeC = new TreeNode(3, "C");
        TreeNode nodeD = new TreeNode(4, "D");
        TreeNode nodeE = new TreeNode(5, "E");
        TreeNode nodeF = new TreeNode(6, "F");
        root.leftChild = nodeB;
        root.rightChild = nodeC;
        nodeB.leftChild = nodeD;
        nodeB.rightChild = nodeE;
        nodeC.rightChild = nodeF;
    }

    /**
     * 根据前序序列递归构建二叉树
     */
    public TreeNode createBinaryTree(ArrayList data) {
        return createBinaryTree(data.size(),data);
    }

    public TreeNode createBinaryTree(int size, ArrayList data) {
        if (data.size() == 0) {
            return null;
        }
        String d = data.get(0);
        TreeNode node = null;
        int index = size - data.size();//获取节点下标
        if (d.equals("#")) {
            node = null;
            data.remove(0);// 删除“#”
            return node;//退出
        }
        node = new TreeNode(index, d);// 创建新节点
        if (index == 0) {
            root = node;// 创建根节点
        }
        data.remove(0);
        node.leftChild = createBinaryTree(size, data);
        node.rightChild = createBinaryTree(size, data);
        return node;
    }

    /**
     * 求二叉树的高度
     */
    public int getHeight() {
        return getHeight(root);
    }

    private int getHeight(TreeNode node) {
        if (node == null) {
            return 0;
        } else {
            int i = getHeight(node.leftChild);
            int j = getHeight(node.rightChild);
            return (i < j) ? j + 1 : i + 1;
        }
    }

    /**
     * 获取二叉树的结点数
     */
    public int getSize() {
        return getSize(root);
    }

    private int getSize(TreeNode node) {
        if (node == null) {
            return 0;
        } else {
            return 1 + getSize(node.leftChild) + getSize(node.rightChild);
        }
    }

    /**
     * 前序遍历——迭代
     * 
     * 规则是若二叉树为空,则空操作返回;否则先访问根结点,然后前序遍历左子树,再前序遍历右子树(根左右)
     */
    public void preOrder(TreeNode node) {
        if (node == null) {
            return;
        } else {
            System.out.println("前序遍历——迭代:" + node.getData());
            preOrder(node.leftChild);
            preOrder(node.rightChild);
        }
    }

    /**
     * 中序遍历——迭代
     * 
     * 规则是若树为空,则空操作返回,否则从根结点开始(注意并不是先访问根结点),中序遍历根结点的左子树,然后是访问根结点,最后中序遍历右子树(左根右)
     */
    public void midOrder(TreeNode node) {
        if (node == null) {
            return;
        } else {
            midOrder(node.leftChild);
            System.out.println("中序遍历——迭代:" + node.getData());
            midOrder(node.rightChild);
        }
    }

    /**
     * 后序遍历——迭代
     * 
     * 规则是若树为空,则空操作返回,否则从左到右先叶子后结点的方式遍历访问左右子树,最后是访问根结点(左到右先叶子后结点)
     */
    public void postOrder(TreeNode node) {
        if (node == null) {
            return;
        } else {
            postOrder(node.leftChild);
            postOrder(node.rightChild);
            System.out.println("后序遍历——迭代:" + node.getData());
        }
    }

    /**
     * 前序遍历——非迭代
     */
    public void theFirstTraversal_Stack(TreeNode root) { // 先序遍历
        Stack stack = new Stack();
        TreeNode node = root;
        while (node != null || stack.size() > 0) { // 将所有左孩子压栈
            if (node != null) { // 压栈之前先访问
                System.out.println("前序遍历——非迭代:" + node.getData());
                stack.push(node);
                node = node.leftChild;
            } else {
                node = stack.pop();
                node = node.rightChild;
            }
        }
    }

    /**
     * 中序遍历——非迭代
     */
    public void theInOrderTraversal_Stack(TreeNode root) { // 中序遍历
        Stack stack = new Stack();
        TreeNode node = root;
        while (node != null || stack.size() > 0) {
            if (node != null) {
                stack.push(node); // 直接压栈
                node = node.leftChild;
            } else {
                node = stack.pop(); // 出栈并访问
                System.out.println("中序遍历——非迭代:" + node.getData());
                node = node.rightChild;
            }
        }
    }

    /**
     * 后序遍历——非迭代
     * 
     */
    public void thePostOrderTraversal_Stack(TreeNode root) { // 后序遍历
        Stack stack = new Stack();
        Stack output = new Stack();// 构造一个中间栈来存储逆后序遍历的结果
        TreeNode node = root;
        while (node != null || stack.size() > 0) {
            if (node != null) {
                output.push(node);
                stack.push(node);
                node = node.rightChild;// 遍历右子树
            } else {
                node = stack.pop();
                node = node.leftChild;// 遍历左子树
            }
        }
        while (output.size() > 0) {
            System.out.println("后序遍历——非迭代:" + output.pop().getData());
        }
    }

    public class TreeNode {
        private int index;
        private String data;
        private TreeNode leftChild;
        private TreeNode rightChild;
        private TreeNode parent;

        public int getIndex() {
            return index;
        }

        public void setIndex(int index) {
            this.index = index;
        }

        public String getData() {
            return data;
        }

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

        public TreeNode getLeftChild() {
            return leftChild;
        }

        public void setLeftChild(TreeNode leftChild) {
            this.leftChild = leftChild;
        }

        public TreeNode getRightChild() {
            return rightChild;
        }

        public void setRightChild(TreeNode rightChild) {
            this.rightChild = rightChild;
        }

        public TreeNode getParent() {
            return parent;
        }

        public void setParent(TreeNode parent) {
            this.parent = parent;
        }

        public TreeNode(int index, String data) {
            this.index = index;
            this.data = data;
            this.leftChild = null;
            this.rightChild = null;
        }
    }

    public static void main(String[] args) {
//      BinaryTree binaryTree = new BinaryTree();
//      binaryTree.createBinaryTree();

        ArrayList data = new ArrayList<>();
        String[] dataArray = new String[]{"A","B","D","#","#","E","#","#","C","#","F","#","#"}; 
        for(String d:dataArray){ 
            data.add(d);
        }
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.createBinaryTree(data);//创建二叉树

        int height = binaryTree.getHeight();//求二叉树的高度
        System.out.println("treeHeihgt:" + height);

        int size = binaryTree.getSize();//获取二叉树的结点数
        System.out.println("treeSize:" + size);

//       binaryTree.preOrder(binaryTree.root);//前序遍历-迭代
        // binaryTree.midOrder(binaryTree.root);//中序遍历-迭代
        // binaryTree.postOrder(binaryTree.root);//后序遍历-迭代

        binaryTree.theFirstTraversal_Stack(binaryTree.root);// 前序遍历-非迭代
        System.out.println("\n");
        binaryTree.theInOrderTraversal_Stack(binaryTree.root);// 中序遍历-非迭代
        System.out.println("\n");
        binaryTree.thePostOrderTraversal_Stack(binaryTree.root);// 后序遍历-非迭代
    }
}
点击复制链接 与好友分享!回本站首页
相关TAG标签 数据结构 算法
上一篇:拼图游戏-从基础到应用玩转手势变化
下一篇:(32位)arm 汇编学习(2)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站