没有
我正在实现以下算法：
1.创建一个空的队列。
2.将列表的第一个节点作为root将其加入到队列中。
3.直到我们到达列表的结尾，请执行以下操作。
-
从队列中排出一个节点。这是当前的父母。
-
列表中的两个节点，将它们添加为当前父母的孩子。
-
将两个节点加入队列。
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <queue>
using namespace std;
struct Node{
int data;
struct Node* next;
};
typedef struct Node* NODE;
NODE createNode(int data){
NODE newNode = (NODE) malloc (sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return (newNode);
}
void insertAtEnd(NODE* head, int data){
NODE newNode = createNode(data);
if(*head == NULL){
*head = newNode;
return ;
}
NODE temp = *head;
while(temp->next){
temp = temp->next;
}
temp->next = newNode;
newNode->next = NULL;
return;
}
struct tree_node{
int data;
struct tree_node* left;
struct tree_node* right;
};
typedef struct tree_node* T_NODE;
T_NODE createTreeNode(int data){
T_NODE newNode = new tree_node;
newNode->right = NULL;
newNode->left = NULL;
newNode->data = data;
return newNode;
}
void inorderTraversal(){}
T_NODE convertListIntoCBT(NODE head){
T_NODE root;
if(head){
queue<T_NODE>q;
root=createTreeNode(head->data);
if(!root){
cout << "Error creating root"<<endl;
exit(-1);
}
q.push(root);
T_NODE temp=NULL , parent=NULL;
while(head->next){
temp = q.front();
q.pop();
parent = temp;
head = head->next;
parent->left = createTreeNode(head->data);
q.push(parent->left);
head = head->next;
parent->right = createTreeNode(head->data);
q.push(parent->right);
}
return root;
}
}
int main(){
NODE head = NULL;
insertAtEnd(&head,36);
insertAtEnd(&head,30);
insertAtEnd(&head,25);
insertAtEnd(&head,15);
insertAtEnd(&head,12);
insertAtEnd(&head,10);
//convert the given linked list into complete binary tree
T_NODE new_root = convertListIntoCBT(head);
return 0;
}
我尝试使用GDB进行调试，并得到以下结果：
Program received signal SIGSEGV, Segmentation fault.
0x0000000000400e5a in convertListIntoCBT(Node*) ()
(gdb) backtrace
0 0x0000000000400e5a in convertListIntoCBT(Node*) ()
1 0x0000000000400fa2 in main ()
(gdb)
我无法弄清楚为什么在功能开始时我会得到分割故障！？
看来，您的while(head->next)循环中有一些缺少的检查。我认为您应该将支票放在接下来和接下来的次要情况下，因为您都在循环中使用两者：
while(head->next && head->next->next)
{
//...
}
或在循环中第二次前进之前，可能会再次检查：
while(head->next){
temp = q.front();
q.pop();
parent = temp;
head = head->next;
parent->left = createTreeNode(head->data);
q.push(parent->left);
if(head->next) // <-- check again here
{
head = head->next;
parent->right = createTreeNode(head->data);
q.push(parent->right);
}
}
也在评论中的建议中，不要将C样式与C 样式混合在一起，选择一种语言并尝试坚持下去。我在这里谈论使用malloc和typedef struct，尽管它们编译了，但它们不是"通常" C 。
正如其他答案所述，问题在于 while语句。
函数convertListIntoCBT中的另一个问题是，如果head == nullptr。
return使用-g构建时，您应该有可辩论的二进制文件：
% lldb 1
(lldb) target create "1"
Current executable set to '1' (x86_64).
(lldb) r
Process 44386 launched: '/Users/paul/src/cpp/1' (x86_64)
Process 44386 stopped
* thread #1: tid = 0xb6153, 0x0000000100001217 1`convertListIntoCBT(head=0x0000000000000000) + 887 at 1.cpp:81, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x0)
frame #0: 0x0000000100001217 1`convertListIntoCBT(head=0x0000000000000000) + 887 at 1.cpp:81
78 parent->left = createTreeNode(head->data);
79 q.push(parent->left);
80 head = head->next;
-> 81 parent->right = createTreeNode(head->data);
82 q.push(parent->right);
83 }
84
(lldb) bt
* thread #1: tid = 0xb6153, 0x0000000100001217 1`convertListIntoCBT(head=0x0000000000000000) + 887 at 1.cpp:81, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x0)
* frame #0: 0x0000000100001217 1`convertListIntoCBT(head=0x0000000000000000) + 887 at 1.cpp:81
frame #1: 0x0000000100001484 1`main + 116 at 1.cpp:100
frame #2: 0x00007fff9cffe5ad libdyld.dylib`start + 1
frame #3: 0x00007fff9cffe5ad libdyld.dylib`start + 1
(lldb) p parent
(T_NODE) $0 = 0x0000000100300320
(lldb) p head
(NODE) $1 = 0x0000000000000000
因此，在第80行中，您可以通过执行head = head->next使head成为CC_11。在第81行中，您可以访问head->data，而head == nullptr获取Segfault。
关键错误是该代码：
while(head->next){
temp = q.front();
q.pop();
parent = temp;
head = head->next;
parent->left = createTreeNode(head->data);
q.push(parent->left);
head = head->next;
parent->right = createTreeNode(head->data);
q.push(parent->right);
}
未经检查头是否为空，重复最后三行。在这种情况下，列表在该功能期望的函数之前就结束了，并且程序试图放弃NULLPTR来崩溃。将检查添加到转换listintocbt和流产工作，或者您可以构建一种将列表中正确数量元素的方法构建到函数中。