我家自动化

这个屌丝很懒，什么也没留下！

热门标签

数据结构之树（一）_转向右子树和画右子树干

作者：我家自动化 | 2024-05-07 21:14:30

踩

转向右子树和画右子树干

树以及二叉树的性质

树的特性：

树是保证节点连通的最小连接方式，即边最少。

结点数=结点总度数+1，N个结点有N-1条边

度为M的树：代表其中一个结点的度最大值是M 例:m叉树代表结点的度最大为m

二叉树

设非空二叉树中度为0，1，2的结点个数分别为x，y，z，则x=z+1，即叶子结点比二分支结点（同时有左孩子和右孩子）多一个
对于一个二叉树，已知节点数为n,则树的深度为： $\log_2N$ +1 。
一棵N个结点的树有N-1条边，一个二叉树第i层的最大节点数是 $2^{i-1}$ 个， $i\geq1$ 。推广到M叉树第i层至多有 $M^{i-1}$ 个结点
深度为K的二叉树，最大总节点数为： $2^{K}-1$ 个， $K\ge1$ ，也即是满二叉树。推广到M叉树，则M叉树的最大总节点数为： $\frac{M^{K+1}-1}{M-1}$ 。
具有N个结点的M叉树的最小高度为： $log_M (N*(M-1)+1)$

完全二叉树

具有N个结点的完全二叉树的高度H为 $H=1+{log_2N}$
第i个结点所在层次为 $log_2{N+1}$
对于完全二叉树，可以由的结点数n推出度为0、1和2的结点个数为x、y、z。其中完全二叉树最多只有一个度为1的结点，y为0或1，x=z+1一定是奇数
若完全二叉树有2k个结点，则必有x=1，y=k，z=k-1
第i个结点的左孩子为2i，右孩子为2i+1，父结点为i/2
判断第i个结点是否有叶子/分支结点： $i>\frac{n}{2}$

对于一个任意一个非空二叉树都有：

$N_0$ 为叶结点(度为0，无子树)的个数， $N_2$ 为度为2的非叶节点个数

则有结论： $N_0=N_2+1$

证明方式：

首先因为树中边的个数为节点个数减一，所以对于任意二叉树有：

总边数= $N_0+N_1+N_2-1$ (其中下标表示度为i的结点，二叉树结点至多两个度)

又因为一个结点的度说明了其贡献的边数，例如 $N_2$ 能贡献两条边。所以通过边数相等得到等式

$N_0+N_1+N_2-1=0*N_0+1*N_1+2*N_2$

即 $N_0=N_2+1$

由此可以推广到M叉树： $N_0-1= \sum_{i=1}^M (i-1)*N_i$

二叉树的链式存储：

(注：有顺序存储但是会造成空间浪费，所以不用)

结构定义：


//链式存储树
typedef struct TreeNode* BinTree;//
struct TreeNode
{
    Elementtype Data;//数据域
    BinTree Left;//指向左数的结点
    BinTree Right;//指向右数的结点
};

遍历方式：

递归形式：

先序遍历：根 - 左子树 - 右子树

自己对于先序遍历的简单理解：

在根结点打印完后先往左边走，一直走到头，走一步打印一下
走到底后再往回走，原路返回的路上又右节点就往右走，
走到右边看看看看有没有左结点，有的话继续往左重复上面步骤，没有的话打印然后原路返回


void PreOrderTraversal(BinTree BT) {
    //:先序遍历：根 - 左子树 - 右子树
    if (BT) {//首先先判断结点为空
        printf("%d", BT->Data);//先打印结点数据
        PreOrderTraversal(BT->Left);
        PreOrderTraversal(BT->Right);
    }
}

中序遍历：左子树 - 根 - 右子树

自己对于中序遍历的简单理解：

从根节点开始，先走左边走到底，打印出最左边的结点，然后往回走
回去的途中每次往回一个结点先打印结点数据，然后看看这个结点有没有右结点，
没有的话就打印继续往回走，走一步打印一个
有的话就往右走，然后把这个结点当作根节点重复上述步骤


void InOrderTraversal(BinTree BT){
    //:中序遍历：左子树 - 根 - 右子树
    if (BT) {//首先先判断结点为空
        InOrderTraversal(BT->Left);
        printf("%d", BT->Data);
        InOrderTraversal(BT->Right);
    }
}

后序遍历：左子树 - 右子树 - 根

自己对于后序遍历的简单理解：

从根节点开始，先走左边走到底，打印出最左边的结点，然后往回走
回去的途中每次往回一个结点先看看这个结点有没有右结点，
没有的话就打印继续往回走
有的话就往右走，然后把这个结点当作根节点重复上述步骤
右边走完回来继续往回走。


void PostOrderTraversal(BinTree BT) {
    //:后序遍历：左子树 - 右子树 - 根
    if (BT) {//首先先判断结点为空
        PostOrderTraversal(BT->Left);
        PostOrderTraversal(BT->Right);
        printf("%d", BT->Data);
    }
}

非递归形式：

思路上就是根据遍历顺序利用堆栈存储结点

前置准备：

堆栈功能的创建：

堆栈结构——入栈函数——出栈函数


typedef struct SNode* Stack;
struct SNode {
    BinTree Data;//存的是树节点的信息
    Stack Next;
};
//创建堆栈
Stack CreatStack() {
    Stack S = (Stack)malloc(sizeof(struct SNode));
    S->Next = NULL; S->Data = NULL;
    return S;
}
//入栈操作
bool Push(Stack S,BinTree X) {
    Stack S1 = CreatStack();
    S1->Data = X; S1->Next = S->Next;
    S->Next = S1;//做一个头插法
    return 1;
}

二叉树的创建：

先序遍历创建树：

思路是创建一个树，利用先序遍历的方式先建立结点然后输入数据，按照先序方式进行递归
每次进入函数表示是一个叶节点，输入0表示无子树。说明到底了创建好这一部分了。
可以理解为，先把二叉树的左侧部分的结点的左子树从上到下，全部创建完之后(叶结点输入0时表示无子树)，
再从下到上创建左侧部分结点的右子树，然后创建右侧部分结点的左子树，最后创建右侧部分结点的右子树。

注意：是以拓展二叉树的方式输入先序遍历的结果

代码实现：


BinTree CreatTree( ) {
    char data;
    BinTree BT=NULL;
    scanf("%c", &data);
    if (data == '0') {
        return 0;
    }
    BT = CreatBinTree();
    BT->Data = data;
    BT->Left = CreatTree();
    BT->Right = CreatTree();
    return BT;
}

层序创建树：

1.输入第一个数据：

若为0则表示是空树，将空指针赋给根节点，然后退出。
若不为0，则分配空间存入数据，然后把这个结点入队

2.队列不空，则出队建立左右子树

输入数据：若为0则左树指空，不为0则创建结点存储然后入队
再次输入数据：若为0则右树指空，不为0则创建结点存储然后入队

3.重复(2)过程，直到队列空位置结束


BinTree LevealCreat() {
    char data;
    BinTree BT, TT;
    scanf("%c", &data);
    Queue Q = CreatQueue();
    if (data == '0') {
        BT = NULL;
        printf("空树");
        return NULL;
    }
    else {
        BT = CreatBinTree();
        BT->Data = data;
        JoinQueue(&Q, BT);
    }
    while (Q.Front->Next)
    {
        TT = OutQueue(&Q);
        scanf("%c", &data);
        if (data == '0') {
            TT->Left = NULL;
        }
        else {
            TT->Left = CreatBinTree();
            TT->Left->Data = data;
            JoinQueue(&Q, TT->Left);
        }
        scanf("%c", &data);
        if (data == '0') {
            TT->Right = NULL;
        }
        else {
            TT->Right = CreatBinTree();
            TT->Right->Data = data;
            JoinQueue(&Q, TT->Right);
        }
    }
    return BT;
}

先序遍历：

改变下prinf的语句位置，先打印在出入栈


void Preorder(BinTree BT) {
    Stack S = CreatStack();
    BinTree TT = BT;//因为树结点的值是一个地址，直接用BT就影响全局变量中的地址值，所以用TT作为临时量操作
        while (TT || S->Next)
        {
            while (TT)//一直左走到底，途中一直入栈
            {
                printf("%c", TT->Data);//先打印在入栈
                Push(S, TT);
                TT = TT->Left;
            }
            if (S->Next != NULL) {
                TT = Pop(S);
                TT = TT->Right;//转向右树，没有的话自动指空
            }
    }
}

中序遍历：

思路是：遇到一个结点入栈，然后与遍历他的左子树
当左子树遍历完后，从栈顶弹出一个结点
访问这个结点的右子树，对这个右子树的结点按照中序遍历的方法再次执行


void inorder(BinTree BT) {
    Stack S = CreatStack();
    BinTree TT = BT;//因为树结点的值是一个地址，直接用BT就影响全局变量中的地址值，所以用TT作为临时量操作
    while (TT||S->Next)
    {
        while (TT)//一直左走到底，途中一直入栈
        {
            Push(S, TT);
            TT = TT->Left;
        }
        if (S->Next!=NULL) {
            TT = Pop(S);
            printf("%c", TT->Data);//弹出左树打印数据
            TT = TT->Right;//转向右树，没有的话自动指空
        }
    }
}

后序遍历：

思路：首先这么理解，对于先序遍历的顺序是根节点-左子树-右子树，而后序遍历的顺序是左子树-右子树-根节点。这两种遍历方式的区别就是，先做遍历交换左右子树遍历的先后顺序，然后取逆序就是后序遍历了。那么怎么改造先序遍历，成为后序遍历呢？

对于交换先序遍历的顺序，从根节点-左子树-右子树到根节点-右子树-左子树的转变，只要把先序遍历里面的TT-Left和TT-Right交换一下就行。本质上就是从右边开始的先序遍历。（从根结点出发一直往右走走到底，返回看到有左节点就进去，然后把左节点当作根节点继续重复上面操作）

利用两个堆栈，分别记作Stack1和Stack2，首先我们注意到先序遍历改造后要逆序输出，所以我们可以利用Stack2来实现逆序输出。因为先序遍历改造后正序输出是根节点-右子树-左子树，这个顺序放入Stack2就变成了左子树-右子树-根节点，然后从Stack2里面输出就实现了顺序的转换，因此我们只要把原先先序遍历的printf语句改成入栈Stack2，最后用Stack2输出即可。


void postorder(BinTree BT) {
    Stack S1 = CreatStack();
    Stack S2 = CreatStack();
    BinTree TT = BT;//因为树结点的值是一个地址，直接用BT就影响全局变量中的地址值，所以用TT作为临时量操作
        while (TT || S1->Next)
        {
            while (TT)//一直右走到底，途中一直入栈
            {
                Push(S2,TT);//代替原先的printf，为了后面的逆序输出，压入右树的树结点
                Push(S1, TT);//压入右树的树结点
                TT = TT->Right;
            }
            if (S1->Next != NULL) {
                TT = Pop(S1);
                TT = TT->Left;//转向左树，没有的话自动指空
            }
    }
        while (S2->Next)
        {
            TT = Pop(S2);
            printf("%c", TT->Data);
        }
}

层序遍历：

利用队列或者堆栈实现

前置准备：队列的一些准备

队列结构：

注意！这里Queue是一个普通变量，不是指针变量，因此在传值得时候，要对队列内部进行修改要是要指针传入！


typedef struct LNode* List;
struct LNode {
    BinTree Data;
    List Next;
};
typedef struct QNode Queue;
struct QNode {
    List Front,Rear;//指向头尾的指针
};

队列的操作函数：


 
Queue CreatQueue() {
    //注意队列结点生成的时候要分配地址，但是虽然这个结点有地址了，但是结点里面的指针的还是野指针
    //所以队列结点里面的指针也要初始化
    Queue Q;
    List tempt = (List)malloc(sizeof(struct LNode));
    Q.Front = tempt;//因为这两个是指针都是空指针要赋值指针类型，进行初始化
    Q.Rear = tempt;//让指针有效存在
    Q.Front->Data = NULL; Q.Front->Next = NULL;//初始化
    Q.Rear->Data = NULL;Q.Rear->Next=NULL;
    return Q;
}
//队列采取尾入头出
bool JoinQueue(Queue *Q,BinTree BT) {//入队是尾插
    List temp = (List)malloc(sizeof(struct LNode));
    temp->Data = BT; temp->Next = NULL;
    Q->Rear->Next = temp;
    Q->Rear = temp;//注意入对的元素的队尾
    return 1;
}
 
BinTree OutQueue(Queue *Q) {/*出队是从头出去的
     思路类似头插法，理解成排队的第一个人或者数组的标; Front不空说明一个位置有人，空就代表没人;
     Rear表示队尾的位置，没人要指空*/
    List temp;//小细节：temp是链表结点不是队列结点，链结点直接指向了这个队列结点，
        //这样用链表结点的好处就是方便直接获取结点里面的值
    BinTree cnt;
    //先判断是否为空
    if (Q->Front->Next == NULL) {
        printf("队列空");
        return NULL;
    }
    else {
        temp = Q->Front->Next;
        //考虑队列是否只有一个元素的情况,因为出去后Rear就空了
        if (temp == Q->Rear) {
            Q->Rear = Q->Front;
        }
            Q->Front->Next = temp->Next;
            cnt = temp->Data;
            free(temp);
            return cnt;    }
}

层序遍历的实现：

思路：就是利用队列访问结点，访问完输出，然后判断有无左右子树，有的话入队，按从左往右顺序执行，知道队列空位置。

注意下：因为JoinQueue中需要移动尾指针，Q.Rear = temp这行代码不会影响到主函数中的Q。而OutQueue中通常不需要移动头指针，只需要更改头指针的next域，Q.Front->Next = temp->Next这行代码会影响主函数中的Q。

函数中对队列的修改是地址上的修改，所以要用指针传入实参！

对于数据结构要考虑实参和形参的问题：

当你传递一个参数给函数的时候，这个参数会不会在函数内被改动决定了参数的传入形式！
需要被改动，则需要传入指向这个参数的指针
不用被改动，则直接传递这个参数


//利用队列作层次遍历
void LevelOrderTraversal(BinTree BT) {
    //:层次遍历：从上到下，从左到右
    Queue Q = CreatQueue();
    BinTree TT ;
    JoinQueue(&Q, BT);
        while (Q.Front->Next) {
            TT=OutQueue(&Q);
            printf("%c", TT->Data);
            if (TT->Left) {
                JoinQueue(&Q, TT->Left);
                Q.Rear = Q.Rear->Next;
            }
            if (TT->Right) {
                JoinQueue(&Q, TT->Right);
                Q.Rear = Q.Rear->Next;
            }
        }
}
 
int main() {
    BinTree BT = CreatTree();
    printf("\n\n\n");
    LevelOrderTraversal(BT);
    return 0;
}

二叉树遍历的应用：

输出二叉树中的叶节点：

就是在遍历的过程中增加判断有无左右结点


void PreprintLeaves(BinTree BT) {
    if (BT) {
        if (!BT->Left && !BT->Right)
            printf("%c", BT->Data);
        PreprintLeaves(BT->Left);
        PreprintLeaves(BT->Right);
    }
}

求二叉树的高度：

运用递归思想：其实就是后续遍历的改版

就是从根节点开始比较左右子树的高度然后加上根节点本身就是树得深度了，然是右怎么知道左右子树的高度呢？那就是把左子树和右子树当成根节点，然后再比较高度+1就行，按照这样的思想，我们走到叶节点的时候，把叶节点当成根节点去看左右子树，那此时左右子树都没了，那此时高度是0然后我就比较完了回来+1，所以对于叶节点前面一个结点1来说，他的左子树高度是1，然后结点1就再进右子树，按照同样的方法执行比较然后返回。
这实际上就是后序遍历的思想：左子树-右子树-根节点，然后比较高度返回一个高的作为根节点高度。

简单点概括：最内层递归递归到叶子结点的时候会继续递归叶子结点左右子树，左右为空所以return 0，就有了初值0，然后再比较左右的深度的大小，两边都是0，就会return 0+1，即高度+1。


int hight(BinTree BT) {
    int tallL,tallR;
    int max;
    if (!BT) {//树空就没高度了
        return 0;//递归的出口
    }
    else {
        tallL = hight(BT->Left);
        tallR = hight(BT->Right);
        max = (tallL > tallR) ? tallL : tallR;
        return max+1;//三目运算符，相等返回哪个都一样
    }
}

对于中缀表达式会受到影响：只要在输出左子树时先输出左括号，然后左子树结束时再加上右括号即可。

注意图中中缀表达式时不准的，是d+e*f

对于两种遍历序列确定一个二叉树：

只要两种遍历序列中存在一种中序遍历，就可以确定一颗二叉树！

因为只知道前序和后续无法去顶左右子树的位置，例如先序:AB和后序BA，无法判断B是左子树还是右子树

如何通过先序和中序确定一颗二叉树：

自己的理解：

首先因为先序遍历是根-左-右，中序遍历是左-根-右，所以先序的第一个节点一定是根据，那确定根节点后对应到中序里边，找到这个结点，那么他的左边就是左子树右的结点，右边就是右子树有的结点。然后可以对应个数判断。通过中序知道了左子树和右子树，那么数出左子树的个数对应到先序里面，那么先序中根节点后面的这么多个全是左子树，其余的都是右子树。然后再把先序中左子树第一个当作根节点对应到中序中的左子树比较，就可以确定一棵树了。

代码：递归思想

总体思路就是：找到根节点——创建结点——分割字符串左右树

注意分割左右树的时候，我们是根据先序遍历的序列，按照他的顺序去建立根节点，每次递归调用建立一个结点，指向先序序列的下表往前移动一位，然后划分左右子树进入递归再次创建结点。

字符串分解分为几个步骤：
(1)前序遍历串的第一个字符ch为根节点
(2)到中序串中找到ch对应的位置rootPos
(3)利用rootPos的值，可以把前序遍历序列的左子树的串，右子树的串分离开；也把中序遍历序列的左子树的串，右子树的串分离开；
然后利用分离出来的串，作为参数传入到递归函数中就行了。

利用static是精髓！


BinTree confirm(char* pre, char* inorder, int start, int end) {
    if (start > end)return NULL;
    static int point = 0;
    //静态本地变量指向先序序列的下标，从左到右按照先序的方式打印结点
    BinTree TT = CreatBinTree();
    int k = 0;
    TT->Data = pre[point];
    for (k = start; k <= end; k++) {
        if (inorder[k] == TT->Data)break;
    }
    point++;
    TT->Left = confirm(pre, inorder, start, k - 1);
    TT->Right = confirm(pre, inorder, k + 1, end);
    return TT;
}
int main() {
    char pre[100]; char inorder[100];
    scanf("%s", pre);
    scanf("%s", inorder);
    BinTree TT;
    int n=strlen(pre);
    TT=confirm(pre, inorder, 0, n - 1);
    LevelOrderTraversal(TT);
    return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/551267