二叉树非递归先序遍历出现读取访问权限冲突怎么解决


#include <stdio.h>
#include <stdlib.h>

//新建树的结构
typedef struct TreeNode {
 char data;
 struct TreeNode* lchild;
 struct TreeNode* rchild;
}TreeNode;

//定义栈的结构，用链表实现
typedef struct StackNode {
 TreeNode* data;
 struct StackNode* next;
}StackNode;

//创建二叉树
void createTree(TreeNode** T, char* data, int* index) {
 char ch;
 ch = data[*index];
 *index += 1;
 if (ch == '#') {
  //此时为空节点
  *T = NULL;
 }
 else {
  //此时不为空
  *T = (TreeNode*)malloc(sizeof(TreeNode));
  (*T) -> data = ch;
  //创建左子树，逻辑一致，进行递归
  createTree(&((*T)->lchild), data, index);
  //创建右子树，逻辑一致，进行递归
  createTree(&((*T)->rchild),data,index);
 }
}

//初始化栈
StackNode* initStack() {
 StackNode* S = (StackNode*)malloc(sizeof(StackNode));
 S->data = NULL;
 S->next = NULL;
 return S;
}

//进栈，头插法
void push(TreeNode* data, StackNode* S) {
 StackNode* node = (StackNode*)malloc(sizeof(StackNode));
 node->data = data;
 node->next = S->next;
 S->next = node;
}

//判断是否栈空
int isEmpty(StackNode* S) {
 if (S->next == NULL) {
  return 1;
 }
 else {
  return 0;
 }
}

//出栈
StackNode* pop(StackNode* S) {
 if (isEmpty(S)) {
  return NULL;
 }
 else {
  StackNode* node = S->next;
  S->next = node->next;
  return node;
 }
}

//先序遍历
void preOrder(TreeNode* T) {
 TreeNode* node = T;
 StackNode* S = initStack();
 while (node || !isEmpty(S)) {
  if (node) {                   //不为空
   printf("%c ", node->data);
   push(node, S);
   node = node->lchild;
  }
  else                         //为空
  {
   node = pop(S)->data;
   node = node->rchild;
  }
 }
}

int main(int argc, char* argv[]) {
 TreeNode* T;
 int index = 0;
 createTree(&T, argv[1], &index);
 preOrder(T);
 return 0;
}

img

主要问题在创建二叉树 void createTree(TreeNode** T, char* data, int* index) 函数里，修改如下，改动处见注释，供参考：

#include <stdio.h>
#include <stdlib.h>
//新建树的结构
typedef struct TreeNode {
    char   data;
    struct TreeNode* lchild;
    struct TreeNode* rchild;
}TreeNode;

//定义栈的结构，用链表实现
typedef struct StackNode {
    TreeNode* data;
    struct StackNode* next;
}StackNode;

//创建二叉树
void createTree(TreeNode** T, char* data, int* index) {
    char ch;
    ch = data[*index];
    *index += 1;
    if (ch == '#') {
       //此时为空节点
       *T = NULL;
    }
    else {
       //此时不为空
        *T = (TreeNode*)malloc(sizeof(TreeNode));
        (*T) ->data = ch;
       //创建左子树，逻辑一致，进行递归
       createTree(&((*T)->lchild), data, &(*index)); //修改
         //createTree(&((*T)->lchild), data, index);
       //创建右子树，逻辑一致，进行递归
       createTree(&((*T)->rchild),data,&(*index));  //修改
         //createTree(&((*T)->rchild),data,index);
    }
}

//初始化栈
StackNode* initStack() {
    StackNode* S = (StackNode*)malloc(sizeof(StackNode));
    S->data = NULL;
    S->next = NULL;
    return S;
}

//进栈，头插法
void push(TreeNode* data, StackNode* S) {
    StackNode* node = (StackNode*)malloc(sizeof(StackNode));
    node->data = data;
    node->next = S->next;
    S->next = node;
}

//判断是否栈空
int isEmpty(StackNode* S) {
    if (S->next == NULL) {
        return 1;
    }
    else {
        return 0;
    }
}

//出栈
StackNode* pop(StackNode* S) {
    if (isEmpty(S)) {
        return NULL;
    }
    else {
        StackNode* node = S->next;
        S->next = node->next;
        return node;
    }
}

//先序遍历
void preOrder(TreeNode* T) {
    TreeNode* node = T;
    StackNode* S = initStack();
    while (node || !isEmpty(S)) {
         if (node) { //不为空
             printf("%c ", node->data);
             push(node, S);
             node = node->lchild;
         }
         else//为空
         {
             node = pop(S)->data;
             node = node->rchild;
         }
    }
}

int main(int argc, char* argv[]) {
    char arv[] = {"12##3as3#####"}; // 修改
    TreeNode* T;
    int index = 0;
    createTree(&T, arv, &index);
    preOrder(T);

    return 0;
}

createTree()传的第二个参数是argv[1]，这个是字符，函数接收字符指针，函数里面试图使用数组的方式访问。应该传argv，不过其它地方还没仔细看。

在非递归方式下，先序遍历二叉树的算法通常使用栈数据结构来实现。读取访问权限冲突可能是由于需要同时访问同一节点或不同节点的两个或多个指针而导致的。可以通过以下方法解决这个问题：
1.使用辅助数据结构：可以用一个辅助栈来记录访问了哪些节点。在访问某个节点时，检查这个节点是否已经被访问过，如果已经被访问则不需要再次访问，直接跳过。如果还没有被访问，则将其入栈并进行访问。
2.修改节点的数据结构：将二叉树节点的数据结构进行修改，添加一个标志位来记录该节点是否已经被访问过。在访问该节点时，检查其标志位的值，如果已经被访问过，则不需要再次访问，直接跳过。如果还没有被访问，则将其标志位设置为“已访问”并进行访问。
3.使用迭代方式：另一种解决方法是使用迭代而不是递归的方式实现先序遍历。这种方法会比较复杂，但可以避免读取访问冲突。
无论采用哪种方法，解决读取访问权限冲突的关键在于在访问节点前，要判断该节点是否已经被访问过，如果已经被访问过，就不需要再次访问。

这段代码看起来没有明显的语法错误，但是在使用时可能会出现一些潜在的问题。以下是一些需要注意的地方：

  1. 代码假定命令行参数 argv[1] 包含了树的数据，但是在 main 函数中没有进行参数数量的检查。建议在使用 argv[1] 前先检查 argc 的值，确保命令行参数的正确使用。

  2. 在 createTree 函数中，当 ch 不等于 '#' 时，代码会动态分配内存来创建新的节点。但是没有对分配内存的情况进行错误处理，如内存分配失败的情况下应该进行适当的处理，例如返回错误代码或终止程序。

  3. 在 preOrder 函数中，如果栈 S 不为空但是节点 node 为空时，代码会出现问题。建议在访问 node 的成员之前，先检查其是否为 NULL。

  4. 在 preOrder 函数中，使用 pop(S)->data 来获取出栈的节点，并将其赋值给 node。然而，该节点的右子树可能为空，导致 node 被赋值为 NULL，下一次循环时会出现问题。应该修改为先将出栈的节点保存为临时变量，然后再获取其右子树。

下面是修改后的代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    char data;
    struct TreeNode* lchild;
    struct TreeNode* rchild;
} TreeNode;

typedef struct StackNode {
    TreeNode* data;
    struct StackNode* next;
} StackNode;

void createTree(TreeNode** T, char* data, int* index) {
    char ch;
    ch = data[*index];
    (*index)++;
    if (ch == '#') {
        *T = NULL;
    }
    else {
        *T = (TreeNode*)malloc(sizeof(TreeNode));
        if (*T == NULL) {
            printf("Memory allocation failed\n");
            exit(1);
        }
        (*T)->data = ch;
        createTree(&((*T)->lchild), data, index);
        createTree(&((*T)->rchild), data, index);
    }
}

StackNode* initStack() {
    StackNode* S = (StackNode*)malloc(sizeof(StackNode));
    if (S == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    S->data = NULL;
    S->next = NULL;
    return S;
}

void push(TreeNode* data, StackNode* S) {
    StackNode* node = (StackNode*)malloc(sizeof(StackNode));
    if (node == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    node->data = data;
    node->next = S->next;
    S->next = node;
}

int isEmpty(StackNode* S) {
    return (S->next == NULL);
}

StackNode* pop(StackNode* S) {
    if (isEmpty(S)) {
        return NULL;
    }
    else {
        StackNode* node = S->next;
        S->next = node->next;
        return node;
    }


}

void preOrder(TreeNode* T) {
    TreeNode* node = T;
    StackNode* S = initStack();
    while (node || !isEmpty(S)) {
        if (node) {
            printf("%c ", node->data);
            push(node, S);
            node = node->lchild;
        }
        else {
            StackNode* temp = pop(S);
            node = temp->data;
            node = node->rchild;
            free(temp);
        }
    }
}

int main(int argc, char* argv[]) {
    if (argc < 2) {
        printf("Not enough arguments\n");
        return 1;
    }

    TreeNode* T;
    int index = 0;
    createTree(&T, argv[1], &index);
    preOrder(T);
    return 0;
}

这些修改包括了错误处理和一些潜在的问题修复。希望能帮助到你！