首页 > 其他 > 详细

算法学习 - 树的一些解释

时间:2014-07-30 01:08:02      阅读:435      评论:0      收藏:0      [点我收藏+]

树的解释

是ADT里面很经典的数据结构了,应用太多了,相对于链表的线性访问时间,O(n)。树的大部分操作的平均运行时间都是为O(logN)。
- 树的概念
树有几种方式定义,一种是递归,若树不为空,则一棵树是由(root)的节点r和0个或者多个非空树组成。N个节点的树,有N-1个边。没有儿子的节点称为叶子(leaf). 对于任意节点N(i),它的深度为从根节点到N(i)的唯一路径长度。如果存在N(1)到N(2)的路径,那么N(1)是N(2)的祖先。如果N(1)不等于N(2),那么就称为真祖先。N(2)为真后裔

树的实现

树的代码实现有多种代码。首先是第一儿子/下一兄弟表示方法。

typedef struct TreeNode * PtrToNode;
struct TreeNode
{
ElementType element;
PtrToNode firstChild;
PtrToNode nextBrother;
};

以上就是他的实现方法了。其实这种表示是一个节点存放了它的第一个孩子,还有它下一个兄弟,这样下一层的节点和本层的节点都能够访问了。

树的遍历

树的遍历有三种:

  • 先序遍历
  • 中序遍历
  • 后序遍历

先序遍历是从头结点依次向下遍历,自上至下,自左之右。
中序遍历是先遍历左节点,然后父节点,然后右节点,再向上遍历。
后序遍历是先遍历左右子节点,然后向上遍历。

bubuko.com,布布扣

上面这二叉树。

先序遍历:1 2 3 4 5 6 7

中序遍历: 4 2 6 7 5 1 3

后序遍历: 4 6 7 5 2 3 1

树的一些分类

  • 普通树
  • 二叉树
  • 二叉查找树
  • 平衡二叉树
  • 伸展树
  • B-树

算法学习 - 树的一些解释,布布扣,bubuko.com

算法学习 - 树的一些解释

原文:http://blog.csdn.net/alps1992/article/details/38277983

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!