二叉树这一章真难,请教各位

Question

为什么非递归二叉树，我二叉树输出不全啊

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define MAXSIZE 100

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

typedef struct StackNode{
    TreeNode *top;
    TreeNode *down;
    int length;
}StackNode;

void push(StackNode *stacknode,TreeNode *treeList){
    if(treeList->data!='#'){
        stacknode->top=treeList;
        stacknode->top++;
    }
    
}

TreeNode* pop(StackNode *stacknode){
    TreeNode *node;
    stacknode->top--;
    node=stacknode->top;
    printf("出栈一个结点:%c\n",node->data);
    return node;
}
void PreOrderIn(TreeNode *treeList){//非递归先序
    StackNode *stacknode;
    TreeNode *node;
    stacknode=(StackNode *)malloc(sizeof(StackNode));
    stacknode->top=(StackNode *)malloc(sizeof(StackNode)*MAXSIZE);
    stacknode->down=stacknode->top; 
    if(treeList!=NULL){
        push(stacknode,treeList);
    }
    while(stacknode!=NULL){
        node=pop(stacknode);
        if(node->rchild!=NULL){
            push(stacknode,node->rchild);
        }
        if(node->lchild!=NULL){
            push(stacknode,node->lchild);
        }
    }
}



TreeNode* create(TreeNode *treeList){
    char value;
    printf("请输入一个字符\n");
    scanf(" %c",&value);//注意啊，回车也会被当作一个字符 
     if(value=='#'){
        treeList=NULL;
    }else{
        treeList=(TreeNode *)malloc(sizeof(TreeNode));
        treeList->data=value;
            //由于每一层都有返回值，
        //所以我们必须保存每次递归后的左右节点的值，否则链表就会连接不起来 
        treeList->lchild=create(treeList->lchild);
        treeList->rchild=create(treeList->rchild);
    }
    return treeList;
    
} 




int main(){
    TreeNode *treeList;
    treeList=create(treeList);
    PreOrderIn(treeList);
    return 0;
}

Answer 1

修改如下，供参考：

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define MAXSIZE 100

typedef struct _TreeNode {
    char data;
    struct _TreeNode* lchild;
    struct _TreeNode* rchild;
}TreeNode;
typedef struct _StackNode {
    TreeNode* top[MAXSIZE];  //修改
       //TreeNode* down;     修改
    int length;
}StackNode;
void push(StackNode* stacknode, TreeNode* treeList) {
    if (treeList != NULL) { //(treeList->data != '#') { 修改
        stacknode->top[stacknode->length] = treeList;  //修改
        stacknode->length++;                 //修改
        //stacknode->top++;                  //修改
    }
}
TreeNode* pop(StackNode* stacknode) {
    TreeNode* node;
    if (stacknode->length != 0)        //修改
        stacknode->length--;           //修改
    node = stacknode->top[stacknode->length]; //修改
    //printf("1--出栈一个结点:%c\n", node->data);
    return  node;
}
void PreOrderIn(TreeNode* treeList) {//非递归先序
    StackNode* stacknode;
    TreeNode* node;
    stacknode = (StackNode*)malloc(sizeof(StackNode));
    //stacknode->top = (TreeNode*)malloc(sizeof(TreeNode) * MAXSIZE);//修改
    //stacknode->top = (StackNode*)malloc(sizeof(StackNode) * MAXSIZE);//修改
    //stacknode->down = stacknode->top;                               //修改
    stacknode->length = 0;                                            //修改
    if (treeList != NULL) {
        push(stacknode, treeList);    
        while (stacknode->length != 0) {  //(stacknode != NULL)  //修改
            node = pop(stacknode);
            printf("2--出栈一个结点:%c\n", node->data);        //修改
            if (node->rchild != NULL) {
                push(stacknode, node->rchild);
            }
            if (node->lchild != NULL) {
                push(stacknode, node->lchild);
            }
        }
    } //修改
}

TreeNode* create(TreeNode* treeList) {
    char value;
    printf("请输入一个字符\n");
    scanf(" %c", &value);//注意啊，回车也会被当作一个字符 
    if (value == '#') {
        treeList = NULL;
    }
    else {
        treeList = (TreeNode*)malloc(sizeof(TreeNode));
        treeList->data = value;
        //由于每一层都有返回值，
    //所以我们必须保存每次递归后的左右节点的值，否则链表就会连接不起来 
        treeList->lchild = create(treeList->lchild);
        treeList->rchild = create(treeList->rchild);
    }
    return treeList;

}

int main() {
    TreeNode* treeList;
    treeList = create(treeList);
    PreOrderIn(treeList);
    return 0;
}