每天get一个新知识，超开心~
前面讲的数据结构都是前后具有一对一的关系，无论是线性表还是队列，栈等都是一对一的关系，那么如果出现一对多的关系的时候该怎么办呢？这种一对多的关系，就是今天要学习的数据结构——树。
一、树的定义二、树的基本概念三、树的抽象数据类型四、树的双亲表示法（Java、C语言）五、树的孩子表示法（Java、C语言）六、树的孩子兄弟表示法（Java、C语言）
一、树的定义树（Tree）是n（n>=0）个结点的有限集。n=0时称为空树。在任意一颗非空树中：
- 有且仅有一个特定的称为根（root）的结点；当n>1时，其余结点可分为m(m>0)个互补交互的有限集T1、T2…Tm，其中每一个集合本身又是一棵树，并称为根的子树（SubTree）。
树需要注意两点
1.有且仅有一个根结点
2.子树没有限制，但是它们一定是不能相交的
1、结点的分类：
树的结点包含一个数据元素及若干个指向其子树的分支。结点拥有的子树数称为结点的度（Degree）。度为0的结点称为叶结点（Leaf）或终端结点；度不为0的结点称为非终端结点或分支支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。
2、结点间的关系
结点的子树的根称为该结点的孩子（Child），相应的，该结点称为孩子的双亲（Parent）（注意是双亲，不是单亲）。同一个双亲的孩子之间互称兄弟（Sibling）。结点的祖先是从根到该结点所经分支上的所有结点。以某结点为根的子树中的任一结点都称为该结点的子孙。
3、树的其他相关概念
结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层。双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度（Depth）或高度。
如果将树中结点的各子树看成从左至右是有次序的，不能互换，则称该树为有序树，否则为无序树。
森林（Forest）是m（m>=0）棵互不相交的树的集合。
ADT 树（tree)
Date
树是由一个根结点和若干颗子树构成。树中结点具有相同数据类型及层次关系。
Operation
InitTree（*T）：构造空树T。
DestroyTree（*T）：销毁树T。
CreateTree（*T，definition）：按definition中的定义给出树。
ClearTree（*T）：若树存在，则将树T清为空树。
TreeEmpty（T）：若T为空树，则返回ture，否则返回false。
Tree depth（T）：返回T的深度。
Root（T）：返回T的根结点。
value（T，cur_e):cur_e是树中的一个结点，返回该结点的值。
Assign（T，cur_e,value):将结点cur_e的值赋值给value.
Parent(T,cur_e):若cur_e是T的根结点，则返回空，否则返回其双亲。
LeftChild（T，cur_e):若cur_e是树T的非叶结点，则返回cur_e的最左孩子。
RightSibiling(T,cur_e):若cur_e有右兄弟，则返回它的右兄弟，否则返回空。
InsertChild(*T,*p,i,c):其中p指向树T的某个结点，i为p所指的结点度加上1，
非空树c与T不相交，将c插入p为所指结点的第i个子树
DeleteChild（*T，*p，i）：其中p指向树T的某个结点，i为所指结点p的度，
*** 作结果为删除T中p所指结点的第i颗子树。
endDate
四、树的双亲表示法（Java、C语言）
双亲表示法定义
假设以一组连续空间存储数的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。
双亲表示的结点结构
#define MAX_TREE_SIZE 100
typedef int TElemType;
typedef struct PTNode
{
TElemType data;
int parent;
} PTNode;
typedef struct
{
PTNode nodes[MAX_TREE_SIZE];
int r,n;
} PTree;
下面是Java代码
package Trees;
import java.util.Arrays;
public class TreeImp1 {
private int capacity;//树容量
private int nodeCount;//树结点数量
private Node[] elements;//存放Node类型的数组
//查询树的结点数量
public int getNodeCount() {
return nodeCount;
}
public void setNodeCount(int nodeCount) {
this.nodeCount = nodeCount;
}
public int getCapacity() {
return capacity;
}
public void setCapacity(int capacity) {
this.capacity = capacity;
}
public Node[] getElements() {
return elements;
}
public void setElements(Node[] elements) {
this.elements = elements;
}
//设置数组容量的构造方法
public TreeImp1(int capacity) {
this.capacity = capacity;
this.elements = new Node[capacity];
}
@Override
public String toString() {
return "TreeImp1{" +
"elements=" + Arrays.toString(elements) +
'}';
}
//是否空树
public boolean isEmpty(){
return nodeCount == 0;
}
//设置根结点
public Node setRootNode(int a){
this.elements[0] = new Node(a,-1);
nodeCount++;
return new Node(a, -1);
}
//查询根结点
public Node getRootNode(){
return this.elements[0];
}
//为某个结点添加结点
public void addNode(int data, int parent, int newData){
if (nodeCount > capacity){
throw new RuntimeException("超出容量");
}
else{
for (int i = 0; i < nodeCount; i++) {
Node oldNode = new Node(data, parent);
if (this.elements[i].equals(oldNode)){
this.elements[nodeCount] = new Node(newData,i);
nodeCount++;
break;
}
}
}
}
//查找第一个存放数值为data的结点的索引位置，有的话返回该数据结点索引，否则返回-1
public int indexNode(int data){
for (int i = 0; i < nodeCount; i++) {
if (this.elements[i].getData() == data){
return i;
}
}
return -1;
}
//查询某个结点的所有子结点,并将他们放入一个新的数组中
public TreeImp1 arrayChildren(int data, int parent){
Node oldNode = new Node(data,parent);
TreeImp1 t = new TreeImp1(this.capacity);
for (int i = 0; i < nodeCount; i++) {
if (this.elements[i].equals(oldNode)){
for (int j = 0; j < nodeCount; j++) {
if (this.elements[j].getParent() == i){
t.elements[t.nodeCount] = elements[j];
t.nodeCount++;
}
}
return t;
}
}
return new TreeImp1(0);
}
//求树的度
public int degreeForTree(){
int max = 0;
for (int i = 0; i < nodeCount; i++) {
TreeImp1 x = arrayChildren(this.elements[i].getData(), this.elements[i].getParent());
int z = x.nodeCount;
max = z > max ? z : max;
}
return max;
}
}
//结点类
class Node{
private int data;//结点中存放的数据
private int parent;//结点的父结点的索引
//两个参数构造方法
public Node(int data, int parent) {
this.setData(data);
this.setParent(parent);
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public int getParent() {
return parent;
}
public void setParent(int parent) {
this.parent = parent;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node node = (Node) o;
return data == node.data &&
parent == node.parent;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
", parent=" + parent +
'}';
}
}
树的存储描述是比较自由的，我们可以在指针域中加入一个指向孩子的指针域，那我们就可以知道这个结点的孩子是谁。
五、树的孩子表示法（Java、C语言）把每个结点的孩子结点排列起来，以单链表作为存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。
孩子表示法的结点结构
孩子表示法有两种结点结构：孩子链表的孩子结点和表头数组的表头结点
孩子链表的孩子结点
表头数组的表头结点
C语言代码
#define MAX_TREE_SIZE 100
typedef int TElemType;
typedef struct CTNode
{
int child;
struct CTNode *next;
} *ChildPtr;
typedef struct
{
TElemType data;
ChildPtr firstchild;
} CTBox;
typedef struct
{
CTBox nodes[MAX_TREE_SIZE];
int r,n;
} CTree;
Java代码（转载的代码）
package com.datastruct.study.tree;
public class SonShow {
private final static Integer ARRAY_SIZE = 10;
private InnerArray[] dataArray;
private Integer position = null;
class InnerArray{
private String data;
private ChildNode firstChild;
public InnerArray(String data, ChildNode firstChild) {
this.data = data;
this.firstChild = firstChild;
}
public String getData() {
return data;
}
public ChildNode getFirstChild() {
return firstChild;
}
}
class ChildNode{
private Integer childPosition;
private ChildNode next;
public ChildNode(Integer childPosition, ChildNode next) {
this.childPosition = childPosition;
this.next = next;
}
public Integer getChildPosition() {
return childPosition;
}
public void setChildPosition(Integer childPosition) {
this.childPosition = childPosition;
}
public ChildNode getNext() {
return next;
}
public void setNext(ChildNode next) {
this.next = next;
}
}
public SonShow(){
dataArray = new InnerArray[ARRAY_SIZE];
}
public SonShow(int size){
dataArray = new InnerArray[size];
}
public String add(String value,Integer parentPosition){
if(position == null){
position = 0;
dataArray[position++] = new InnerArray(value,null);
return value;
}
//先插入到数组的位置，再将该节点链接到对应的父节点的链表最后
dataArray[position++] = new InnerArray(value,null);
//如果还没有孩子链表则生成
if(dataArray[parentPosition].firstChild==null){
//上面++了所以次数要-1，指定刚插入的孩子节点的位置
dataArray[parentPosition].firstChild = new ChildNode(position-1,null);
return value;
}
//若是已经存在链表，则遍历链表，放在最后面
ChildNode firstNode = dataArray[parentPosition].getFirstChild();
while (firstNode.next!=null){
firstNode = firstNode.next;
}
firstNode.next = new ChildNode(position-1,null);
return value;
}
public InnerArray getValueAndChild(Integer position){
return dataArray[position];
}
public int size(){
return position;
}
}
}
六、树的孩子兄弟表示法（Java、C语言）
定义：任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟存在也是唯一的。因此，设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。
孩子兄弟表示法的结点结构
typedef struct CSNode
{
TElemType data;
struct CSNode *firstchild,*rightsib;
} CSNode,*CSTree;
这个孩子兄弟表示法，其实更好理解，就两个指针，一个指向孩子，一个指向兄弟，那么，这样一来就把复杂的树转化成为了二叉树。
这个Java代码也很简单，如下：
Java代码
class TreeNode {
private TreeNode sonNode;//这里存储的是最左的儿子节点
private TreeNode brotherNode;//这里存储的是自己的兄弟节点
private String value;
public TreeNode(TreeNode sonNode, TreeNode brotherNode, String value) {
this.sonNode = sonNode;
this.brotherNode = brotherNode;
this.value = value;
}
public TreeNode getSonNode() {
return this.sonNode;
}
public TreeNode getBrotherNode() {
return brotherNode;
}
public String getValue() {
return value;
}
public void setSonNode(TreeNode sonNode) {
this.sonNode = sonNode;
}
public void setBrotherNode(TreeNode brotherNode) {
this.brotherNode = brotherNode;
}
}
class SBTree {
private TreeNode root;//这个是根节点
public SBTree(String rootValue) {//构建树的时候需要吧根节点的值初始化一下
root = new TreeNode(null, null, rootValue);
}
public TreeNode getRoot() {
return this.root;
}
public TreeNode insertSonNode(TreeNode targetNode, String value) {
TreeNode nowSonNode = new TreeNode(null, null, value);
TreeNode preSonNode = targetNode.getSonNode();
if (preSonNode != null) { //已经有儿子,把前儿子的兄弟设置为自己.
return insertBrotherNode(preSonNode, value);
} else
targetNode.setSonNode(nowSonNode);
return nowSonNode;
}
public TreeNode insertBrotherNode(TreeNode targetNode, String value) {
TreeNode nowBrotherNode = new TreeNode(null, null, value);
while (targetNode.getBrotherNode() != null) { //有兄弟了
targetNode = targetNode.getBrotherNode();
}
targetNode.setBrotherNode(nowBrotherNode);
return nowBrotherNode;
}
static void printTree(TreeNode root, int depth) {
if (root == null)
return;
for (int i = 0; i < depth; i++) {
System.out.print("t|");
}
System.out.println(root.getValue());
printTree(root.getSonNode(), depth + 1);
printTree(root.getBrotherNode(), depth);
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）