java数据结构(四)

关于树的基本概念可以查看此篇文章树、堆、集合

1、一般树的实现：

树结构可以由递归实现，也可以由链表实现：
链表实现的单个节点的表示方法：

class TreeNode{
    Object element;  //节点的值
    TreeNode firstChild; //该节点的第一个子节点
    TreeNode nextSibling; //下一个兄弟节点
}

树的遍历：分为前序遍历、后续遍历，二叉树还有一种特殊的遍历方法（中序遍历）；
前序遍历：及对节点的处理，先于其子节点进行，其时间复杂度为O(n);
后序遍历：及对节点的处理，晚于其子节点进行，其时间复杂度为O(n);
[图片上传失败...(image-754579-1509972359621)]

前序遍历为：A-B-D-#-#-#-C-E-#-#-#

后序遍历为：#-#-D-#-B-#-#-E-#-C-A

2、二叉树的实现：

二叉树是一颗树，其每个节点都不能有多于两个的儿子；

其单个节点为：

    private static class BinaryNode<T>{
        T element;
        BinaryNode<T> leftBinaryNode;
        BinaryNode<T> rightBinaryNode;
        
        BinaryNode(T element){
            this.element=element;
        }

        public BinaryNode(T element, BinaryNode<T> leftBinaryNode, BinaryNode<T> rightBinaryNode) {
            this.element = element;
            this.leftBinaryNode = leftBinaryNode;
            this.rightBinaryNode = rightBinaryNode;
        }
        
    }

二叉搜索树的实现：


package tree;

import com.sun.jmx.remote.internal.ArrayQueue;

import java.nio.BufferUnderflowException;
import java.util.Queue;

public class myBinaryTree<T extends Comparable<? super T>> {
    private BinaryNode<T> root;
    public myBinaryTree(){
        root=null;
    }
    public boolean isEmpty(){
        return root==null;
    }
    public void makeEmpty(){
        root=null;
    }
    public boolean contains(T item){
        return contains(item,root);
    }

    private boolean contains(T item,BinaryNode<T> t){
        if(t==null){
            return false;
        }
        int compareValue=item.compareTo(t.element);
        if(compareValue<0){
            return contains(item,t.leftBinaryNode);
        }
        else if(compareValue>0){
            return contains(item,t.rightBinaryNode);
        }
        else {
            return true;
        }
    }


    public T findMin(){
        if(isEmpty())
            throw new BufferUnderflowException();
        return findMin(root).element;
    }
    private BinaryNode<T> findMin(BinaryNode<T> t){
        if(t==null){
            return null;
        }
        while (t.leftBinaryNode!=null){
            t=t.leftBinaryNode;
        }
        return t;
    }


    public T findMax(){
        if(isEmpty())
            throw new BufferUnderflowException();
        return findMax(root).element;
    }
    private BinaryNode<T> findMax(BinaryNode<T> t){
        if(t==null){
            return null;
        }
        while (t.rightBinaryNode!=null){
            t=t.rightBinaryNode;
        }
        return t;
    }

    public void insert(T item){
        root=insert(item,root);
    }
    private BinaryNode<T> insert(T item,BinaryNode<T> t){
        if(t==null){
            return new BinaryNode<T>(item,null,null);
        }
        int compareValue=item.compareTo(t.element);
        if(compareValue<0){
            t.leftBinaryNode=insert(item,t.leftBinaryNode);
        }
        else if(compareValue>0){
            t.rightBinaryNode=insert(item,t.rightBinaryNode);
        }
        else{
            ;
        }

        return t;
    }

    public int height(){
        if(isEmpty()){
            return 0;
        }
        else
            return height(root);
    }
    private int height(BinaryNode<T> t){
        if(t==null){
            return 0;
        }
        else
            return 1+Math.max(height(t.rightBinaryNode),height(t.leftBinaryNode));
    }


    public void printTreeNodeLast(){ //后序遍历
        if(isEmpty()){
            System.out.println("Tree is empty");
        }
        else {
            printTreeNodeLast(root);
        }
    }
    private void printTreeNodeLast(BinaryNode<T> t){
        if (t!=null){
            printTreeNodeLast(t.leftBinaryNode);
            printTreeNodeLast(t.rightBinaryNode);
            System.out.println(t.element);
        }
    }


    public void printTreeNodeFirst(){ //先序遍历
        if(isEmpty()){
            System.out.println("Tree is empty");
        }
        else {
            printTreeNodeFirst(root);
        }
    }
    private void printTreeNodeFirst(BinaryNode<T> t){
        if (t!=null){
            System.out.println(t.element);
            printTreeNodeFirst(t.leftBinaryNode);
            printTreeNodeFirst(t.rightBinaryNode);
        }
    }

    public void printTreeNodeMedu(){ //中序遍历
        if(isEmpty()){
            System.out.println("Tree is empty");
        }
        else {
            printTreeNodeMedu(root);
        }
    }
    private void printTreeNodeMedu(BinaryNode<T> t){
        if (t!=null){
            printTreeNodeMedu(t.leftBinaryNode);
            System.out.print(t.element);
            printTreeNodeMedu(t.rightBinaryNode);
        }
    }

    public void printTree(){ //层序遍历
        if(isEmpty()){
            System.out.println("Tree is empty");
        }
        else {
            printTree(root);
        }
    }
    private void printTree(BinaryNode<T> t){
        ArrayQueue<BinaryNode<T>> arrayQueue=new ArrayQueue<>(height());
        if(t==null){
            System.out.println("Tree is empty");
        }
        arrayQueue.add(t);
        while (!arrayQueue.isEmpty()){
            BinaryNode<T> binaryNode=arrayQueue.remove(0);
            System.out.println(binaryNode.element);
            if(binaryNode.leftBinaryNode!=null){
                arrayQueue.add(binaryNode.leftBinaryNode);
            }
            if(binaryNode.rightBinaryNode!=null){
                arrayQueue.add(binaryNode.rightBinaryNode);
            }
        }
    }

    public void remove(T item){
        root=remove(item,root);
    }
    private BinaryNode<T> remove(T item,BinaryNode<T> t){
       if(t==null){
           return null;
       }
       int comparaValue=item.compareTo(t.element);
       if(comparaValue>0){
           t.rightBinaryNode=remove(item,t.rightBinaryNode);
       }
       else if(comparaValue<0) {
           t.leftBinaryNode=remove(item,t.leftBinaryNode);
       }
       else {
           if(t.rightBinaryNode!=null&&t.leftBinaryNode!=null){
               t.element=findMin(t.rightBinaryNode).element;
               t.rightBinaryNode=remove(t.element,t.rightBinaryNode);
           }
           else {
               t=(t.leftBinaryNode!=null)?t.leftBinaryNode:t.rightBinaryNode;
           }
       }
        return t;
    }

    private static class BinaryNode<T>{
        T element;
        BinaryNode<T> leftBinaryNode;
        BinaryNode<T> rightBinaryNode;

        BinaryNode(T element){
            this.element=element;
        }

        public BinaryNode(T element, BinaryNode<T> leftBinaryNode, BinaryNode<T> rightBinaryNode) {
            this.element = element;
            this.leftBinaryNode = leftBinaryNode;
            this.rightBinaryNode = rightBinaryNode;
        }

    }
}

3、AVL树
带有自平衡调整的二叉查找树，其要求每个节点的左右子节点的高度差，相差不超过1；


package tree;

import com.sun.org.apache.xerces.internal.impl.xpath.regex.Match;

import java.nio.BufferUnderflowException;

public class myAvlTree<T extends Comparable<? super T>> {
    private static final int ALLOWED_HEIGHT=1;
    private AvlNode<T> root;

    public myAvlTree(){
        root=null;
    }

    public boolean isEmpty(){
        return root==null;
    }
    public void insert(T item){
        root=insert(item,root);
    }


    public T findMin(){
        if(isEmpty())
            throw new BufferUnderflowException();
        return findMin(root).element;
    }
    private AvlNode<T> findMin(AvlNode<T> t){
        if(t==null){
            return null;
        }
        while (t.left!=null){
            t=t.left;
        }
        return t;
    }
    private AvlNode<T> insert(T item,AvlNode<T> t){
        if(t==null){
            return new AvlNode<T>(item,null,null);
        }
        int comparaValue=item.compareTo(t.element);
        if(comparaValue>0){
            t.right=insert(item,t.right);
        }
        else if(comparaValue<0){
            t.left=insert(item,t.left);
        }
        else
            ;
        return balance(t);
    }

    public void remove(T x){
        if(isEmpty()){
            System.out.println("tree is empty");
            throw new BufferUnderflowException();
        }
        remove(x,root);
    }
    private AvlNode<T> remove(T x,AvlNode<T> t){
        if(t==null){
            return null;
        }
        int comparaVaule=x.compareTo(t.element);
        if(comparaVaule>0){
            t.right=remove(x,t.right);
        }
        else if(comparaVaule<0){
            t.left=remove(x,t.left);
        }
        else if(t.left!=null&&t.right!=null){
            t.element=findMin(t.right).element;
            t.right=remove(t.element,t.left);
        }
        else {
            t=(t.left!=null)?t.left:t.right;
        }
        return t;
    }
    private AvlNode<T> balance(AvlNode<T> t){
        if(t==null){
            return t;
        }
        if(height(t.left)-height(t.right)>ALLOWED_HEIGHT){
            if(height(t.left.left)>=height(t.left.right)){
                t=rotateWithLeftChild(t);
            }
            else{
                t=doubleWithLeftChild(t);
            }
        }
        else if(height(t.right)-height(t.left)>ALLOWED_HEIGHT){
            if(height(t.right.right)>=height(t.right.left)){
                t=rotateWithRightChild(t);
            }
            else {
                t=doubleWithRightChild(t);
            }
        }
        t.height=Math.max(height(t.left),height(t.right))+1;
        return t;
    }
    private AvlNode<T> rotateWithLeftChild(AvlNode<T> k2){
        AvlNode<T> k1=k2.left;
        k2.left=k1.right;
        k1.right=k2;
        k2.height= Math.max(height(k2.left),height(k2.right))+1;
        k1.height=Math.max(height(k1.left),k2.height)+1;
        return k1;
    }
    private AvlNode<T> doubleWithLeftChild(AvlNode<T> k2){
        k2.left=rotateWithRightChild(k2.left);
        return rotateWithLeftChild(k2);
    }
    private AvlNode<T> rotateWithRightChild(AvlNode<T> k1){
        AvlNode<T> k2=k1.right;
        k1.right=k2.left;
        k2.left=k1;
        k1.height=Math.max(height(k1.right),k1.height);
        k2.height=Math.max(k1.height,height(k2.right))+1;
        return k2;
    }
    private AvlNode<T> doubleWithRightChild(AvlNode<T> k2){
        k2.right=rotateWithLeftChild(k2.left);
        return rotateWithRightChild(k2);
    }


    private int height(AvlNode<T> t){ //计算AVL树的高度；
        return t==null?-1:t.height;
    }

    public void printTree(){ //后序遍历
        if(isEmpty()){
            System.out.println("Tree is empty");
        }
        else {
            printTree(root);
        }
    }
    private void printTree(AvlNode<T> t){
        if (t!=null){
            printTree(t.left);
            printTree(t.right);
            System.out.println(t.element);
        }
    }

    public void printTreelast(){ //先序遍历
        if(isEmpty()){
            System.out.println("Tree is empty");
        }
        else {
            printTreelast(root);
        }
    }
    private void printTreelast(AvlNode<T> t){
        if (t!=null){
            System.out.println(t.element);
            printTreelast(t.left);
            printTreelast(t.right);

        }
    }


    public void printTreemd(){ //中序遍历
        if(isEmpty()){
            System.out.println("Tree is empty");
        }
        else {
            printTreemd(root);
        }
    }
    private void printTreemd(AvlNode<T> t){
        if (t!=null){
            printTreemd(t.left);
            System.out.println(t.element);
            printTreemd(t.right);

        }
    }

    private static class AvlNode<T>{
        T element;
        AvlNode<T> left;
        AvlNode<T> right;
        int height; //height
        AvlNode(T element){
            this.element=element;
        }
        public AvlNode(T element, AvlNode<T> left, AvlNode<T> right) {
            this.element = element;
            this.left = left;
            this.right = right;
            height=0;
        }

    }
}


 public static void main(String[] args){
        myAvlTree<Integer> myAvlTree=new myAvlTree<>();
        Integer[] integer={10,3,5,9,8,7,0,4};
        for(Integer ints:integer){
            myAvlTree.insert(ints);
        }
        System.out.println("中序");
        myAvlTree.printTreemd();
    }
    
    
中序
0
3
4
5
7
8
9
10

最后编辑于：2017.12.11 09:13:37

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 206,839评论 6赞 482
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 88,543评论 2赞 382
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 153,116评论 0赞 344
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 55,371评论 1赞 279
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 64,384评论 5赞 374
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,111评论 1赞 285
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,416评论 3赞 400
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,053评论 0赞 259
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,558评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,007评论 2赞 325
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,117评论 1赞 334
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,756评论 4赞 324
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,324评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,315评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,539评论 1赞 262
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,578评论 2赞 355
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,877评论 2赞 345

java数据结构(四)

推荐阅读更多精彩内容