bitree.png

# 一、递归法

```#include <iostream>
#include <malloc.h>
using namespace std;
struct Node
{
struct Node *lchild;//左孩子指针
struct Node *rchild;//右孩子指针
int data;           //节点数值
};
//创建结点
Node* createTreeNode(int data)
{
Node *n=(Node *)malloc(sizeof(Node));
n->data = data;
n->lchild = NULL;
n->rchild = NULL;
return n;
}
//遍历第level层的所有结点
int printNodeAtLevel(Node *root, int level)
{
if(root == NULL || level < 0)
{
return 0;
}
if(level == 0)
{
cout << root -> data << " ";
return 1;
}
return printNodeAtLevel(root -> lchild, level - 1) + printNodeAtLevel(root -> rchild, level - 1);
}
//遍历所有层
void levelTraverse(Node *root)
{
for(int level = 0; ; level++)
{
if(!printNodeAtLevel(root, level))
{
break;
}
}
}
int main()
{
Node* n1 = createTreeNode(1);
Node* n2 = createTreeNode(2);
Node* n3 = createTreeNode(3);
Node* n4 = createTreeNode(4);
Node* n5 = createTreeNode(5);
Node* n6 = createTreeNode(6);
Node* n7 = createTreeNode(7);
Node* n8 = createTreeNode(8);
n1->lchild = n2;
n1->rchild = n3;
n2->lchild = n4;
n2->rchild = n5;
n3->rchild = n6;
n6->lchild = n7;
n6->rchild = n8;
levelTraverse(n1);
return 0;
}```

`1 2 3 4 5 6 7 8 `

# 二、使用数组和两个游标的非递归方法

```#include <iostream>
#include <malloc.h>
#include <vector>
using namespace std;
struct Node
{
struct Node *lchild;//左孩子指针
struct Node *rchild;//右孩子指针
int data;           //节点数值
};
//创建结点
Node* createTreeNode(int data)
{
Node *n=(Node *)malloc(sizeof(Node));
n->data = data;
n->lchild = NULL;
n->rchild = NULL;
return n;
}
//分层遍历
void levelTraverse(Node *root)
{
if(root == NULL)
{
return;
}
vector<Node *> vec;
vec.push_back(root);
int cur = 0;
int last = vec.size();
while(cur < (int)vec.size())
{
//定位last为当前行最后一个节点的下一个位置，即下行的首位置
last = vec.size();
while(cur < last)   //cur位于当前行时
{
cout << vec[cur] -> data << " ";
if(vec[cur] -> lchild)
{
vec.push_back(vec[cur] -> lchild);
}
if(vec[cur] -> rchild)
{
vec.push_back(vec[cur] -> rchild);
}
cur++;//cur后移
}
cout << endl;//当cur与last相等时，说明该层访问结束，换行
}
}
int main()
{
Node* n1 = createTreeNode(1);
Node* n2 = createTreeNode(2);
Node* n3 = createTreeNode(3);
Node* n4 = createTreeNode(4);
Node* n5 = createTreeNode(5);
Node* n6 = createTreeNode(6);
Node* n7 = createTreeNode(7);
Node* n8 = createTreeNode(8);
n1->lchild = n2;
n1->rchild = n3;
n2->lchild = n4;
n2->rchild = n5;
n3->rchild = n6;
n6->lchild = n7;
n6->rchild = n8;
levelTraverse(n1);
return 0;
}```

```1
2 3
4 5 6
7 8```

241 篇文章45 人订阅

0 条评论

## 相关文章

8805

791

1461

4069

1630

671

1925

913

### HashSet/HashMap详解

HashMap和HashSet是Java Collection接口两个重要的成员，其中HashMap是Map接口常用的实现类，HashSet是Set接口常用...

23410

1233