如何实现将树的结点入队，出队？或者入栈，出栈 （同时写出该队列/栈的结构体）
在非递归树的相关问题中，很多时候需要用到队列，栈。如何写一个以树的结点为内容的队列或栈呢？
本人数据结构初学者，我自己写了一部分，也不知道对不对：
typedef struct Queue
{
struct Queue *next;
}StackQ,*Qpre;
typedef struct
{
Qpre front;
Qpre rear;
}LinkQueue;
void InQueue(LinkQueue* p,BitNode* T)
{
p->rear->next=T;
p->rear=T;
} //入队
BitNode* DeQueue(LinkQueue* p)
{
BitNode* pre;
if(p->front==p->rear)
printf("队空");
else
{
pre=p->front->next;
p->front->next=pre->next;
if(pre->next==null)
p->front=p->rear;
pre->next=null；
return pre;
}
} // 出队
求解！
首先你需要构建树。
构建如图所示的树。
你可以用一个数组来表示,也可以用结构体，结构体在这篇教程中比较复杂，暂不展示·
char* tree = new char['A', 'B', 'C', 'D', 'E', '*', 'F'];
显而易见的，a[0] 是根节点 a[1],[2] 是其子节点。
D----a[3],E----a[4] 是B的子节点,'*'----a[5],F---a[6] 是 C的子节点。
你可以 很显然的发现，a[0] 的子节点 是a[0*2+1],a[0*2+2]
a[4]的子节点 是a[4*2+1,4*2+2]
深搜算法是什么呢？ 是一个栈。
根节点 push A 栈底====>栈顶 A
A有未访问的子节点吗？有B。B已访问 push B A B
B有未访问的子节点吗？有D D已访问 push D A B D
D有未访问的子节点吗？ 没有 pop A B
B有未访问的子节点吗？ 有E E已访问 push E A B E
E有未访问的子节点吗？ 没有 pop A B
B有未访问的子节点吗？ 没有 pop A
A有未访问的子节点吗？有C C已访问 push C A C
C有未访问的子节点吗？ 有F F已访问 push F A C F
F有未访问的子节点吗？没有 pop A C
C有未访问的子节点吗？没有 pop A
A有未访问的子节点吗？没有 pop 空
广搜是一个队列
把A 扔进队列，问 A的子节点？ B C 队列 A B C
A出队 B C
问 B 的子节点 D E 队列 B C D E
B 出队 C D E
问 C 的子节点 F C D E F
由于 C D E F 都没有 子节点。
所以他们的操作就是一个一个排好了出队。
队列：D E F
队列：E F
队列：F
树的深搜
#include<iostream>
#include <vector>
#include <stack>
#include <queue>
#pragma warning(disable:4996)
using namespace std;
int n = 8;
vector<char> tree = { 'A', 'B', 'C', 'D', 'E', '*', 'F' };
vector<int> visited = { 0,0,0,0,0,0,0,0 };
int hasChild(int index) {
if (index * 2 + 1 >= 7) {
return -1;
}
// 左孩子
if (!visited[index * 2 + 1] && tree[index * 2 + 1] != '*') {
return index * 2 + 1;
}
// 右孩子
else if (!visited[index * 2 + 2] && tree[index * 2 + 2] != '*') {
return index * 2 + 2;
}
else {
return -1;
}
}
int main() {
stack<int> dfs;
int node = 0;
dfs.push(node);
while (dfs.size() != 0) {
// 查询子节点
// 子节点在上文中说过,是 node*2+1 node*2+2
node = dfs.top();
int child = hasChild(node);
if ( child != -1) {
dfs.push(child);
visited[child] = 1;
node = dfs.top();
}
else {
node = dfs.top();
dfs.pop();
}
//,不在算法内,只是为了打印栈内元素
cout << "栈内元素:从栈顶到栈底=>";
stack<int> s2;
s2 = dfs;
while (!s2.empty()) {
cout << tree[s2.top()] << " ";
s2.pop();
}
cout << endl;
}
cout << endl;
}
此处使用了上文,用数组的形式来存树，并利用c++已经封装好的栈来展示深搜的过程。
这是运行结果。
#include<iostream>
#include <vector>
#include <stack>
#include <queue>
#pragma warning(disable:4996)
using namespace std;
int n = 8;
vector<char> tree = { 'A', 'B', 'C', 'D', 'E', '*', 'F' };
vector<int> visited = { 0,0,0,0,0,0,0,0 };
int hasChild(int index) {
if (index * 2 + 1 >= 7) {
return -1;
}
// 左孩子
if (!visited[index * 2 + 1] && tree[index * 2 + 1] != '*') {
return index * 2 + 1;
}
// 右孩子
else if (!visited[index * 2 + 2] && tree[index * 2 + 2] != '*') {
return index * 2 + 2;
}
else {
return -1;
}
}
int main() {
stack<int> dfs;
int node = 0;
dfs.push(node);
while (dfs.size() != 0) {
// 查询子节点
// 子节点在上文中说过,是 node*2+1 node*2+2
node = dfs.top();
int child = hasChild(node);
if ( child != -1) {
dfs.push(child);
visited[child] = 1;
node = dfs.top();
}
else {
node = dfs.top();
dfs.pop();
}
//,不在算法内,只是为了打印栈内元素
cout << "栈内元素:从栈顶到栈底=>";
stack<int> s2;
s2 = dfs;
while (!s2.empty()) {
cout << tree[s2.top()] << " ";
s2.pop();
}
cout << endl;
}
cout << endl;
visited = { 0,0,0,0,0,0,0,0 };
queue<int> bfs;
node = 0;
bfs.push(node);
while (bfs.size() != 0) {
node = bfs.front();
int child = hasChild(node);
// 第一次访问左孩子
if (child != -1) {
bfs.push(child);
visited[child] = 1;
node = bfs.front();
}
child = hasChild(node);
if (child != -1) {
bfs.push(child);
visited[child] = 1;
node = bfs.front();
}
else {
node = bfs.front();
bfs.pop();
}
//,不在算法内,只是为了打印栈内元素
cout << "队内元素:从队首到队尾=>";
queue<int> s2;
s2 = bfs;
while (!s2.empty()) {
cout << tree[s2.front()] << " ";
s2.pop();
}
cout << endl;
}
cout << endl;
}
这是深搜广搜的版本。
