一上午学习了相关树的知识,更多相关树的东西在接下来的一周再鼓捣,先做下笔记:)
先写下相关树的概念:
1.树:就是n个结点的有限集.
2.空树:有0个结点有限集.
3.根(Root),子树(SubTree).直接上图比较好...
A
/ \
B C
/ \ / \
D E F G
/ \ \
H I J
上图中A就是根,而下面的B和C就是A的子树,当然了,D,E又是B的子树,F,G是C的子树.用<<大话>>上说就是:在任意一颗非空树中:1.有且仅有一个特定的成为根的结点.2.当n>1时,其余结点可分为m个互不相交的有限集T1,T2...Tm,其中每一个集合本身又是一棵树,并且称为根的子树.
4.结点的度(Degree):结点拥有的子树树量.度为0的结点称为叶结点或终端结点(Leaf),度不为0的结点成为非终端结点或分支结点.同时除了根结点外,分支结点也叫内部结点.
5.树的度:树内个结点的度的最大值,如上面那个树的度就为2.
6.孩子(Child)和双亲(Parent)以及兄弟(Sibling):用上面的树举例子,A是B和C的双亲,B和C是A的孩子,B和C是兄弟.同时注意,根是没有双亲的,终端结点没有孩子,但是有可能有兄弟
7.结点的层次(Level):从根开始定义,根为第一层,根的孩子为第二层,以此类推.其双亲在同一层的结点互称为堂兄弟.
8.深度(Depth)和高度(Height):这里<<大话>>上只说了"树中结点的最大层次称为书的深度或高度".Wiki上是这样解释的:
The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. The depth of a node is the length of the path to its root (i.e., its root path).然后再Stackoverflow又看到这样更为详细的说明:
According to Cormen et al. Introduction to Algorithms (Appendix
B.5.3), the depth of a node X in a tree T is defined as the length of
the simple path (number of edges) from the root node of T to X. The
height of a node Y is the number of edges on the longest downward
simple path from Y to a leaf. The height of a tree is defined as the
height of its root node.Note that a simple path is a path without
repeated vertices.The height of a tree is equal to the max depth of a
tree. The depth of a node and the height of a node are not necessarily
equal. See Figure B.6 of the 3rd Edition of Cormen et al. for an
illustration of these concepts.
很清楚了,结点的深度就是从根结点到当前结点的高度,用上面的那个树来说结点D的深度就是2.高度就是当前结点到终端结点的值,也就是说结点D的高度就是1.好了,再来说下树的高度,按照定义,就是从根结点到终端结点的长度,这里就是3,而树的高度呢?按照值来说是0,注意看清楚上面说的这句话The height of a tree is equal to the max depth of a tree. 这里不是说树的高度和深度是相同的,而是说"树的高度和树的最大深度相同".
9.注意:树中结点的各子树看成从左到右是有序的,该树则为有序树,否则为无序树.
10.森林:m(m>=0)棵互不相交的树的集合.第树中每个结点而言,其子树的集合极为森林.
二叉树:
定义:n(n>=0)个结点的有限集合,该集合可能为空集(空二叉树),或有一个根结点或两棵互不相交的/分别称为根结点的左子树和右子树的二叉树组成.其实就是说每个结点最多只能有2个子结点.而且就算某个结点只有一个子结点,那么这个子结点也是要区分左子树和右子树的.
特殊的二叉树:
1.斜树:顾名思义,就是每个结点只有左子树的叫做左斜树.每个结点只有右子树的叫做右斜树.
2.满二叉树(Full binary tree):一棵二叉树中所有的分支结点都存在左子树和右子树,并且所有叶子都在同一层上.如下图:
A
/ \
B C
/ \ / \
D E F G
但是接下来我就对这个概念有点疑惑了.下面详说...
3.完全二叉树(Complete binary tree):这里我也有一些疑惑,现在也没有搞懂,就是到底什么叫做完全二叉树(Complete binary tree),<<大话>>上这样说:对一棵具有n个结点的二叉树按照层次序排列,如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树.并且举了下面几个例子:
点击查看原图点击查看原图点击查看原图
如果像下面这种情况呢?
点击查看原图
按照大话上的说法,这厮就是完全二叉树.但是我在VirginiaTech大学看到这篇文章:(http://courses.cs.vt.edu/~cs3114/Fall09/wmcquain/Notes/T03a.BinaryTreeTheorems.pdf)这里对完全二叉树的定义是这样的:
a binary tree T with n levels is complete if all levels except
possibly the last are completely full, and the last level has all its
nodes to the left side.
就是说除了最后一层外,所有的结点都是有左孩子和右孩子的,并且最后一层的结点都有左孩子.并且用了下列的例子来说明:Capture.PNG
按照这里的定义来讲,我刚刚说的那个例子就不应该是完全二叉树了呀!很是奇怪,同时这里也有对满二叉树的定义:
a binary tree T is full if each node is either a leaf or possesses
exactly two child nodes.
就是说一个结点要么都有左右孩子要么一个都没有,这样的二叉树就叫做满二叉树.可是大话上说了所有的终端结点都在同一层,很是不解...
二叉树的性质:
1.在二叉树的第i层上至多有2^(i-1)个结点(i>=1)
2.深度为k的二叉树至多有2^k-1个结点(k>=1)
3.对任意一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1
4.具有n个结点的完全二叉树的深度为[log2n]+1([x]表示不大于x的最大整数)
5.如果对一棵有n个结点的完全二叉树的结点按层序编号(每层从左到右),对任一结点(1<=i<=n)有:
1)如果i=1,则结点i是二叉树的根,无双亲,如果i>1,则其双亲是结点[i/2].
2)如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i.
3)如果2i+1>n,则结点无右孩子,否则其右孩子是结点2i+1