我想说我每次学到树都学不下去...

感觉知道思路写代码就很方便了...

这篇是给我这种菜鸟记录用的,请大家不要浪费时间看..

1. 原来非递归先序遍历要这么想...

img

  • 1入栈。
  • 1出栈(栈顶元素出栈),输出栈顶元素1,并将1的左右孩子节点入栈;其中右孩子4先入栈,然后左孩子2入栈。(因为,对左边孩子的访问先序遍历先于右孩子,后入栈的先访问)。
  • 2出栈(栈顶元素出栈),输出栈顶元素2,并将2的左右孩子节点入栈,同理5先入栈,3后入栈。
  • 3出栈(栈顶元素出栈),输出栈顶元素3,3为叶子结点,无孩子,本次无入栈。
  • 5出栈(栈顶元素出栈),输出栈顶元素5
  • 4出栈(最后的栈顶元素出栈),此时 栈空,遍历完毕。

2. 终于弄懂了由先序和中序构造树

Pre+In2Post

函数声明:

int CreateBT(char * preorder, char * inorder, BTNode * &bt, int length)

易错点:

在递归的时候从哪里开始取preorder和inorder很容易有+1,-1的错误。
解决:写的时候举个栗子
这里的cnt是preorder[0]在inorder中的位置(从0算起)
左子树:CreateBT(preorder + 1,inorder,bt->lchild,cnt);
右子树:CreateBT(preorder + cnt + 1,inorder + cnt + 1,bt->rchild,length - cnt - 1);

代码在此

int CreateBT(char * preorder, char * inorder, BTNode * &bt, int length)
{
// 在此处补充你的代码
    bt = (BTNode *)malloc(sizeof(BTNode));
     if(length <= 0) {
         bt = NULL;
         return 0;
    }
    char check = preorder[0];
    bt->e = check;
    int cnt;
    for(int i = 0;i < strlen(inorder);i++){
        if(check == inorder[i]) {
            cnt = i;
            break;
        }
    }
    CreateBT(preorder + 1,inorder,bt->lchild,cnt);
    CreateBT(preorder + cnt + 1,inorder + cnt + 1,bt->rchild,length - cnt - 1);
    return 0;
}

Last modification:October 19th, 2020 at 01:20 pm
请赏我杯奶茶,让我快乐长肉