白话文之二叉树

如果有不懂二叉树或者看不明白的同学, 简易别可着一个人的文章/视频在那死扣, 这个人的文章/视频看不懂说明当前你的理解水平较作者的理解水平可能还不在一个水平面上,谷歌一下换一个人的文章/视频再看看, 多来几次没准你就懂了

有点不好意思, 数据结构这一块我也懵逼,二叉树这东西头一次的见的时候看着看着就想睡觉了, 但是你要是真的想用心学,自己找合适自己的方法, 加油你可以的

因为二叉树已经是一个立体结构,不再像链表,队列那样是前后一对一的关系了,

打个比喻吧过年回家你是先回你自己家还是先回你父母家还是先回你丈母娘家, 嗯想了半天这个比喻好~ 惊不惊喜意不意外表情->贱贱的

image.png

你父母也有你父母家父母的父母家父母的丈母娘家
你丈母娘也有你丈母娘家丈母娘的父母家丈母娘的丈母娘家
.......................不考虑年龄应该可以追踪到侏罗纪时代了

前序,中序,后续遍历(递归)

网上的文章多了去了,在这里说一下前,中,后三种遍历的套路吧
套用上图, 这就是个填空题了,

前序:
自己家
left (父母家)
right(丈母娘家)

中序:
left(父母家)
自己家
right(丈母娘家)

后序:
left(父母家)
right(丈母娘家)
自己家

是不是能看到一点阳光了? 前序中序后续其实就是自己家应该是先执行还是中间执行还是最后执行
那下面来对照下代码吧

typedef struct BiTNode {//二叉树结点
    char data;                      //数据
    struct BiTNode *lchild,*rchild; //左右孩子指针
} BiTNode,*BiTree;

void Visit(BiTree T) {//输出
    if (T->data != '#') {
        printf("%c ",T->data);
    }
}
void PreOrder(BiTree T) {//先序遍历
    if (T != NULL) {
        Visit(T);               //访问根节点(自己家)
        PreOrder(T->lchild);    //访问左子结点
        PreOrder(T->rchild);    //访问右子结点
    }
}
void InOrder(BiTree T) {//中序遍历
    if (T != NULL) {
        InOrder(T->lchild);     //访问左子结点
        Visit(T);               //访问根节点(自己家)
        InOrder(T->rchild);     //访问右子结点
    }
}
void PostOrder(BiTree T) {//后序遍历
    if (T != NULL) {
        PostOrder(T->lchild);   //访问左子结点
        PostOrder(T->rchild);   //访问右子结点
        Visit(T);               //访问根节点(自己家)
    }
}

反转二叉树

然后呢你过年还真这么干了, 恰巧你还是个妻管严,
凭啥一直都先去你父母家再去我娘家? 不行调过来!!
同时... 你妈, 你丈母娘, 你奶奶你姥姥 .......一并炸毛(相当于第四次世界大战)

反转二叉树就出来了.....

   BiTree  ReverseWithRecursive(BiTree T)
        {
            if (T == null)
            {
                return null;
            }

            if (!(T->Left == null && T->Right == null))
            {
                BiTree* temp = T->Right;//左右节点反转
                T->Right = T->Left;
               T-> Left = temp;

                if (T->Left != null)
                    T->Left = ReverseWithRecursive(T->Left);//递归反转左子节点
                if (Right != null)
                    T->Right = ReverseWithRecursive(T->Right);//递归反转右子节点
            }
            return T;
        }