美文网首页
数据结构与算法 java语言描述

数据结构与算法 java语言描述

作者: 奉先 | 来源:发表于2018-10-18 21:01 被阅读128次

1.树的基本概念

1.1 概念

下面是一个树的例子,下面以这个树介绍基本概念。


A节点是根节点,A节点和F节点由一条连接;F节点是A节点的儿子,并且是K,L,M节点的父亲。没有儿子节点的节点叫做树叶(例如B,C,H等),具有相同父亲的节点称为兄弟(例如K,L,M)。
对于n1,n2,...nk的序列,对于任何1<=i<=k,ni都是ni+1的父亲节点,这样的序列称为从n1到nk的路径。路径的等于这条路径上边的个数。对任意节点ni,它的深度就是从根到ni的唯一的路径的长。对任意节点ni,它的就是从ni到一片树叶的最长路径的长。例如,上图中E的深度为1,高度为2。如果存在一条从 n1到n2的路径,那么n1称为n2的祖先,n2称为n1的后裔,如果n1不等于n2,称为真祖先真后裔

1.2 实现:

由于树的每个节点的儿子节点的个数不定,所以实现树时,将树的每个节点的所有儿子都放在树节点的链表中。

class TreeNode{
    Object element;
    TreeNode firstChild;
    TreeNode nextSibling
}

firstChild指向节点的第一个儿子节点,nextSibling指向节点的下一个兄弟节点。
树的一个广泛应用是Unix文件目录模拟。树的遍历一般有2种主要方式,先序遍历是先处理数节点,再处理该节点的孩子节点。后续遍历是先处理该节点的孩子节点,再处理该节点。

2. 二叉树

二叉树是一种树,每个节点的孩子节点不能超过二个。因为二叉树的每个节点至多只有2个孩子节点,所以可以使用下边的数据结构来表示。

class TreeNode {
    Object element;
    TreeNode left;
    TreeNode right;
}

相关文章

网友评论

      本文标题:数据结构与算法 java语言描述

      本文链接:https://www.haomeiwen.com/subject/qoaszftx.html