| 数据结构,树的学习（1）先图后树是不是不太对？ | 您所在的位置：网站首页 › 先序遍历的顺序 › 数据结构,树的学习（1）先图后树是不是不太对？ |
|
1.树的基本术语： 森林，是若干个互不相交的数的集合。 2.二叉树性质1：在二叉树的第i层上，最多有2 ^i-1 个节点，也就是满二叉树，中每一层的节点是*2的，逐层递增的。 最少的话，则是拥有一个节点，否则不再存在此层级。 性质2：深度为K的二叉树至多有(2^K )-1个节点深度为k的二叉树最少拥有K个节点。 性质3：对任何一颗二叉树如果其叶子数为n0，度为2de结点数为n2，则n0 = n2 +1 性质4：具有n个节点的完全二叉树的深度为（log2n） +1性质5：如果对一颗有n个节点的完全二叉树，按照编号，如果节点为i，则其子节点编号为2i 以及2i+1，父节点则为i/2 or （i +1）/2 。关键在于此节点处于父节点的左臂还是右臂、满二叉树一颗深度为K且有(2^K)-1个节点的二叉树称为满二叉树 叶子节点全部在最底层，从上到下，从左到右，每一节点位置都有元素 完全二叉树深度为k的具有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中编号为1~n的节点--对应时，称之为完全二叉树。 也就是像加载数据时，一般不会出现中途为空的节点。如果出现连续中途为空的情况，那这个二叉树就不是完全二叉树。特点：1.叶子只可能分布在最大层次的两层上 2.对任一结点，如果其右子树的最大层次为i，则其左子树的最大层次必为i或i+1 树的存储结构顺序存储实现方式，将二叉树的节点层次编号，依次存放二叉树的数据元素，有点像是序列化的键值对存储。 这个存储方式依靠性质5. 如果其中某一个节点空了，也要用一个空值去填充空位置 这种存储方式的缺点就是，不论怎样，也要去生成一个完整的数，对全二叉树的存储很合适，但是对稀疏的二叉树存储极其不友好。 链式存储每一个节点要留有左右两方的指针引用。和父节点的引用。也就是三个指针引用。然后，可以在这个的基础上，再存有数据。 树的遍历先序遍历ABC 中左右 从根节点开始， 优先遍历左臂，如果左臂存在物体，则深入，如果左臂为空，则遍历右侧，如果全部遍历完毕，则回退一级。继续访问右臂 中序遍历BAC 左中右 优先左，依照一个左中右的流程顺序遍历完整个树，然后逐渐向上遍历 后序遍历BCA 左右中 个人认为，先序遍历更符合人眼中的逻辑思维。嗯，也可以说时我自己眼中的思维吧public void PrePrderTraverse(Tree T){ if(T==null)return;//在节点为空时返回 else { T.Fun(); PrePrderTraverse(T.leftNode); -- 递归遍历左右节点 如果需要，可以调整方法返回值记录数据，也可以传入委托方法来进行遍历操作 PrePrderTraverse(T.RightNode); } }中序遍历感觉有些奇怪 PrePrderTraverse(Tree T) if(T==null)return;//在节点为空时返回 else { PrePrderTraverse(T.leftNode); -- 递归遍历左右节点 如果需要，可以调整方法返回值记录数据，也可以传入委托方法来进行遍历操作 T.Fun(); PrePrderTraverse(T.RightNode); } }后续遍历 PrePrderTraverse(Tree T) if(T==null)return;//在节点为空时返回 else { PrePrderTraverse(T.leftNode); -- 递归遍历左右节点 如果需要，可以调整方法返回值记录数据，也可以传入委托方法来进行遍历操作 PrePrderTraverse(T.RightNode); T.Fun(); } }二叉树的层次遍历算法这个很符合我第一次想到的二叉树遍历方法。 遍历方式，（最开始就是把根节点加入队列）逐层将节点丢入队列，然后将遍历到的左右节点丢进队列中。（如果为空则不加入） 这样逐层遍历，直到队列为空，就是遍历完成。 ｛这个很简单，也很好理解，偷懒就不写了。｝ |
| CopyRight 2018-2019 实验室设备网 版权所有 |