数据结构之⑮树的定义

树的定义...



定义

树Tree是n个结点的有限集。n = 0时称为空树。

在任意一颗非空树中：

1. 有且仅有一个特定的称为根Root的结点；

2. 当n > 1时，其余结点可分为m(m > 0)个互补相交的有限集T1、T2、...、Tm，其中每一个集合本身又是一棵树，并且称为根的子树；

注意：n > 0时根结点是唯一的；m > 0时，子树的个数没有限制，但他们一定是互不相交的。

树的结点

结点分类

• 结点拥有的子树数称为结点的度Degree。
• 度为0的结点称为叶结点Leaf。
• 度不为0的结点称为分支结点。
• 树的度是树内各结点的度的最大值。

结点间的关系

• 结点的子树的根称为该结点的孩子Child，该结点称为孩子的双亲Parent。
• 同一双亲的孩子之间互称为兄弟。
• 结点的子树中的任一结点都为该结点的子孙，该结点称为子孙的祖先。

树的其他相关概念

• 结点的层次：从根开始定义起，根为第一层，根的该子为第二层。
• 树中结点的最大层次称为树的深度Depth或高度

• 如果将树中的各子树看成是从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

• 森林Forest是指m （m >= 0）颗互不相交的树的集合。

树的基本操作

• 创建树
• 销毁树
• 清空树
• 插入结点
• 删除结点
• 获取结点
• 获取根结点
• 获取根的结点数
• 获取树的高度
• 获取树的度

树结构的代码表示

头文件

//
// Tree.h
//
// Created by 刘涤生 on 2017/2/15 21:53.
//
#ifndef _TREE_H_
#define _TREE_H_
typedef void Tree;
typedef void TreeNode;
/**

* 创建树

* @return

*/
Tree* Tree_Create();
/**

* 销毁树

* @param tree

*/
void Tree_Destroy(Tree* tree);
/**

* 清空树

* @param list

*/
void Tree_Clear(Tree* tree);
/**

* 插入结点

* @param list

* @param node

* @param pos >= 0

* @return

*/
int Tree_Insert(Tree* tree,TreeNode* node,int pos);
/**

* 删除结点并返回结点

* @param list

* @param pos

* @return

*/
TreeNode* Tree_Delete(Tree* tree,int pos);
/**

* 获取结点

* @param list

* @param pos

* @return

*/
TreeNode* Tree_Get(Tree* tree,int pos);
/**

* 获取树的根结点

* @param tree

* @return

*/
TreeNode* Tree_Root(Tree* tree);
/**

* 获取树的高度

* @param list

* @return

*/
int Tree_Height(Tree* tree);
/**

* 获取树的结点数

* @param tree

* @return

*/
int Tree_Count(Tree* tree);
/**

* 获取树的度树

* @param tree

* @return

*/
int Tree_Degree(Tree* tree);
#endif
实现文件

//
// Tree.c
//
// Created by 刘涤生 on 2017/2/15 21:53.
//
#include "Tree.h"
#include

Tree* Tree_Create() {

return NULL;
}

void Tree_Destroy(Tree* tree) {

}

void Tree_Clear(Tree* tree) {

}

int Tree_Insert(Tree* tree,TreeNode* node,int pos) {

return 0;
}

TreeNode* Tree_Delete(Tree* tree,int pos) {

return NULL;
}

TreeNode* Tree_Get(Tree* tree,int pos) {

return NULL;
}

TreeNode* Tree_Root(Tree* tree) {

return NULL;
}

int Tree_Height(Tree* tree) {

return 0;
}

int Tree_Count(Tree* tree) {

return 0;
}

int Tree_Degree(Tree* tree) {

return 0;
}小结

线性结构

树结构

第一个结点：无前驱

根结点：无双亲

最后一个结点：无后继

叶结点：无后继

中间结点：一个前驱，一个后继

中间结点：一个前驱，多个后继

在一些情况下，线性结构可看作特殊的树结构

    关注 刘涤生