二叉树遍历（宽度优先）入门

二叉树遍历（宽度优先）入门

算法思路:

使用一个队列（可以是数组或链表）来完成。初始时只有一个根节点，然后每次取出一个结点，就把它的左右儿子（如果有）放入队列。

源代码如下：

　　 封装成头文件 "BinaryTree.h" 和与之对应的实现文件

 1 #ifndef BINARYTREE_H
 2 #define BINARYTREE_H
 3 
 4 typedef struct BinaryTree_node
 5 {
 6     int data;
 7     bool have_value;
 8     struct BinaryTree_node *left,*right;
 9 }BT_node;
10 
11 class BinaryTree
12 {
13     private:
14         BT_node *root;
15     private:
16         void add_BT(int data,char* str);
17         void removeall(BT_node *temp);
18     public:
19         BinaryTree();
20         ~BinaryTree();
21         BT_node* get_root();
22         void input_BT();
23         void output_BT();
24 };
25 
26 #endif // BINARYtREE_H

  1 #include "BinaryTree.h"
  2 
  3 #include<stdlib.h>
  4 #include<string.h>
  5 #include<stdio.h>
  6 #include<malloc.h>
  7 #include<ctype.h>
  8 using namespace std;
  9 
 10 void  BinaryTree::removeall(BT_node *root)
 11 {
 12     if(root!=0)
 13     {
 14         BinaryTree::removeall(root->left);
 15         BinaryTree::removeall(root->right);
 16         free(root);
 17     }
 18 }
 19 BinaryTree::BinaryTree()
 20 {
 21   root=(BT_node *)malloc(sizeof(BT_node));
 22 }
 23 BinaryTree::~BinaryTree()
 24 {
 25     removeall(root);
 26 }
 27 
 28 void BinaryTree::add_BT(int data,char str[])
 29 {
 30     BT_node *root_temp=root;
 31 
 32     for(int i=0;str[i];++i)
 33     {
 34         switch(str[i])
 35         {
 36             case 'L':
 37             case 'l':
 38                 {
 39                     if(root_temp->left==0)
 40                     {
 41                         root_temp->left=(BT_node *)malloc(sizeof(BT_node));
 42                         root_temp->left->have_value=false;
 43                         root_temp->left->left=0;
 44                         root_temp->left->right=0;
 45                     }
 46                     root_temp=root_temp->left;
 47                 }
 48                 break;
 49             case 'R':
 50             case 'r':
 51                 {
 52                     if(root_temp->right==0)
 53                     {
 54                         root_temp->right=(BT_node *)malloc(sizeof(BT_node));
 55                         root_temp->right->have_value=false;
 56                         root_temp->right->left=0;
 57                         root_temp->right->right=0;
 58                     }
 59                     root_temp=root_temp->right;
 60                 }break;
 61         }
 62         root_temp->data=data;
 63         if(!root_temp->have_value)
 64             root_temp->have_value=true;
 65     }
 66     root_temp->data=data;
 67     root_temp->have_value=true;
 68 }
 69 
 70 BT_node* BinaryTree::get_root()
 71 {
 72     return root;
 73 }
 74 
 75 void BinaryTree::input_BT()
 76 {
 77     char command[125];
 78     int  data;
 79     while(scanf("%s",command)&&strcmp(command,"()")!=0)
 80     {
 81         data=0;int i=1;
 82         while(isdigit(command[i]))
 83         {
 84             data=data*10+command[i]-48;
 85             ++i;
 86         }
 87         add_BT(data,&command[i]+1);
 88     }
 89 }
 90 
 91 void BinaryTree::output_BT()
 92 {
 93     int front_=0,rear=1;
 94     BT_node *queue_[256]={0};
 95     queue_[0]=root;
 96     while(front_ < rear)
 97     {
 98          BT_node *root_temp=queue_[front_++];
 99          if(!root_temp->have_value)
100          {
101             exit(0);
102          }
103         printf("%d	",root_temp->data);
104          if(root_temp->left != 0)
105             queue_[rear++]=root_temp->left;
106          if(root_temp->right != 0)
107             queue_[rear++]=root_temp->right;
108     }
109 }

测试文件 :

 1 #include <iostream>
 2 #include "BinaryTree.h"
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     BinaryTree test;
 8     test.input_BT();
 9     test.output_BT();
10     cout << "overed" << endl;
11     return 0;
12 }

注意：

　　在运行时，有规定的输入格式，如：

　　(1,) (2,L) (3,R) ()

　　其中(1,)为根，（2,L)表是根下左子树的值为2，(3,R)表示根下右子树的值为3。