C格式字符串转为二叉树

　　最近在LeetCode做题,二叉树出现错误时不好排查,于是自己写了一个函数,将前序遍历格式字串转换成二叉树。

　　形如 "AB#D##C##" 的字符串，"#"表示孩子节点为空，算法如下：

　　1.当前节点进栈 push(s,t)

　　2.出栈: pcur=pop(s) ,判断当前字符
　　　　a 不等于'#'，申请新的节点pnew并赋给pcur的左或右孩子，当右孩子时将标记置真，pcur进栈，pnew进栈
　　　　b 等于'#'，如果当前为左孩子，左孩子置null，pcur进栈；
　　　　　　当前为右孩子，右孩子置空，父节点出栈。如果pcur是父节点的左孩子，终止寻找；否则保存父节点为当前节点，继续寻找。

　　代码如下：

TreeNode *creat_tree(char *str){

    if(  == strlen(str) ) return NULL;

    TreeNode *t = (TreeNode *)malloc(sizeof(TreeNode));

    TreeNode *pcur = NULL, *pnew = NULL;

    Stack *s = init_s();

    bool left_child = true;

    t->data = *str;

    push(s,t);

    while( '\0' != *++str ){

        pcur = pop(s);

        printf("  pcur->data:%c, val:%c\n",pcur->data,*str );

        if( '#' != *str ){

            pnew = (TreeNode *)malloc(sizeof(TreeNode));

            pnew->data = *str;

            if( left_child ){

                pcur->lchild = pnew;

            }

            else{

                pcur->rchild = pnew;

                left_child = true;        // 下一个值要放到左孩子

            }

            push(s,pcur);            // 父节点进栈

            push(s,pnew);            // 新的结点作为下一次的父节点

        }

        else{

            if( left_child ){

                pcur->lchild = NULL;

                left_child = false;        // 无左孩子，下一个轮到右孩子

                push(s,pcur);            // 当前节点进栈，下一个轮到右孩子

            }

            else{

                pcur->rchild = NULL;    // 无右孩子

                while( ! empty_stack(s) ){

                    pnew = pop(s);        // 取出父节点

                    if( pcur != pnew->lchild ){    // 判断pcur是否为左孩子

                        pcur = pnew;            // 若不是，说明父节点已有2孩子

                    }                            // 继续查找，直到父节点只有左孩子

                    else{

                        push(s,pnew);            // 节点进栈，下一个轮到右孩子

                        break;

                    }

                }

                printf("  right end\n");

            }

        }

    }

    return t;

}

　　测试二叉树：

void PreOrderTraverse(TreeNode *t){

    //printf("in PreOrderTraverse\n");

    if( NULL == t ) return;

    printf("%c",t->data);

    PreOrderTraverse(t->lchild);

    PreOrderTraverse(t->rchild);

}

void InOrderTraverse(TreeNode *t){

    if( NULL == t ) return;

    InOrderTraverse(t->lchild);

    printf("%c",t->data);

    InOrderTraverse(t->rchild);

}

void PostOrderTraverse(TreeNode *t){

    if( NULL == t ) return;

    PostOrderTraverse(t->lchild);

    PostOrderTraverse(t->rchild);

    printf("%c",t->data);

}

int main(){

    TreeNode *t = NULL;

    char str[] = "ABDH#K###E##CFI###G#J##";

    t = creat_tree(str);

    PreOrderTraverse(t);

    printf("\n");

    InOrderTraverse(t);

    printf("\n");

    PostOrderTraverse(t);

    printf("\n");

    char str2[] = "AB##C##";

    t = creat_tree(str2);

    PreOrderTraverse(t);

    printf("\n");

    InOrderTraverse(t);

    printf("\n");

    PostOrderTraverse(t);

    printf("\n");

}

　　输出：

ABDHKECFIGJ
HKDBEAIFCGJ
KHDEBIFJGCA

ABC
BAC
BCA

巴特西

C格式字符串转为二叉树

最新文章

热门文章