树基本概念
程序员文章站
2022-05-09 16:21:51
...
结点(node):包含数据项及指向其他结点的分支。
结点的度(degree):是结点所拥有子树的棵数。
叶结点(leaf):度为0的结点,又称终端结点。
分支结点(branch):除叶结点外的其他结点,又称非终端结点。
子女结点(child):若结点x有子树,则子树的根结点即为结点x的子女。
父结点(parent):若结点x有子女,它即为子女的父结点。
兄弟结点(sibling):同一个父结点的子女互称为兄弟。
祖先结点(ancestor):从根结点到该结点所经分支上的所有结点。
子孙结点(descendant):某一结点的子女,以及这些子女的子女都是该结点的子孙。
结点所处层次(level):结点的层次,即从根到该结点所经路径上的分支条数。
树的深度(depth):树中距离根结点最远的结点所处层次即为树的深度。空树的深度是0.
树的高度(height):与深度计算的方向不同,但数值相等。
树的度(degree):树中结点的度的最大值.
结点的度(degree):是结点所拥有子树的棵数。
叶结点(leaf):度为0的结点,又称终端结点。
分支结点(branch):除叶结点外的其他结点,又称非终端结点。
子女结点(child):若结点x有子树,则子树的根结点即为结点x的子女。
父结点(parent):若结点x有子女,它即为子女的父结点。
兄弟结点(sibling):同一个父结点的子女互称为兄弟。
祖先结点(ancestor):从根结点到该结点所经分支上的所有结点。
子孙结点(descendant):某一结点的子女,以及这些子女的子女都是该结点的子孙。
结点所处层次(level):结点的层次,即从根到该结点所经路径上的分支条数。
树的深度(depth):树中距离根结点最远的结点所处层次即为树的深度。空树的深度是0.
树的高度(height):与深度计算的方向不同,但数值相等。
树的度(degree):树中结点的度的最大值.
#ifndef TREE_H
#define TREE_H
template<typename T>
class Tree{
public:
Tree();
~Tree();
position Root(); //返回根结点地址
BuildRoot(const T& value);//建立树的根结点
position FirstChild(position p);//返回第一个子树地址,没有返回0
position NextSibling(position p);//返回下一个兄弟结点,没有返回0
position Parent(position p); //返回父结点地址,若p为根返回0
T getData(position p);//返回p存放的值
bool InsertChild(const position p,const T& value);//在p下插入子女value
bool DeleteChild(position p,int i);//删除p的第i个子女及全部子孙结点
void DeleteSubTree(position t);//删除以t为根结点的子树
bool IsEmpty();
void Traversal(void(*visit)(position p));//遍历,visit是用户自编的访问结点p数据的函数
};
#endif // TREE_H