二叉树深度遍历（二叉树的深度优先遍历就是二叉树前序遍历吗）

本文目录

• 二叉树的深度优先遍历就是二叉树前序遍历吗
• 算法设计 递归实现遍历二叉树，输出每个节点的度
• 树的深度遍历和先序遍历是一回事吗广度遍历呢
• 深度遍历二叉树这题怎么做，求高手指点一下，谢谢！

二叉树的深度优先遍历就是二叉树前序遍历吗

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

算法设计 递归实现遍历二叉树，输出每个节点的度

既然是树，除叶节点的度是1以外，其他节点的度都是2。#include《iostream》usingnamespacestd;structsegtree{inta,b;}tree;voidbuildtree(intl,intr,introot=0)/*建树*/{tree.b=r;if(l==r)return;intmid=(l+r)》》1;root《《=1;buildtree(l,mid,root+1);buildtree(l,mid,root+2);}voiddfs(intlevel,introot=0)/*深度遍历，递归法*/{for(inti=1;i《level;i++)cout《《’’;cout《《"Lv"《《level《《":\n";if(tree.b){root《《=1;dfs(level+1,root+1);dfs(level+1,root+2);}}struct{introot,level;}st;voidbfs()/*层次遍历*/{inttop=1,first=0;st.root=0;st.level=1;while(first《top){for(inti=st.level;i》1;i--)cout《《’’;cout《《"Lv"《《st.level《《":\n";if(tree.b){st.root*2+1;st.level+1;st.root*2+2;st.level+1;}first++;}}intmain(){intt,i;cout《《"以线段树为例，生成一个二叉树。\n\n";buildtree(1,9);cout《《"以深度遍历该树（深搜）：\n";dfs(1);cout《《"以层次遍历该树（宽搜）：\n";bfs();system("pause");return0;}

树的深度遍历和先序遍历是一回事吗广度遍历呢

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

深度遍历二叉树这题怎么做，求高手指点一下，谢谢！

-12-04 19:07按层次输入，这样可以根据实际需要建立树型，更为实用。但我的程序仍存在一个问题，就是遍历（2）：输出为空的孩子时都会多输出两个空孩子。不知道怎么改。 //二叉树结点类型为字符型的情况 #include 《stdio.h》 #include 《stdlib.h》 #include 《string.h》 #define null 0 #define MaxSize 1024 typedef struct tree { /*声明树的结构*/ struct tree *left; /*存放左子树的指针*/ struct tree *right; /*存放又子树的指针*/ char data; /*存放节点的内容*/ } treenode, * b_tree; /*声明二叉树的链表*/ b_tree Q; /*建立二叉树，按完全二叉树的层次遍历序列输入*/ b_tree createbtree() { char ch; int front,rear; b_tree root,s; root=NULL; front=1;rear=0; ch=getchar(); getchar(); while(ch!=’?’) { s=NULL; if(ch!=’.’) { s=(b_tree)malloc(sizeof(treenode)); s-》data=ch; s-》left=NULL; s-》right=NULL; } rear++; Q=s; if(rear==1) root=s; else { if(s&&Q) if(rear%2==0) Q-》left=s; else Q-》right=s; if(rear%2==1) front++; } ch=getchar(); getchar(); } return root; } /*先序遍历打印二叉排序树*/ void preorder_btree(b_tree root) { b_tree p=root; if(p!=null) { printf("%3c",p-》data); preorder_btree(p-》left); preorder_btree(p-》right); } } /* 中序遍历打印二叉排序树*/ void inorder_btree(b_tree root) { b_tree p=root; if(p!=null){ inorder_btree(p-》left ); printf("%3c",p-》data ); inorder_btree(p-》right ); } } /*后序遍历打印二叉排序树*/ void postorder_btree(b_tree root) { b_tree p=root; if(p!=null) { postorder_btree(p-》left ); postorder_btree(p-》right ); printf("%3c",p-》data ); } } /*求树的高度*/ int treedepth(b_tree bt) { int hl,hr,max; if(bt!=null) { hl=treedepth(bt-》left); hr=treedepth(bt-》right); max=(hl》hr)?hl:hr; return (max+1); } else return 0; } int count=0; /*求叶子结点总数*/ int leafcount(b_tree bt) { if(bt!=null) { leafcount(bt-》left); leafcount(bt-》right); if(bt-》left==null&&bt-》right==null) count++; } return count; } void paintleaf(b_tree bt) { if(bt!=null) { if(bt-》left==null&&bt-》right==null) printf("%3c",bt-》data); paintleaf(bt-》left); paintleaf(bt-》right); } } typedef b_tree ElemType ; /*定义队列结点类型*/ typedef struct QueueNode { ElemType data; struct QueueNode *next; } QueueNode; /*定义队列*/ typedef struct linkQueue { QueueNode * front; QueueNode * rear; }linkQueue; /*初始化队列*/ void initQueue(linkQueue * q) { q-》front=q-》rear =null; //----无头结点 } /*判断队列是否为空*/ int QueueEmpty(linkQueue * Q) { return (Q-》front==null)&&(Q-》rear==null); /*实际上只须判断队头指针是否为空即可*/ } /*入队操作*/ void EnQueue(linkQueue *Q,ElemType x) { /*将元素x插入链队列尾部*/ QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode)); /*申请新结点*/ p-》data=x; p-》next=null; if(QueueEmpty(Q)) /*将x插入空队列*/ //----无头结点 Q-》front=Q-》rear=p; else { /*x插入非空队列的尾*/ Q-》rear-》next=p; /*p链到原队尾结点后*/ Q-》rear=p; /*队尾指针指向新的尾*/ } } /*出队操作*/ ElemType DeQueue (linkQueue *Q) { ElemType x; QueueNode *p; if(QueueEmpty(Q)) { printf("Queue underflow");/*下溢*/ exit(1) ; } p=Q-》front; /*指向对头结点*/ x=p-》data; /*保存对头结点的数据*/ Q-》front=p-》next; /*将对头结点从链上摘下*/ if(Q-》rear==p)/*原队中只有一个结点，删去后队列变空，此时队头指针已为空*/ Q-》rear=NULL; free(p); /*释放被删队头结点*/ return x; /*返回原队头数据*/ } void visit(b_tree p) { printf("%3c",p-》data); } void breadthFirst2(b_tree root) { b_tree p,tmp; linkQueue * q; tmp=(treenode *)malloc(sizeof(treenode)); q=(linkQueue *)malloc(sizeof(linkQueue)); tmp-》data=’?’; initQueue(q); p=root; if(p!=null) { EnQueue(q,p); while(!QueueEmpty(q)) { p=DeQueue(q); visit(p); if(p-》data!=’?’) { if(p-》left!=null) EnQueue(q,p-》left); else EnQueue(q,tmp); if(p-》right!=null) EnQueue(q,p-》right); else EnQueue(q,tmp); } } } } void breadthFirst(b_tree root) { b_tree p; linkQueue * q; q=(linkQueue *)malloc(sizeof(linkQueue)); initQueue(q); p=root; if(p!=null) { EnQueue(q,p); while(!QueueEmpty(q)) { p=DeQueue(q); visit(p); if(p-》left!=null) EnQueue(q,p-》left); if(p-》right!=null) EnQueue(q,p-》right); } } } int main() { char nodelist; int len,flag; char cmd; b_tree root; printf("\n\n----------------------------------------------------\n"); printf("\n****欢迎测试和修正本程序！本程序用以研究二叉树。****\n"); printf("\n----------------------------------------------------\n\n"); do { printf("\n\n 请选择你要执行的操作:\n\n"); printf(" c,C......创建一棵二叉排序树\n"); printf(" a,A......结束本程序\n\n"); flag=0; do { if(flag!=0) printf("选择操作错误！请重新选择！\n"); fflush(stdin); scanf("%c",&cmd); flag++; }while(cmd!=’c’&&cmd!=’C’&&cmd!=’a’&&cmd!=’A’); if(cmd==’c’||cmd==’C’) { printf("请输入那你所要创建的二叉树的结点的值,以‘？’结束）：\n"); getchar(); root=createbtree(); do { flag=0; printf("\n\n 请选择你要对这棵二叉树所做的操作:\n\n"); printf(" x,X......先序遍历这棵二叉树\n"); printf(" z,Z......中序遍历这棵二叉树\n"); printf(" h,H......后序遍历这棵二叉树\n"); printf(" b,B......层次遍历这棵二叉树\n"); printf(" d,D......求这棵二叉树的高度\n"); printf(" y,Y......求这棵二叉树的叶子总数\n"); printf(" j,J......输出这棵二叉树的叶子结点\n"); printf(" q,Q......结束对这棵二叉树的操作\n\n"); do { if(flag!=0) printf("选择操作错误！请重新选择！\n"); fflush(stdin); scanf("%c",&cmd); flag++; }while(cmd!=’x’&&cmd!=’X’&&cmd!=’z’&&cmd!=’Z’&&cmd!=’h’&&cmd!=’H’&&cmd!=’b’&&cmd!=’B’&&cmd!=’d’&&cmd!=’D’&&cmd!=’y’&&cmd!=’Y’&&cmd!=’j’&&cmd!=’J’&&cmd!=’q’&&cmd!=’Q’); switch(cmd) { case ’x’: case ’X’: printf("\n先序遍历开始:\n"); preorder_btree(root); printf("\n先序遍历结束\n\n"); break; case ’z’: case ’Z’: printf("\n中序遍历开始:\n"); inorder_btree(root); printf("\n中序遍历结束\n\n"); break; case ’h’: case ’H’: printf("\n后序遍历开始:\n"); postorder_btree(root); printf("\n后序遍历结束\n\n"); break; case ’b’: case ’B’: printf("\n层次遍历开始:\n"); printf("遍历（1）：不输出为空的孩子\n"); breadthFirst(root); printf("\n"); printf("遍历（2）：输出为空的孩子\n"); breadthFirst2(root); printf("\n层次遍历结束\n\n"); break; case ’d’: case ’D’: printf("\n这棵二叉树的高度：\n%d\n\n",treedepth(root)); break; case ’y’: case ’Y’: count=0; count=leafcount(root); printf("\n这棵二叉树的叶子总数为:\n%d\n\n",count); count=0; break; case ’j’: case ’J’: printf("\n这棵二叉树的叶子结点为：\n"); paintleaf(root); printf("\n"); break; } }while(cmd!=’q’&&cmd!=’Q’); } }while(cmd!=’a’&&cmd!=’A’); printf("\n\n----------------------------\n\n"); printf("****谢谢使用！欢迎指正！****\n\n"); printf("----------------------------\n\n"); printf("作者：Remainder 学号：07082107 时间：2008.11.23\n\n\n\n"); return 0; } /*（10 （8 5 3 34 23 73 15 34 56 32）。。。。。。结点数据整型时 6 1 2 3 4 5 6 4 a b c d */