树结构的自定义及基本算法（Java数据结构学习笔记）

数据结构可以归类两大类型：线性结构与非线性结构，本文的内容关于非线性结构：树的基本定义及相关算法。关于树的一些基本概念定义可参考：维基百科
树的ADT模型：
根据树的定义，每个节点的后代均构成一棵树树，称为子树。因此从数据类型来讲，树、子树、树节点是等同地位，可将其看作为一个节点，用通类：Tree表示。如下图所示：

图：Tree ADT模型示意图
可采用“父亲-儿子-兄弟”模型来表示树的ADT。如图所示，除数据项外，分别用三个引用表示指向该节点的父亲，儿子，兄弟。

表：树ADT实现的操作

就对树的更新操作而言，不同的应用问题会要求树结构提供不同方法。这方面的差异太大，无法在树 ADT 中定义出通用的更新操作。在之后将结合各种应用问题，陆续给出一些具体的更新操作的实现。

树的java接口：

            
                package com.tree;

/**
 * Java Structure for Tree
 * Construct interface Tree
 * @author gannyee
 *
 */publicinterfaceTree {//Get size of tree which recent node as parentpublicintgetSize();

    //Get height of recent nodepublicintgetHeight();

    //Get depth of recent nodepublicintgetDepth();

    //Get element of recent nodepublic Object getElement();

    //Set element of recent node, return former elementpublic Object setElement(Object newElement);

    //Get parent of recent nodepublic TreeLinkedList getParent();

    //Get first child of recent nodepublic TreeLinkedList getFirstChild();

    //Get biggest sibling of recent nodepublic TreeLinkedList getNextSibling();
}

        

Java代码：树节点模型实现

            
                package com.tree;

import java.lang.reflect.Constructor;

publicclassTreeLinkedListimplementsTree{//Pointer point to parentprivate TreeLinkedList parent;
    //Elementprivate Object element;
    //Pointer point to firstChildprivate TreeLinkedList firstChild;
    //Pointer point to nextSiblingprivate TreeLinkedList nextSibling;

    //ConstructorpublicTreeLinkedList(){
        this(null,null,null,null);
    }

    //Constructor with parameterspublicTreeLinkedList(TreeLinkedList p, Object e,TreeLinkedList f,TreeLinkedList n){
        this.parent = p;
        this.element = e;
        this.firstChild = f;
        this.nextSibling = n;
    }
    //Get size of tree which recent node as parentpublicintgetSize(){
        int size = 1; //Recent node also include own children
        TreeLinkedList subTree = firstChild;//Start with first childwhile(null != subTree){
            size += subTree.getSize(); 
            subTree = subTree.getNextSibling();//Get all descendants
        }
        return size;
    }

    //Get height of recent nodepublicintgetHeight(){
        int height = -1;//Recent node‘s(parent) height
        TreeLinkedList subTree = firstChild;//Start with first childwhile(null != subTree){
            height = Math.max(height, subTree.getHeight());//Get the max height
            subTree = subTree.getNextSibling();
        }
        return height + 1;//Get recent node height
    }

    //Get depth of recent nodepublicintgetDepth(){
        int depth = 0;
        TreeLinkedList p = parent;//Start with parentwhile(p != null){
            depth ++;
            p = p.getParent();//Get all parents of every node
        }
        return depth;
    }

    //Get element of recent node,if nothing return nullpublic Object getElement(){
        returnthis.element;
    }

    //Set element of recent node,return former elementpublic Object setElement(Object newElement){
        Object swap;
        swap = this.element;
        this.element = newElement;
        returnthis.element;
    }

    //Get parent of recent node,if nothing return nullpublic TreeLinkedList getParent(){
        return parent;
    }

    //Get first child of recent node,if nothing return nullpublic TreeLinkedList getFirstChild(){
        return firstChild;
    }

    //Get biggest sibling of recent node,if nothing return nullpublic TreeLinkedList getNextSibling(){
        return nextSibling;
    }
}

        

测试代码：

            package com.tree;

publicclass TreeTest {

    /**
     * @param args
     */publicstaticvoidmain(String[] args) {
        // TODO Auto-generated method stub

        TreeLinkedList a = new TreeLinkedList();
        TreeLinkedList b = new TreeLinkedList();
        TreeLinkedList c = new TreeLinkedList();
        TreeLinkedList d = new TreeLinkedList();
        TreeLinkedList e = new TreeLinkedList();
        TreeLinkedList f = new TreeLinkedList();
        TreeLinkedList g = new TreeLinkedList();

        a = new TreeLinkedList(null,0,d,null);
        b = new TreeLinkedList(a,1,d,c.getFirstChild());
        c = new TreeLinkedList(a,2,null,null);
        d = new TreeLinkedList(b,3,f,e.getFirstChild());
        e = new TreeLinkedList(b,4,null,null);
        f = new TreeLinkedList(d,5,null,g.getFirstChild());
        g = new TreeLinkedList(d,6,null,null);

        System.out.println(a.getDepth());
        System.out.println(b.getDepth());
        System.out.println(c.getDepth());
        System.out.println(d.getDepth());
        System.out.println(e.getDepth());
        System.out.println(f.getDepth());

        System.out.println(a.getHeight());
        System.out.println(b.getHeight());
        System.out.println(c.getHeight());
        System.out.println(d.getHeight());
        System.out.println(e.getHeight());
        System.out.println(f.getHeight());
        System.out.println(g.getHeight());

    }

}

        

测试结果：

            
                0
                1
                2
                com
                .tree
                .TreeLinkedList
                @7c1c8c58
1
null
null

        

后续将给出关于树的遍历算法！

参考文献：数据结构与算法（ Java 描述）邓俊辉 著

版权声明：本文为博主原创文章，未经博主允许不得转载。个人github代码空间：https://github.com/gannyee