欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

树基本概念

程序员文章站 2022-05-09 16:21:51
...
结点(node):包含数据项及指向其他结点的分支。
结点的度(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