二叉树

package com.weeks.tree;

/**
 * @author 达少
 * @version 1.0
 *
 * 实现二叉树数据结构
 */
public class BinaryTreeDemo 
    public static void main(String[] args) 
        //定义二叉树
        BinaryTree binaryTree = new BinaryTree();
        //定义二叉树的节点对象
        HeroNode node1 = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "吴用");
        HeroNode node3 = new HeroNode(3, "卢俊义");
        HeroNode node4 = new HeroNode(4, "林冲");
        HeroNode node5 = new HeroNode(5, "关胜");
        //这里先使用手动创建二叉树，以后可以使用递归方式创建
        binaryTree.setRoot(node1);
        node1.setLeft(node2);
        node1.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);

        //测试前序遍历
//        System.out.println("前序遍历");
//        binaryTree.preOrder();//1,2,3,5,4

        //测试中序遍历
//        System.out.println("中序遍历");
//        binaryTree.infixOrder();//2,1,5,3,4

        //测试后续遍历
//        System.out.println("后续遍历");
//        binaryTree.postOrder();//2,5,4,3,1

        //测试前序查找
//        HeroNode resNode = binaryTree.preOrderSearch(5);
//        HeroNode resNode = binaryTree.infixOrderSearch(5);
//        HeroNode resNode = binaryTree.postOrderSearch(5);
//        if(resNode != null)
//            System.out.printf("找到了结点id = %d, name = %s\\n", resNode.getNo(), resNode.getName());
//        else
//            System.out.println("没有找到要查找的结点！！！");
//        

        System.out.println("删除前的二叉树（前序遍历）");
        binaryTree.preOrder();
        //删除no=5的结点
        binaryTree.delNode(5);
        System.out.println("删除后的二叉树（前序遍历）");
        binaryTree.preOrder();
    


//定义二叉树类
class BinaryTree
    private HeroNode root;//根结点

    public HeroNode getRoot() 
        return root;
    

    public void setRoot(HeroNode root) 
        this.root = root;
    

    //前序遍历
    public void preOrder()
        if(root == null)
            return;
        
        root.preOrder();
    

    //中序遍历
    public void infixOrder()
        if(root == null)
            return;
        
        root.infixOrder();
    

    //后序遍历
    public void postOrder()
        if(root == null)
            return;
        
        root.postOrder();
    

    //前序查找
    public HeroNode preOrderSearch(int no)
        if(root == null)
            return null;
        
        return root.preOrderSearch(no);
    

    //中序查找
    public HeroNode infixOrderSearch(int no)
        if(root == null)
            return null;
        
        return root.infixOrderSearch(no);
    

    //后序查找
    public HeroNode postOrderSearch(int no)
        if(root == null)
            return null;
        
        return root.postOrderSearch(no);
    

    //删除结点
    public void delNode(int no)
        //判断二叉树是否为空
        if(root == null)
            return;
        
        //判断根节点是否符合删除条件，符合则将整棵树置空后返回
        if(root.getNo() == no)
            root = null;
            return;
        else//否则执行HeroNode中的delNode操作
            root.delNode(no);
        
    


//定义树的结点对象类
class HeroNode
    private int no;
    private String name;
    private HeroNode left;
    private HeroNode right;

    public HeroNode(int no, String name)
        this.no = no;
        this.name = name;
    

    public int getNo() 
        return no;
    

    public void setNo(int no) 
        this.no = no;
    

    public String getName() 
        return name;
    

    public void setName(String name) 
        this.name = name;
    

    public HeroNode getLeft() 
        return left;
    

    public void setLeft(HeroNode left) 
        this.left = left;
    

    public HeroNode getRight() 
        return right;
    

    public void setRight(HeroNode right) 
        this.right = right;
    

    @Override
    public String toString() 
        return "HeroNode" +
                "no=" + no +
                ", name='" + name + '\\'' +
                '';
    

    //前序遍历
    public void preOrder()
        //先输出当前结点
        System.out.println(this);
        //递归遍历左子树
        if(this.left != null)
            this.left.preOrder();
        
        //递归遍历右子树
        if(this.right != null)
            this.right.preOrder();
        
    

    //中序遍历
    public void infixOrder()
        //递归遍历左子树
        if(this.left != null)
            this.left.infixOrder();
        
        //输出当前结点
        System.out.println(this);
        //递归遍历右子树
        if(this.right != null)
            this.right.infixOrder();
        
    

    //后序遍历
    public void postOrder()
        //递归遍历左子树
        if(this.left != null)
            this.left.postOrder();
        
        //递归遍历右子树
        if(this.right != null)
            this.right.postOrder();
        
        //输出当前结点
        System.out.println(this);
    

    //前序查找
    /**
     *
     * @param no 需要查找的编号
     * @return 找到就返回该结点，否则返回null
     */
    public HeroNode preOrderSearch(int no)
        //判断该结点是否为查找的结点
        if(this.no == no)
            return this;//找到就返回该结点
        

        HeroNode resNode = null;
        //如果不是当前结点就递归左子树查找
        if(this.left != null)
            resNode = this.left.preOrderSearch(no);
        
        //如果在左子树找到就返回
        if(resNode != null)
            return resNode;
        

        //在左子树没有找到，那么向右子树查找
        if(this.right != null)
            resNode = this.right.preOrderSearch(no);
        

        //无论找没找到最后返回
        return resNode;//返回不为空就是找打了，返回空就是没有找到
    

    //中序查找
    public HeroNode infixOrderSearch(int no)
        HeroNode resNode = null;
        //向左子树递归查找
        if(this.left != null)
            resNode = this.left.infixOrderSearch(no);
        
        //如果在左子树找到则返回
        if(resNode != null)
            return resNode;
        

        //判断该节点是否为查找的结点
        if(this.no == no)
            return this;
        

        //向左右子树遍历查找
        if(this.right != null)
            resNode = this.right.infixOrderSearch(no);
        
        return resNode;
    

    //后序查找
    public HeroNode postOrderSearch(int no)
        HeroNode resNode = null;
        //向左子树递归查找
        if(this.left != null)
            resNode = this.left.postOrderSearch(no);
        
        //如果在左子树找到则返回
        if(resNode != null)
            return resNode;
        
        //向左右子树遍历查找
        if (this.right != null)
            resNode = this.right.postOrderSearch(no);
        
        //判断该节点是否为查找的结点
        if(this.no == no)
            return this;
        
        return resNode;
    

    //删除结点
    /**
     * 约定：
     * 如果删除的是叶子结点，则直接删除
     * 如果不是也只结点直接删除以该节点为父节点的子树
     */
    public void delNode(int no)
        /**
         * 1.因为要现在创建的二叉树是单向的，要删除只能找到父节点分别判断左右结点是否符合
         *   删除的条件，所以首先判断左子树是否有符合删除的条件的结点，递归实现
         * 2.接下来是递归判断右子树中是否有符合删除条件的结点
         */
        //判断该节点是否有左子树并判断左子树是否符合删除条件
        if(this.left != null && this.left.no == no)
            //如果左子树符合删除条件，将左子树置空，并返回
            this.left = null;
            return;
        
        //判断该节点是否有右子树并判断右子树是否符合删除条件
        if(this.right != null && this.right.no == no)
            //如果右子树符合删除条件，将右子树置空，并返回
            this.right = null;
            return;
        
        //递归判断左子树
        if(this.left != null)
            this.left.delNode(no);
        

        //递归判断右子树
        if(this.right != null)
            this.right.delNode(no);
        
    

顺序存储二叉树

package com.weeks.tree;

import java.util.ArrayList;

/**
 * @author 达少
 * @version 1.0
 *
 * 顺序存储二叉树
 */
public class ArrayBinaryTreeDemo 
    public static void main(String[] args) 
        int[] arr = 1, 2, 3, 4, 5, 6, 7;
        ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(arr);
//        arrayBinaryTree.preOrder();
//        arrayBinaryTree.infixOrder();
        arrayBinaryTree.postOrder();
    


//顺序存储二叉树，就是使用数组存储二叉树，并保留前中后序遍历的特点
class ArrayBinaryTree
    private int[] arr;

    public ArrayBinaryTree(int[] arr)
        this.arr = arr;
    

    //前序遍历
    /**
     *
     * @param index 从数组的index下标开始遍历
     */
    public void preOrder(int index)
        //判断数组是否为空，为空则返回
        if(arr == null)
            return;
        
        //输出当前结点的值
        System.out.println(arr[index]);
        //递归遍历左子树，在数组中左子树的下标是(2 * index + 1)
        if((2 * index + 1) < arr.length)//要判断下标是否越界数组
            preOrder(2 * index + 1);
        
        //递归遍历左子树，在数组中左子树的下标是(2 * index + 2)
        if((2 * index + 2) < arr.length)
            preOrder(2 * index + 2);
        
    

    //我们一般都是从根节点开始遍历，所以一般index = 0
    //重载preOrder函数方便调用，不用传入参数
    public void preOrder()
        preOrder(0);
    

    //仿照前序遍历，写出中序遍历
    public void infixOrder(int index)
        if(arr == null)
            return;
        
        if((2 * index + 1) < arr.length)
            infixOrder(2 * index + 1);
        
        System.out.println(arr[index]);
        if((2 * index + 2) < arr.length)
            infixOrder(2 * index + 2);
        
    
    public void infixOrder()
        infixOrder(0);
    

    //后序遍历
    public void postOrder(int index)
        if(arr == null)
            return;
        
        if((2 * index + 1) < arr.length)
            postOrder(2 * index + 1);
        
        if((2 * index + 2) < arr.length)
            postOrder(2 * index + 2);
        
        System.out.println(arr[index]);
    
    public void postOrder()
        postOrder(0);
    

线索二叉树

package com.weeks.tree.threadedbinarytree;

/**
 * @author 达少
 * @version 1.0
 * 线索化二叉树
 */
public class ThreadedBinaryTreeDemo 
    public static void main(String[] args) 
        HeroNode node1 = new HeroNode(1, "tom");
        HeroNode node2 = new HeroNode(3, "jack");
        HeroNode node3 = new HeroNode(6, "smith");
        HeroNode node4 = new HeroNode(8, "milan");
        HeroNode node5 = new HeroNode(10, "adair");
        HeroNode node6 = new 
java数据结构与算法之二叉树的最大宽度和最大深度问题(代码片段)
①、最大深度问题求二叉树的最大深度，最常见的无非两种方式第一种是，以【宽度优先遍历】统计树的层数，树有多少层，那么树就有多高第二种是，以【深度优先遍历】，以我们上面讲的【二叉树通用...  查看详情  
                
java数据结构与算法之二叉树
二叉树树存储方式的分析能提高数据存储，读取的效率,比如利用二叉排序树(BinarySortTree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。树示意图:二叉树遍历的说明1)前序遍历:先输出父节点，再...  查看详情  
                
整理：数据结构与算法之二叉树(代码片段)
1、概述通过前面的学习，我们知道，有序数组可以利用二分查找法快速的查找特定的值，时间复杂度为O(log2N)，但是插入数据时很慢，时间复杂度为O(N)；链表的插入和删除速度都很快，时间复杂度为O(1...  查看详情  
                
数据结构与算法之二叉树——indart(代码片段)
用dart语言实现的二叉树，实现了插入、查找、删除，中序遍历、前序、后序遍历等功能。1classBinaryTree<EextendsComparable>2Node<E>_root;3int_nodeNumbers;45BinaryTree():_nodeNumbers=0;67factoryBinaryTree.from(Iterable<E>elements)8vartree=BinaryTree<...  查看详情  
                
数据结构之二叉树(代码片段)
1.二叉树的基本概念　　二叉树是一种非常常见并实用的数据结构，它结合了有序数组和链表的优点，在二叉树中查找数据与在数组中查找数据一样快，在二叉树中添加删除数据的速度与在链表中一样高效。　　二叉树也称为二...  查看详情  
                
javascript--数据结构与算法之二叉树
树是一种非线性的数据结构，以分层的方式存储数据。二叉树：查找非常快，而且二叉树添加或者删除元素也非常快。形象的可以描述为组织结构图，用来描述一个组织的结构。树是由边连接的点组成。树的一些基本概念：根节...  查看详情  
                
java数据结构与算法之二叉树的最大宽度和最大深度问题
①、最大深度问题求二叉树的最大深度，最常见的无非两种方式第一种是，以【宽度优先遍历】统计树的层数，树有多少层，那么树就有多高第二种是，以【深度优先遍历】，以我们上面讲的【二叉树通用...  查看详情  
                
java数据结构之二叉树(代码片段)
1、二叉树各功能模块介绍   1.1、创建二叉树          二叉树数据输入是广义表输入形式：A(B(C),D(E(F,G),H(,I)))。创建该二叉树使用的是非递归方式。整个流程为：A是根元素，B、D为A的子节点，所以输入A时&#x...  查看详情  
                
数据结构之二叉树(代码片段)
对象由指针所构成的关系有很多种，如果没有循环可以广义称为树，否则称为图。而二叉树是一种特殊的树形结构。常用与二叉树排序的应用。二叉树的定义： 每个结点最多有两个子树的结构称为二叉树。所以两个分叉可以...  查看详情  
                
数据结构与算法实验报告之二叉树高度的求解
数据结构与算法实验报告二叉树高度的求解      姓名：孙瑞霜  一、实验目的1、熟练掌握学习的每种结构及其相应算法；2、理论联系实际，会对现实问题建模并设计相应算法。3、优化算法，使得算...  查看详情  
                
数据结构与算法(java)之二叉排序树与avl树(代码片段)
二叉排序数packagecom.weeks.tree.binarysorttree;/***@author达少*@version1.0*二叉排序树：*每个结点的左子结点的值小于当前结点的值，右子结点的大于当前结点的值*如果有相同的值则放在左子结点或右子结点（下面的示例...  查看详情  
                
数据结构与算法实验报告之二叉树高度的求解
数据结构与算法实验报告二叉树高度的求解      姓名：孙瑞霜  一、实验目的1、熟练掌握学习的每种结构及其相应算法；2、理论联系实际，会对现实问题建模并设计相应算法。3、优化算法，使得算...  查看详情  
                
数据结构之二叉树(代码片段)
简述：二叉树是十分重要的数据结构，主要用来存放数据，并且方便查找等操作，在很多地方有广泛的应用。二叉树有很多种类，比如线索二叉树，二叉排序树，平衡二叉树等，本文写的是最基础最简单的二叉树。思路：二叉树...  查看详情  
                
java数据结构与算法之翻转二叉树(代码片段)
该题本来不是一个具有代表性的题目，其实质就是考了一个对于二叉树的遍历问题，但是由于在面试中我多次被问到该题，所以做一个记录。题目描述给你一棵二叉树的根节点root，翻转这棵二叉树，并返回其...  查看详情  
                
数据结构与算法学习笔记树(代码片段)
数据结构与算法学习笔记(7)树前情回顾文章目录数据结构与算法学习笔记(7)树一.树和二叉树的定义1.树树的定义树的基本术语树结构与线性结构比较2.二叉树二叉树的定义二叉树与树的差别二叉树基本形态3.树和二叉树的抽象数...  查看详情  
                
数据结构之二叉树(代码片段)
概要参考《大话数据结构》，把常用的基本数据结构梳理一下。本节介绍二叉树。?定义??二叉树（BinaryTree）是\(n\)（\(n\geqslant0\)）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、...  查看详情  
                
数据结构与算法:树顺序存储二叉树(代码片段)
...言,关注博主,底部附有完整代码工具:IDEA本系列介绍的是数据结构:树这是第二篇目前计划一共有12篇:二叉树入门顺序二叉树(本篇)线索化二叉树堆排序赫夫曼树(一)赫夫曼树(二)赫夫曼树(三)二叉排序树平衡二叉树2-3树,2-3-4树,B树B&#...  查看详情  
                
sdut3341数据结构实验之二叉树二：遍历二叉树(代码片段)
 数据结构实验之二叉树二：遍历二叉树TimeLimit: 1000ms MemoryLimit: 65536KiBProblemDescription已知二叉树的一个按先序遍历输入的字符序列，如abc,,de,g,,f,,, (其中,表示空结点)。请建立二叉树并按中序和后序的方式遍历该...  查看详情