域名查询备案查询武汉官网优化公司

二叉树中的深度优先遍历DFS和广度优先遍历BFS，是对树的一种很常见操作。特别是树的深度优先遍历，常见方式有三种：前序，中序和后序。

#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;
typedef struct Node {int data;struct Node *left;struct Node *right;
} Node ;
void create_btree(Node **root,const int data)
{if(root==NULL){fprintf(stdout,"arg is illegal");exit(-1);}if(*root==NULL){*root = (Node*)malloc(sizeof(Node));(*root)->data = data;(*root)->left = NULL;(*root)->right = NULL;} else {Node *p = *root;if(p->left==NULL){create_btree(&(p->left),data);} else if(p->right==NULL) {create_btree(&(p->right),data);} else {create_btree(&(p->left),data);}}
}
void BFS(Node *root)
{int head = 0;int end = 0;vector<Node*> v;if(root==NULL){return ;}v.push_back(root);while(v[end]!=NULL){end = v.size();for(int i=head;i<end;i++){if(v[i]->left!=NULL){v.push_back(v[i]->left);}if(v[i]->right!=NULL){v.push_back(v[i]->right);}head++;}}for(int i=0;i<v.size();i++){printf("%d ",v[i]->data);}
}
void DFS(Node *root)
{if(root==NULL){return ;} else {DFS(root->left);  //调整语句的先后顺序，可实现树的前序，中序和后序遍历printf("%d ",root->data);DFS(root->right);}
}
int main(void)
{int a[] = {1,2,3,4,5,6,7};const int len = sizeof(a)/sizeof(int);Node *root = NULL;for(int i=0;i<len;i++){create_btree(&root,a[i]);}DFS(root);printf("\n");BFS(root);return 0;
}

二叉树结构图：

                      1

                   /       \

                 2        3

              /     \

           4       5

         /    \

      6        7

所以广度优先遍历的结构是：1    2     3     4    5    6   7   ；中序遍历的结果是：6   4   7   2    5    1   3