数据结构二叉树知识点概括
发布时间：2021-12-05 16:55:46 所属栏目：PHP教程 来源：互联网
导读：数据结构二叉树知识点总结 术语 1. 节点的度：一个节点含有的子树的个数称为该节点的度； 2. 叶节点或终端节点：度为零的节点； 3. 非终端节点或分支节点：度不为零的节点； 4. 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 5
|
数据结构二叉树知识点总结 术语 1. 节点的度：一个节点含有的子树的个数称为该节点的度； 2. 叶节点或终端节点：度为零的节点； 3. 非终端节点或分支节点：度不为零的节点； 4. 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 5. 兄弟节点：具有相同父节点的节点互称为兄弟节点； 6. 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推； 7. 树的高度或深度：树中节点的最大层次； 8. 堂兄弟节点：父节点在同一层的节点互为堂兄弟； 9. 节点的祖先：从根到该节点所经分支上的所有节点； 10. 孙：以某节点为根的子树中任一节点都称为该节点的子孙。 11. 森林：由m（m>=0）棵互不相交的树的集合称为森林； 12. 满二叉树：一棵深度为k，且有2^k-1 (2的k次方减一)个节点称之为满二叉树 13. 完全二叉树：完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树 二叉树的性质 1.在非空二叉树中，第i层的结点总数不超过2^(i-1),i>=1； 2.深度为h的二叉树最多有2^h-1个结点(h>=1)，最少有h个结点； 3.对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1； 4.具有n个结点的完全二叉树的深度为K =[log2n」+1(取下整数) 5.有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系： 若I为结点编号则 如果I>1，则其父结点的编号为I/2； 6.完全二叉树，如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子； 如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。 7.给定N个节点，能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。 8.设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i 二叉树的遍历三种方式，如下： （1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。 （2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。 （3）后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。  （编辑：应用网_丽江站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
浙公网安备 33038102330468号