最近数据结构看的还真是恶心额,脑子不好使,算法写不来额·····
二叉树一大堆概念性的东西,不过还是写吧。
二叉树(binary tree)
二叉树的基本形态
二叉树也是递归定义的,其结点有左右子树之分,逻辑上二叉树有五种基本形态:
(1)空二叉树——(a);
(2)只有一个根结点的二叉树——(b);
(3)只有左子树——(c);
(4)只有右子树——(d);
(5)完全二叉树——(e)
度(Degree):节点孩子的数目。
叶子(Leaf): 度为0的节点称为叶子。
深度(Depth):树中最大的层次(从最上0开始数)
满二叉树:一棵深度为k且有2^k -1个节点的二叉树。
完全二叉树:若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h层有叶子节点,并且叶子节点都是从左到右依次排布,这就是完全二叉树。
性质1:在二叉树的第i层上至多有2^(i-1)个节点(i >= 1)
性质2:深度为k的二叉树至多有2^k - 1个节点
性质3:任意一棵二叉树T,若其叶子节点数为n0,度为2的节点数为n2,则n0 = n2 + 1
对于完全二叉树:
性质4:具有n个节点的完全二叉树的深度是[log2n] + 1
性质5:有N个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系:
若I为结点编号则 如果I<>1,则其父结点的编号为I/2;
如果2*I<=N,则其左儿子(即左子树的根结点)的编号为2*I;若2*I>N,则无左儿子;
如果2*I+1<=N,则其右儿子的结点编号为2*I+1;若2*I+1>N,则无右儿子。
二叉树按层次遍历----队列实现
1.创建二叉树,输入#代表NULL,调用递归创建二叉树。
2.构建一个队列专门用来储存二叉树节点指针,先把根节点入队,假设是A,对A元素进行访问,然后对A的左右孩子依次入队,假设B,C。A出队列,再是对B进行访问,同样将B的左右孩子入队列,B出对列······重复以上,知道队列为空。
下面是的代码是实现按层次从上到下遍历二叉树:
分享到:
相关推荐
层次遍历的特点是,在所有未被访问结点的集合中,排列在已访问结点集合中最前⾯结点的左⼦树的根结点将最先被访问,然后是该结 点的右⼦树的根结点。这样,如果把已访问的结点放在⼀个队列中,那么,所有未被访问...
二叉树的层次遍历
按层次遍历二叉树的算法 简单易懂 按层次遍历二叉树的算法 简单易懂
老师布置的作业呐,自己做完调试运行了先序输入是EACBDGF,中序...先序遍历的二叉树:E A C B D G F 中序遍历的二叉树:A B C D E F G 后序遍历的二叉树:B D C A F G E ****************捞分下题目嗷=A=************
编写程序,用先序递归遍历法建立二叉树的二叉链表存储结构,然后输出其先序、中序、后序以及层次遍历结点访问次序。其中层次遍历的实现需使用循环队列。二叉树结点数据类型建议选用字符类型
用c++的模板类来实现二叉树,其中包含前序遍历,中序遍历,后序遍历,以及层次遍历。用了递归和非递归2中方法
二叉树的层次遍历 该程序使用队列实现了二叉树的层次遍历,同时使用了广义表表示法来创建二叉树。程序先创建好一棵二叉树,然后调用 levelOrder 函数即可得到该二叉树的层次遍历结果。
设计一个利用队列实现二叉树层次遍历的程序。假设二叉树结点的元素数据类型为字符型,二叉树以二叉链表存储。利用二叉树的递归结构性质,通过读取键盘输入的如图所示二叉树的先序序列,建立其二叉链表。
原创:leetcode 107. 二叉树的层次遍历 II【队列】* Definition for a binary tree node.
//初始化队列Q,用于保存当前结点左右孩子 if (T == NULL) return ERROR; p = T; visit(p->data); // 访问根节点 if (p->lchild) EnQueue(Q, p->lchild); // 若存在左孩子,左孩子进队列 if (p->rchild) ...
①初始化一个辅助队列 ②根结点入队 ③若队列非空,则队头结点出队,访问该结点,并将其左、右孩子插入队尾(如果有的话) ④重复③直至队列为空 ①初始化一个辅助队列
1.创建以二叉链表作存储结构的二叉树; 2.按前序遍历二叉树; 3.按中序遍历二叉树; 4.按后序遍历二叉树; 5.计算二叉树的单枝结点数; 6.按层次遍历二叉树。
按先序遍历的扩展序列建立二叉树的二叉链表存储结构,实现二叉树先序、中序、后序遍历的递归算法,实现二叉树中序遍历的非递归算法,实现二叉树层次遍历的非递归算法(要求使用顺序队列,调用顺序队列基本操作...
自己写得二叉树的遍历程序,包括递归遍历,栈的非递归遍历和队列的层次遍历,已在VC中运行通过,希望以此与大家交流交流,如有不妥之处希望大家能帮我修正,本着共同进步的目的。
二叉树层次遍历就是按照深度从上往下从左往右依次遍历,与常见的三种先、中、后序遍使用的递归不同,需要使用到队列来实现。
运用C语言实现链队列的创建、入队、出队以及二叉树的递归遍历和层次遍历等。
c代码-二叉树的层次遍历(队列实现)
本文主要通过python以非递归形式实现二叉树构造、前序遍历,中序遍历,后序遍历,层次遍历以及求二叉树的深度及叶子结点数。其他非递归形式的遍历,想必大多人应该都很清楚,就不再声明。如果你用C或者C++或者其他...
(1)输入字符序列,建立二叉链表。 (2)先序、中序、后序遍历二叉树:递归算法。 (3)中序遍历二叉树:非递归... (8)借助队列实现二叉树的层次遍历。 (9)在主函数中设计一个简单的菜单,分别调试上述算法。