数据结构--树形结构 数据结构--树形结构
数据结构--树形结构
今天在博客上看到这样一段代码，感觉挺有意思，代码如下:
1 public class Edge {
2 //Name of origin town
3 public Node origin;
4 //Name of destination town
5 public Node destination;
6 //Route weight to destination
7 public int weight;
8 //next possible route
9 public Edge next;
10 //constructor
11 public Edge(Node origin, Node destination, int weight) {
12 this.origin = origin;
13 this.destination = destination;
14 this.weight = weight;
15 this.next = null;
16 }
17
18 public Edge next(Edge edge) {
19 this.next = edge;
20 return this;
21 }
22 }
23
24 graph.routeTable.put(a, new Edge(a, b, 5).next(new Edge(a, d, 5).next(new Edge(a, e, 7))));我想到了树形结构，但还是有争议，有人说它是邻接链表，不知大家怎么看？总之还是先回顾下树形吧。
树形结构-- 一对多的关系
数据结构中,使用树形结构表示数据表素之间一对多的关系,树形结构是一种非线型结构.
定义:
树(Tree)是n(n≥0)个相同数据类型的数据元素的集合.树中的数据元素称为节点(Node).。n=0的树称为空树(Empty Tree)；对于n＞0的任意非空树T有：
（1）有且仅有一个特殊的结点称为树的根(Root)结点，根没有前驱结点；
（2）若n＞1，则除根结点外，其余结点被分成了m(m＞0)个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti(1≤i≤m)本身又是一棵树。树T1，T2，…，Tm称为这棵树的子树(Subtree)。
由树的定义可知，树的定义是递归的，用树来定义树。因此，树（以及二叉树）的许多算法都使用了递归。
树的形式定义为：树(Tree)简记为T，是一个二元组，
T = (D, R)
其中：D是结点的有限集合；
R是结点之间关系的有限集合。
树具有下面两个特点：
（1）树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。
（2）树中的所有结点都可以有零个或多个后继结点。
实际上，第（1）个特点表示的就是树形结构的“一对多关系”中的“一”，第（2）特点表示的是“多”。
树的相关术语：
1、结点(Node)：表示树中的数据元素，由数据项和数据元素之间的关系组成。在图中，共有10个结点。
2、结点的度(Degree of Node)：结点所拥有的子树的个数，在图中，结点A的度为3。
3、树的度(Degree of Tree)：树中各结点度的最大值。在图5.1中，树的度为3。
4、叶子结点(Leaf Node)：度为0的结点，也叫终端结点。在图5.1中，结点E、F、G、H、I、J都是叶子结点。
5、分支结点(Branch Node)：度不为0的结点，也叫非终端结点或内部结点。在图5.1中，结点A、B、C、D是分支结点。
6、孩子(Child)：结点子树的根。在图中，结点B、C、D是结点A的孩子。
7、双亲(Parent)：结点的上层结点叫该结点的双亲。在图中，结点B、C、D的双亲是结点A。
8、祖先(Ancestor)：从根到该结点所经分支上的所有结点。在图中，结点E的祖先是A和B。
9、子孙(Descendant)：以某结点为根的子树中的任一结点。在图中，除A之外的所有结点都是A的子孙。
10、兄弟(Brother)：同一双亲的孩子。在图5.1中，结点B、C、D互为兄弟。
11、结点的层次(Level of Node)：从根结点到树中某结点所经路径上的分支数称为该结点的层次。根结点的层次规定为1，其余结点的层次等于其双亲结点的层次加1。
12、堂兄弟(Sibling)：同一层的双亲不同的结点。在图中，G和H互为堂兄弟。
13、树的深度(Depth of Tree)：树中结点的最大层次数。在图5.1中，树的深度为3。
14、无序树(Unordered Tree)：树中任意一个结点的各孩子结点之间的次序构成无关紧要的树。通常树指无序树。
15、有序树(Ordered Tree)：树中任意一个结点的各孩子结点有严格排列次序的树。二叉树是有序树，因为二叉树中每个孩子结点都确切定义为是该结点的左孩子结点还是右孩子结点。
16、森林(Forest)：m(m≥0)棵树的集合。自然界中的树和森林的概念差别很大，但在数据结构中树和森林的概念差别很小。从定义可知，一棵树有根结点和m个子树构成，若把树的根结点删除，则树变成了包含m棵树的森林。当然，根据定义，一棵树也可以称为森林。
树的逻辑表示
二叉树的定义（BinaryTree）：
每个节点至多有两个子树。
二叉树有左右之分，不可颠倒。如果把左右子树顺序颠倒则变了另一个全新的二叉树。
二叉树具有5种形态：
1）满二叉树(Full Binary Tree)：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树，如图所示。
由定义可知，对于深度为k的满二叉树的结点个数为2k-1。（24-1=15）
（2）完全二叉树(Complete Binary Tree)：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k，有n个结点的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树，如图所示。完全二叉树的特点是叶子结点只可能出现在层次最大的两层上，并且某个结点的左分支下子孙的最大层次与右分支下子孙的最大层次相等或大1。
二叉树的性质
性质1 一棵非空二叉树的第i层上最多有2i-1个结点(i≥1)。
性质2 若规定空树的深度为0，则深度为k的二叉树最多有2k-1个结点(k≥0)。
性质3 具有n个结点的完全二叉树的深度k为log2n+1。
性质4 对于一棵非空二叉树，如果度为0的结点数目为n0，度为2的结点数目为n2，则有n0= n2+1。
性质5 对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对所有结点从1开始编号，则对于序号为i的结点，有：
（1）如果i>1，则序号为i的结点的双亲结点的序号为i/2(“/”表示整除)；如果i=1，则该结点是根结点，无双亲结点。
（2）如果2i≤n，则该结点的左孩子结点的序号为2i；若2i>n，则该结点无左孩子。
（3）如果2i+1≤n，则该结点的右孩子结点的序号为2i+1；若2i+1>n，则该结点无右孩子。
二叉树的存储结构--顺序存储
顺序存储：
1 把一个满二叉树从上到下，从左到右顺序编号，依次放到数组中，可得到如图示结果。
2 设满二叉树节点在数组中的索引为i，那么有如下性质：
（1）如果i=0，此节点为根节点，无双亲。
（2）如果i>0，则其双亲为（i-1）/2。（结果取整）
（3）结点i的左孩子为2i+1，右孩子为2i+2.
（4）当i>0时，当i为奇数时，它是双亲节点的左孩子，它的兄弟为i+1；当i为偶数时，它是双亲节点的右孩子，它的兄弟为i-1.
（5）深度为K的满二叉树需要长度为2k-1的数组存储。
今天在博客上看到这样一段代码，感觉挺有意思，代码如下:
1 public class Edge {
2 //Name of origin town
3 public Node origin;
4 //Name of destination town
5 public Node destination;
6 //Route weight to destination
7 public int weight;
8 //next possible route
9 public Edge next;
10 //constructor
11 public Edge(Node origin, Node destination, int weight) {
12 this.origin = origin;
13 this.destination = destination;
14 this.weight = weight;
15 this.next = null;
16 }
17
18 public Edge next(Edge edge) {
19 this.next = edge;
20 return this;
21 }
22 }
23
24 graph.routeTable.put(a, new Edge(a, b, 5).next(new Edge(a, d, 5).next(new Edge(a, e, 7))));我想到了树形结构，但还是有争议，有人说它是邻接链表，不知大家怎么看？总之还是先回顾下树形吧。
树形结构-- 一对多的关系
数据结构中,使用树形结构表示数据表素之间一对多的关系,树形结构是一种非线型结构.
定义:
树(Tree)是n(n≥0)个相同数据类型的数据元素的集合.树中的数据元素称为节点(Node).。n=0的树称为空树(Empty Tree)；对于n＞0的任意非空树T有：
（1）有且仅有一个特殊的结点称为树的根(Root)结点，根没有前驱结点；
（2）若n＞1，则除根结点外，其余结点被分成了m(m＞0)个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti(1≤i≤m)本身又是一棵树。树T1，T2，…，Tm称为这棵树的子树(Subtree)。
由树的定义可知，树的定义是递归的，用树来定义树。因此，树（以及二叉树）的许多算法都使用了递归。
树的形式定义为：树(Tree)简记为T，是一个二元组，
T = (D, R)
其中：D是结点的有限集合；
R是结点之间关系的有限集合。
树具有下面两个特点：
（1）树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。
（2）树中的所有结点都可以有零个或多个后继结点。
实际上，第（1）个特点表示的就是树形结构的“一对多关系”中的“一”，第（2）特点表示的是“多”。
树的相关术语：
1、结点(Node)：表示树中的数据元素，由数据项和数据元素之间的关系组成。在图中，共有10个结点。
2、结点的度(Degree of Node)：结点所拥有的子树的个数，在图中，结点A的度为3。
3、树的度(Degree of Tree)：树中各结点度的最大值。在图5.1中，树的度为3。
4、叶子结点(Leaf Node)：度为0的结点，也叫终端结点。在图5.1中，结点E、F、G、H、I、J都是叶子结点。
5、分支结点(Branch Node)：度不为0的结点，也叫非终端结点或内部结点。在图5.1中，结点A、B、C、D是分支结点。
6、孩子(Child)：结点子树的根。在图中，结点B、C、D是结点A的孩子。
7、双亲(Parent)：结点的上层结点叫该结点的双亲。在图中，结点B、C、D的双亲是结点A。
8、祖先(Ancestor)：从根到该结点所经分支上的所有结点。在图中，结点E的祖先是A和B。
9、子孙(Descendant)：以某结点为根的子树中的任一结点。在图中，除A之外的所有结点都是A的子孙。
10、兄弟(Brother)：同一双亲的孩子。在图5.1中，结点B、C、D互为兄弟。
11、结点的层次(Level of Node)：从根结点到树中某结点所经路径上的分支数称为该结点的层次。根结点的层次规定为1，其余结点的层次等于其双亲结点的层次加1。
12、堂兄弟(Sibling)：同一层的双亲不同的结点。在图中，G和H互为堂兄弟。
13、树的深度(Depth of Tree)：树中结点的最大层次数。在图5.1中，树的深度为3。
14、无序树(Unordered Tree)：树中任意一个结点的各孩子结点之间的次序构成无关紧要的树。通常树指无序树。
15、有序树(Ordered Tree)：树中任意一个结点的各孩子结点有严格排列次序的树。二叉树是有序树，因为二叉树中每个孩子结点都确切定义为是该结点的左孩子结点还是右孩子结点。
16、森林(Forest)：m(m≥0)棵树的集合。自然界中的树和森林的概念差别很大，但在数据结构中树和森林的概念差别很小。从定义可知，一棵树有根结点和m个子树构成，若把树的根结点删除，则树变成了包含m棵树的森林。当然，根据定义，一棵树也可以称为森林。
树的逻辑表示
二叉树的定义（BinaryTree）：
每个节点至多有两个子树。
二叉树有左右之分，不可颠倒。如果把左右子树顺序颠倒则变了另一个全新的二叉树。
二叉树具有5种形态：
1）满二叉树(Full Binary Tree)：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树，如图所示。
由定义可知，对于深度为k的满二叉树的结点个数为2k-1。（24-1=15）
（2）完全二叉树(Complete Binary Tree)：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k，有n个结点的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树，如图所示。完全二叉树的特点是叶子结点只可能出现在层次最大的两层上，并且某个结点的左分支下子孙的最大层次与右分支下子孙的最大层次相等或大1。
二叉树的性质
性质1 一棵非空二叉树的第i层上最多有2i-1个结点(i≥1)。
性质2 若规定空树的深度为0，则深度为k的二叉树最多有2k-1个结点(k≥0)。
性质3 具有n个结点的完全二叉树的深度k为log2n+1。
性质4 对于一棵非空二叉树，如果度为0的结点数目为n0，度为2的结点数目为n2，则有n0= n2+1。
性质5 对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对所有结点从1开始编号，则对于序号为i的结点，有：
（1）如果i>1，则序号为i的结点的双亲结点的序号为i/2(“/”表示整除)；如果i=1，则该结点是根结点，无双亲结点。
（2）如果2i≤n，则该结点的左孩子结点的序号为2i；若2i>n，则该结点无左孩子。
（3）如果2i+1≤n，则该结点的右孩子结点的序号为2i+1；若2i+1>n，则该结点无右孩子。
二叉树的存储结构--顺序存储
顺序存储：
1 把一个满二叉树从上到下，从左到右顺序编号，依次放到数组中，可得到如图示结果。
2 设满二叉树节点在数组中的索引为i，那么有如下性质：
（1）如果i=0，此节点为根节点，无双亲。
（2）如果i>0，则其双亲为（i-1）/2。（结果取整）
（3）结点i的左孩子为2i+1，右孩子为2i+2.
（4）当i>0时，当i为奇数时，它是双亲节点的左孩子，它的兄弟为i+1；当i为偶数时，它是双亲节点的右孩子，它的兄弟为i-1.
（5）深度为K的满二叉树需要长度为2k-1的数组存储。