一、树
1、什么是树?
树状图是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:
每个节点有零个或多个子节点;没有父节点的节点称为根节点;每一个非根节点有且只有一个父节点;除了根节点外,每个子节点可以分为多个不相交的子树;
树(tree)是包含n(n>0)个结点的有穷集,其中:
(1)每个元素称为结点(node);
(2)有一个特定的结点被称为根结点或树根(root)。
(3)除根结点之外的其余数据元素被分为m(m≥0)个互不相交的集合T1,T2,……Tm-1,其中每一个集合Ti(1<=i<=m)本身也是一棵树,被称作原树的子树(subtree)。
2、相关术语
- 节点的度:一个节点含有的子树的个数称为该节点的度;
- 叶节点或终端节点:度为0的节点称为叶节点;
- 非终端节点或分支节点:度不为0的节点;
- 双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;
- 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;
- 兄弟节点:具有相同父节点的节点互称为兄弟节点;
- 树的度:一棵树中,最大的节点的度称为树的度;
- 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
- 树的高度或深度:树中节点的最大层次;
- 堂兄弟节点:双亲在同一层的节点互为堂兄弟;
- 节点的祖先:从根到该节点所经分支上的所有节点;
- 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。
- 森林:由m(m>=0)棵互不相交的树的集合称为森林;
二、二叉树
1、什么是二叉树?
二叉树,就是度不超过2的树(节点最多有两个叉)。
2、两种特殊的二叉树
满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。
完全二叉树:叶节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。
满二叉树一定是完全二叉树,但是完全二叉树不一定是满二叉树。
三、树的遍历
前序遍历:先从根部出发,然后由左向右,一颗一颗树来完成遍历。先访问根再访问叶子结点,这就是我画出来的前序遍历图,箭头的方向表示遍历的顺序。a为起点。(根节点->左子树->右子树)
结果是:1、2、5、6、7、3、4、8、9、10
结果是:1、2、4、5、7、8、3、6。
后序遍历:顾名思义,就是从叶子结点出发,先遍历叶子结点再到根结点,最后到父结点。我画出顺序可能会更直观点。 (左子树->右子树->根节点)
结果是:5、6、7、2、3、9、10、8、4、1
结果是:4、8、7、5、2、6、3、1
层次遍历:按0层、1层、2层、3层,从左到右来遍历
结果是:1、2、3、4、5、6、7、8、9、10
结果是:1、2、3、4、5、6、7、8
中序遍历:(左子树->根节点->右子树)
结果是:4,2,7,8,5,1,3,6。
四、堆
堆是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:
- 堆中的某个节点的值总是不大于或不小于其父节点的值(不大于则为大根堆,不小于则为小根堆)。
- 堆总是一棵完全二叉树。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)