二叉树的深度遍历和广度遍历 二叉树的创建 – haodro.com

我写了一个二叉树 你给看看 一定能行的 我自己用了#include “stdio.h“#include “malloc.h“#include “string.h“#include “stdlib.h“#define Max 20 //结点的最大个数typedef struct BinTNode{ char data; struct BinTNode *lchild,*rchild;}BinTNode,*BinTree; //自定义二叉树的结点类型 //定义二叉树的指针int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数//==========以广义表显示二叉树==============void DisTree(BinTree T){ if(T) { printf(“%c“,T-》data); if((T-》lchild)||(T-》rchild)) { if(T-》lchild) { printf(“%c“,’(’); DisTree(T-》lchild); } if(T-》rchild) { printf(“%c“,’,’); DisTree(T-》rchild); printf(“%c“,’)’); } } }}//==========基于先序遍历算法创建二叉树==============//=====要求输入先序序列，其中加入虚结点“#“以示空指针的位置==========BinTree CreatBinTree(BinTree T){ char ch; ch=getchar(); if(ch==’#’) T=NULL; else { if(!(T=(BinTNode *)malloc(sizeof(BinTNode)))) printf(“Error!“); T-》data=ch; T-》lchild=CreatBinTree(T-》lchild); T-》rchild=CreatBinTree(T-》rchild); } return T; }//========NLR 先序遍历=============void Preorder(BinTree T){ if(T) { printf(“%c“,T-》data); Preorder(T-》lchild); Preorder(T-》rchild); } }//========LNR 中序遍历===============void Inorder(BinTree T){ if(T){ Inorder(T-》lchild); printf(“%c“,T-》data); Inorder(T-》rchild); } }//==========LRN 后序遍历============void Postorder(BinTree T){ if(T){ Postorder(T-》lchild); Postorder(T-》rchild); printf(“%c“,T-》data); } }//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========int TreeDepth(BinTree T){ int hl,hr,max; if(T){ hl=TreeDepth(T-》lchild); //求左深度 hr=TreeDepth(T-》rchild); //求右深度 max=hl》hr? hl:hr; //取左右深度的最大值 NodeNum=NodeNum+1; //求结点数 if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0，即为叶子。 return(max+1); } else return(0);}//====利用“先进先出“（FIFO）队列，按层次遍历二叉树==========void Levelorder(BinTree T){ int front=0,rear=1; BinTNode *cq,*p; //定义结点的指针数组cq cq=T; //根入队 while(front!=rear) { front=(front+1)%NodeNum; p=cq; //出队 printf(“%c“,p-》data); //出队，输出结点的值 if(p-》lchild!=NULL){ rear=(rear+1)%NodeNum; cq=p-》lchild; //左子树入队 } if(p-》rchild!=NULL){ rear=(rear+1)%NodeNum; cq=p-》rchild; //右子树入队 } }}//==========主函数=================void main(){ BinTree T,root; int i,depth; printf(“\n“); printf(“输入完全二叉树的先序序列:“); //输入完全二叉树的先序序列， // 用#代表虚结点，如ABD###CE##F## root=CreatBinTree(T); //创建二叉树，返回根结点 DisTree(root); printf(“\n“); do //从菜单中选择遍历方式，输入序号。 { printf(“\t********** 菜单 ************\n“); printf(“\n“); printf(“\t1: 先序遍历\n“); printf(“\t2: 中序遍历\n“); printf(“\t3: 后序遍历\n“); printf(“\t4: 该树的深度,结点数,叶子数\n“); printf(“\t5: 层次遍历\n“); //按层次遍历之前，先选择4，求出该树的结点数。 printf(“\t0: 退出\n“); printf(“\t*******************************\n“); scanf(“%d“,&i); //输入菜单序号（0-5） switch(i) { case 1: {printf(“Print Bin_tree Preorder: “); Preorder(root); //先序遍历 }break; case 2: {printf(“Print Bin_Tree Inorder: “); Inorder(root); //中序遍历 }break; case 3: {printf(“Print Bin_Tree Postorder: “); Postorder(root); //后序遍历 }break; case 4: {depth=TreeDepth(root); //求树的深度及叶子数 printf(“树深=%d 树总结点数=%d“,depth,NodeNum); printf(“ 树叶子数=%d“,leaf); }break; case 5: {printf(“LevePrint Bin_Tree: “); Levelorder(root); //按层次遍历 }break; default: exit(1); } }while(i》=0&&i《6);}兄弟你看看 不懂再往下留言 记得给我的劳动成果一点点奖励哦！！

对二叉树树有前序遍历，中序遍历，后序遍历，分层遍历。对图有深度优先遍历和广度优先遍历。

二叉树遍历方式分为深度优先搜索和宽度优先搜索

很简单，递归调用，先处理根数据再处理左子树，右子树。中根序和后根序与此类似，调换一下数据处理顺序就可以了

后面还要分析非递归的遍历，分析算法复杂度

先序，后序，中序针对二叉树。深度、广度针对普通树。深度遍历：从树根开始扫描，顶层扫描完了，从一层最左（也可以右）面的结点往下层扫描，直到下层已无结点，这时所有靠最左（右）的结点全部扫描完毕，从树梢往上退一层，看这层旁有无兄弟结点，有的话还是一样从最左（右）边开始扫描，这是个递归概念，利用这一方法来遍历整棵树。广度遍历：从树根开始扫描，顶层扫描完了，扫描一层的所有结点，扫描二层的所有结点，……，扫描最底层的结点。

一、什么是深度优先遍历 深度优先遍历算法是经典的图论算法。从某个节点v出发开始进行搜索。不断搜索直到该节点所有的边都被遍历完，当节点v所有的边都被遍历完以后，深度优先遍历算法则需要回溯到v以前驱节点来继续搜索这个节点。 注意：深度优先遍历问题一定要按照规则尝试所有的可能才行。

二、二叉树

2.二叉树类型 二叉树类型：空二叉树、满二叉树、完全二叉树、完美二叉树、平衡二叉树。

空二叉树：有零个节点 完美二叉树：每一层节点都是满的二叉树（如1中举例的图） 满二叉树：每一个节点都有零个或者两个子节点 完全二叉树：出最后一层外，每一层节点都是满的，并且最后一层节点全部从左排列 平衡二叉树：每个节点的两个子树的深度相差不超过1.

注：国内对完美二叉树和满二叉树定义相同 3.二叉树相关术语 术语 解释 度 节点的度为节点的子树个数 叶子节点 度为零的节点 分支节点 度不为零的节点 孩子节点 节点下的两个子节点 双亲节点 节点上一层的源节点 兄弟节点 拥有同一双亲节点的节点 根 二叉树的源头节点 深度 二叉树中节点的层的数量

DLR（先序）： LDR（中序）： LRD(后序）： 注意：L代表左子树R代表右子树；D代表根

6.深度优先遍历和广度优先遍历 深度优先遍历：前序、中序和后序都是深度优先遍历 从根节点出发直奔最远节点， 广度优先遍历：首先访问举例根节点最近的节点，按层次递进，以广度优先遍历上图的顺序为：1-2-3-4-5-6-7 三、面试题+励志 企鹅运维面试题： 1.二叉树遍历顺序：看上文 2.用你熟悉的语言说说怎么创建二叉树？ python看上文

二叉树的深度计算，首先要判断节点，以下是计算二叉树的详细步骤：

1、一颗树只有一个节点，它的深度是1；

2、二叉树的根节点只有左子树而没有右子树，那么可以判断，二叉树的深度应该是其左子树的深度加1；

3、二叉树的根节点只有右子树而没有左子树，那么可以判断，那么二叉树的深度应该是其右树的深度加1；

4、二叉树的根节点既有右子树又有左子树，那么可以判断，那么二叉树的深度应该是其左右子树的深度较大值加1。

一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。

具有n个节点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2k-1个叶子节点，至多有2k-1个节点。

二叉树深度的性质：

1、在非空二叉树中，第i层的结点总数不超过, i》=1；

2、深度为h的二叉树最多有个结点(h》=1)，最少有h个结点；

3、对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

4、具有n个结点的完全二叉树的深度为

5、有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

若I为结点编号则 如果I》1，则其父结点的编号为I/2；

如果2*I《=N，则其左孩子（即左子树的根结点）的编号为2*I；若2*I》N，则无左孩子；

这是因为图的深度优先遍历算法先访问所在结点，再访问它的邻接点。与二叉树的先序遍历先访问子树的根结点，再访问它的孩子结点（邻接点）类似。图的广度优先遍历算法类似于二叉树的按层次遍历。

中序遍历的递归版本是：也就是一路往左走到底，左边走不通了，再往右边走；所以中序遍历遵循的还是DFS

dfs(root.left)

打印节点 root

dfs(root.right)

如下：先走左子树，而且会按照 深度优先遍历 的原则往深处探，走4-3-1-2 返回的时候把这个值返回去：maxGain = Math.max(maxGain, leftValue+rightValue+root.val);

总结深度优先与广度优先的区别1、区别 1） 二叉树的深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列。 2） 深度优先遍历：对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。要特别注意的是，二叉树的深度优先遍历比较特殊，可以细分为先序遍历、中序遍历、后序遍历。具体说明如下：先序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树。中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树。后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。 广度优先遍历：又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。　　　 3）深度优先搜素算法：不全部保留结点，占用空间少；有回溯操作(即有入栈、出栈操作)，运行速度慢。 广度优先搜索算法：保留全部结点，占用空间大； 无回溯操作(即无入栈、出栈操作)，运行速度快。