普通树简介以及Java代码实现

  1. 树相关的概念


    tree01.png

    根节点：没有父节点的节点(图中A、1)
    叶子节点：没有子节点的节点(图中B、D、3、5)
    普通节点：有子节点的节点(图中C、2、4)
    节点的度(degree)：节点拥有的子树的个数称为该节点的度(例如，C节点的度为2，2节点的度为3)
    树的度：树中所有节点的度的最大值(例如，左边的树的度为3)
    节点的层次(level)：节点的层次从根开始算起，根的层次为1，其余节点的层次值为其父节点的层次值加1
    数的深度(depth)：树中节点的最大层次值称为树的深度(例如，左边的树的深度为3，右边的树的深度为4)
    森林：两颗或两颗以上互不相交的树的集合

  2. 用代码实现表示一棵树的方法


    tree02.png

    范例树
    (1) 父节点表示法

数组索引 data parent
0 A -1
1 B 0
2 C 0
3 D 0
4 E 1
5 F 3
6 G 3
7 H 4
8 I 4
9 J 4
10 K 6

以下程序采用父节点表示法实现了一棵树：

import java.util.ArrayList;
import java.util.List;

/**
 * @Description: 使用父节点表示法实现一棵树
 * @author Jed
 * @date 2018年1月31日
 * @param <E>
 */
public class TreeParent<E> {
    
    public static class Node<T> {
        
        T data; // 节点中存放的数据
        int parent; // 节点的父节点的索引
        
        public Node() {}
        
        public Node(T data) {
            this.data = data;
        }
        
        public Node(T data, int parent) {
            this.data = data;
            this.parent = parent;
        }
        
        @Override
        public String toString() {
            return "TreeParent$Node [data=" + data + ", parent=" + parent + "]";
        }
    }
    
    private final int DEFAULT_TREE_SIZE = 100; // 默认的树的大小
    private int treeSize = 0;
    private Node<E>[] nodes; // 使用一个Node[]数组来记录该树中的所有节点
    private int nodeNums; // 记录节点数
    
    /**
     * 指定根节点创建树
     */
    public TreeParent(E data) {
        treeSize = DEFAULT_TREE_SIZE;
        nodes = new Node[treeSize];
        nodes[0] = new Node<E>(data, -1);
        nodeNums++;
    }
    
    /**
     * 指定根节点、指定treeSize创建树
     */
    public TreeParent(E data, int treeSize) {
        this.treeSize = treeSize;
        nodes = new Node[treeSize];
        nodes[0] = new Node<E>(data, -1);
        nodeNums++;
    }
    
    /**
     * 获取某个节点的索引值
     */
    public int getNodeIndex(Node node) {
        for(int i = 0; i < treeSize; i++) {
            // 找到指定节点
            if(nodes[i] == node) {
                return i;
            }
        }
        return -1;
    }
    
    /**
     * 为指定节点添加子节点
     */
    public void addNode(E data, Node parent) {
        for(int i = 0; i < treeSize; i++) {
            if(nodes[i] == null) {
                // 创建新节点，并用指定的数组元素保存它
                nodes[i] = new Node(data, getNodeIndex(parent));
                nodeNums++;
                return;
            }
        }
        throw new RuntimeException("该树已满，无法添加新节点");
    }
    
    /**
     * 判断树是否为空
     */
    public boolean isEmpty() {
        return nodes[0] == null;
    }
    
    /**
     * 返回根节点
     */
    public Node<E> getRoot() {
        return nodes[0];
    }
    
    /**
     * 返回指定节点(非根节点)的父节点
     */
    public Node<E> getParent(Node node) {
        // 每个节点的parent记录了其父节点的索引
        return nodes[node.parent];
    }
    
    public Node<E> getNodeByData(E data) {
        for(int i = 0; i < treeSize; i++) {
            if(nodes[i].data == data) {
                return nodes[i];
            }
        }
        System.out.println("树中不存在包含该数据的节点");
        return null;
    }
    
    /**
     * 返回指定节点(非叶子节点)的所有子节点
     */
    public List<Node<E>> getChildren(Node parent) {
        List<Node<E>> list = new ArrayList<>();
        for(int i = 0; i < treeSize; i++) {
            if(nodes[i] != null && nodes[i].parent == getNodeIndex(parent)) {
                list.add(nodes[i]);
            }
        }
        return list;
    }
    
    /**
     * 返回树的深度
     */
    public int getDeep() {
        int max = 0; // 用于记录节点的最大层次值
        for(int i = 0; i < treeSize && nodes[i] != null; i++) {
            int def = 1; // 初始化本节点的深度
            int m = nodes[i].parent; // 当前节点的父节点的索引
            // 如果其父节点存在
            while(m != -1 && nodes[m] != null) {
                // 继续向上搜索父节点
                m = nodes[m].parent;
                def ++;
            }
            if(max < def) {
                max = def;
            }
        }
        return max;
    }
    
}

import java.util.List;

public class TreeParentTest {
    
    public static void main(String[] args) {
        TreeParent<String> tree = new TreeParent<String>("root");
        TreeParent.Node<String> root = tree.getRoot();
        System.out.println(root);
        tree.addNode("A", root);
        tree.addNode("B", root);
        TreeParent.Node<String> A = tree.getNodeByData("A");
        TreeParent.Node<String> B = tree.getNodeByData("B");
        tree.addNode("C", A);
        tree.addNode("D", A);
        tree.addNode("E", B);
        tree.addNode("F", B);
        System.out.println("树的深度为：" + tree.getDeep());
        List<TreeParent.Node<String>> list = tree.getChildren(A);
        System.out.println("A节点的子节点为：");
        for(TreeParent.Node<String> node : list) {
            System.out.println(node);
        }
        
    }

}

结果：
TreeParent$Node [data=root, parent=-1]
树的深度为：3
A节点的子节点为：
TreeParent$Node [data=C, parent=1]
TreeParent$Node [data=D, parent=1]

父节点表示法的特点：

每个节点可以快速找到父节点
找某个节点的子节点需要遍历整颗树

(2) 子节点链表示法

数组索引 data child
0 A 1 -> 2 -> 3
1 B 4
2 C
3 D 5 -> 6
4 E 7 -> 8 -> 9
5 F
6 G 10
7 H
8 I
9 J
10 K

以下程序采用子节点链表示法实现了一棵树：

import java.util.ArrayList;
import java.util.List;

/**
 * @Description: 使用子节点链表示法实现一棵树
 * @author Jed
 * @date 2018年1月31日
 */
public class TreeChild<E> {
    
    private static class SonNode {
        
        private int pos; // 记录当前节点的位置
        private SonNode next;
        
        public SonNode(int pos, SonNode next) {
            this.pos = pos;
            this.next = next;
        }
    }
    
    public static class Node<T> {
        
        T data;
        SonNode first; // 记录第一个子节点
        
        public Node(T data) {
            this.data = data;
            this.first = null;
        }
        
        @Override
        public String toString() {
            if(first != null) {
                return "TreeChild$Node [data=" + data + ", first=" + first.pos + "]";
            }else {
                return "TreeChild$Node [data=" + data + ", first=-1]";
            }
        }
    }
    
    private final int DEFAULT_TREE_SIZE = 100; // 默认的树的大小
    private int treeSize = 0;
    private Node<E>[] nodes; // 使用一个Node[]数组来记录该树中的所有节点
    private int nodeNums; // 记录节点数
    
    /**
     * 指定根节点创建树
     */
    public TreeChild(E data) {
        treeSize = DEFAULT_TREE_SIZE;
        nodes = new Node[treeSize];
        nodes[0] = new Node<E>(data);
        nodeNums++;
    }
    
    /**
     * 指定根节点、指定treeSize创建树
     */
    public TreeChild(E data, int treeSize) {
        this.treeSize = treeSize;
        nodes = new Node[treeSize];
        nodes[0] = new Node<E>(data);
        nodeNums++;
    }
    
    /**
     * 获取某个节点的索引值
     */
    public int getNodeIndex(Node node) {
        for(int i = 0; i < treeSize; i++) {
            // 找到指定节点
            if(nodes[i] == node) {
                return i;
            }
        }
        return -1;
    }
    
    /**
     * 为指定节点添加子节点
     */
    public void addNode(E data, Node parent) {
        for(int i = 0; i < treeSize; i++) {
            // 找到数组中第一个为null的元素，该元素保存新节点
            if(nodes[i] == null) {
                // 创建新节点，并用指定的数组元素保存它
                nodes[i] = new Node(data);
                if(parent.first == null) {
                    parent.first = new SonNode(i, null);
                }else {
                    SonNode next = parent.first;
                    while(next.next != null) {
                        next = next.next;
                    }
                    next.next = new SonNode(i, null);
                }
                nodeNums++;
                return;
            }
        }
        throw new RuntimeException("该树已满，无法添加新节点");
    }
    
    /**
     * 判断树是否为空
     */
    public boolean isEmpty() {
        return nodes[0] == null;
    }
    
    /**
     * 返回根节点
     */
    public Node<E> getRoot() {
        return nodes[0];
    }
    
    /**
     * 返回指定节点(非叶子节点)的所有子节点
     */
    public List<Node<E>> getChildren(Node parent) {
        List<Node<E>> list = new ArrayList<>();
        // 获取parent节点的第一个子节点
        SonNode next = parent.first;
        // 沿着孩子链不断搜索下一个孩子节点
        while(next != null) {
            // 添加孩子链中的节点
            list.add(nodes[next.pos]);
            next = next.next;
        }
        return list;
    }
    
    /**
     * 返回指定节点(非叶子节点)的第index个子节点
     */
    public Node<E> getChild(Node parent, int index) {
        // 获取parent节点的第一个子节点
        SonNode next = parent.first;
        // 沿着孩子链不断搜索下一个孩子节点
        for(int i = 0; next != null; i++) {
            if(index == i) {
                return nodes[next.pos];
            }
            next = next.next;
        }
        return null;
    }
    
    // 这是一个递归方法，每颗子树的深度为其所有子树的深度 +1
    private int deep(Node node) {
        if(node.first == null) {
            return 1;
        }else {
            // 记录其所有子树的最大深度
            int max = 0;
            SonNode next = node.first;
            // 沿着孩子链不断搜索下一个孩子节点
            while(next != null) {
                // 获取以其子节点为根的子树的深度
                int tmp = deep(nodes[next.pos]);
                if(tmp > max) {
                    max = tmp;
                }
                next = next.next;
            }
            return max + 1;
        }
    }
    
    /**
     * 返回该树的深度
     */
    public int getDeep() {
        return deep(getRoot());
    }

}

import java.util.List;

public class TreeChildTest {
    
    public static void main(String[] args) {
        TreeChild<String> tc = new TreeChild<String>("root");
        TreeChild.Node<String> root = tc.getRoot();
        System.out.println(root);
        tc.addNode("A", root);
        tc.addNode("B", root);
        TreeChild.Node<String> A = tc.getChild(root, 0);
        TreeChild.Node<String> B = tc.getChild(root, 1);
        tc.addNode("C", A);
        tc.addNode("D", A);
        tc.addNode("E", B);
        tc.addNode("F", B);
        System.out.println("树的深度为：" + tc.getDeep());
        List<TreeChild.Node<String>> list = tc.getChildren(A);
        System.out.println("A节点的子节点为：");
        for(TreeChild.Node<String> node : list) {
            System.out.println(node);
        }
        System.out.println(A);
        System.out.println(B);
        
    }
    
}

结果：
TreeChild$Node [data=root, first=-1]
树的深度为：3
A节点的子节点为：
TreeChild$Node [data=C, first=-1]
TreeChild$Node [data=D, first=-1]
TreeChild$Node [data=A, first=3]
TreeChild$Node [data=B, first=5]

子节点链表示法的特点：

每个节点都可以快速找到它的所有子节点
但要找到某个节点的父节点则需要遍历整颗树

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