首页 > 学院 > 开发设计 > 正文

树的基本概念

2019-11-14 11:35:38
字体:
来源:转载
供稿:网友

逻辑非线性结构

数据和数据之间是1:m

若某个节点有后继,则后继节点可以是多个

若某个节点有前驱,则前驱节点只能是一个

可以把节点分成前驱节点和后继节点

节点的度:若A节点有m个子节点,则节点A的度是m

树的度·:树中节点最大的度

度为n,高度为h的树中,最多有多少个节点?:1+n+n^2+n^3+....+n^(h-1)

树的遍历:对树中所有节点,无遗漏,无重复的访问一遍

遍历的方法:

深度优先遍历:优先访问某一个“路径”,直到叶子节点

根节点入栈;

while(栈非空){

node = pop(堆栈);

access(node); // 访问node节点的值

将node所有子节点入栈

}

广度优先遍历:优先访问同层的所有节点

根节点入队

while(队非空){

node = out(队列);

Access(node);

将node所有子节点入队

]

树的表示法:

typedef  ... USER_TYPE;

typedef struct TREE{

USER_TYPE value;

struct  TREE *child;

int childCount;

}TREE;

TREE *tree;

tree->child = (TREE *)malloc(sizeof(TREE) * tree->childCount);

使用上述方式申请一个节点的子节点数目,那么这个子节点的数目就被固定

另一种方法:将节点依次排上编号,从0开始

将每一个节点的数据和其父节点的下标放在一起

二叉数:

二叉树的子节点分左右

满二叉树:高度为h的节点,节点总数为2^h-1

一颗二叉树的节点总数为n,则二叉树的高度是[log(2)n]+1

完全二叉树

1.假设一个完全二叉树的节点总数是n,且从上到下,从左到右一次编号。那么为 i 的节点如果有左节点,那么左节点的编号是2*i,右节点的个数是2*i+1

2.一个高度为h的二叉树,其节点总数最少是2^(h-1),最多是2^h-1个

3.任意一个二叉树:n0 = n2 + 1

问题:一个节点总数是n的二叉树,n为偶数,则叶子节点数是多少?

n总 = n0 + n1 +n2

n0 = n2 + 1

n总 = n1+2n0-1

因为n总是偶数,则其叶子数是奇数个,所以n1= 1

no = n总/2


发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表