[数据结构]二叉树遍历、求深度C语言的简单实现

朱雀 2022-06-04 01:06 101阅读 0赞

Github:([https://github.com/FlameCharmander/DataStructure][https_github.com_FlameCharmander_DataStructure])  
  当年在学数据结构的时候，要求自己把代码给实现一遍。在实现完线性表，栈和队列之后，到了树这章实现代码确实有点难以入手，原因大家都懂，有递归。  
  树的这章，比较重要的代码是递归遍历以及求深度，先弄明白这两段代码再去看关于树的相关代码就会容易很多。 这里提个小小意见，递归很抽象，最好能画个树的图，然后按照程序代码在树的图中给画出来，最好能Debug一遍。  
  所以我给出这相关代码。希望可以帮助大家。

#include <stdio.h>
    
    typedef struct BiTnode{
        char data;
        struct BiTnode *lchild, *rchild;
    }*BiTree, BiTNode;
    
    void PreOrder(BiTree T);	//前序遍历
    void InOrder(BiTree T);	//中序遍历
    void PostOrder(BiTree T);	//后序遍历
    void CreateBiTree(BiTree* T);	//创建树
    int Depth(BiTree T);
    
    int main() {
        BiTree T;
        CreateBiTree(&T);
        printf("PreOrder:");
        PreOrder(T);
        printf("\n");
        printf("InOrder:");
        InOrder(T);
        printf("\n");
        printf("PostOrder:");
        PostOrder(T);
        printf("\n");
        printf("Depth:%d", Depth(T));
        printf("\n");
        return 0;
    }
    
    void CreateBiTree(BiTree* T) {   //以先序遍历创建树
        char ch;
        if ((ch = getchar()) == '\n')
        {
            return;
        }
        if (ch == '#')
        {
            (*T) = NULL;
        }
        else
        {
            *T = (BiTNode *)malloc(sizeof(BiTNode));
            (*T)->data = ch;
            CreateBiTree(&((*T)->lchild)); //因为要传入一个(struct BiTnode *lchild)的指针，也就是指针的指针
            CreateBiTree(&((*T)->rchild));
        }
    }
    
    void PreOrder(BiTree T) {
        if (T != NULL) {
            printf("%c ", T->data);
            PreOrder(T->lchild);
            PreOrder(T->rchild);
        }
    }
    
    void InOrder(BiTree T) {
        if (T != NULL) {
            InOrder(T->lchild);
            printf("%c ", T->data);
            InOrder(T->rchild);
        }
    }
    
    void PostOrder(BiTree T) {
        if (T != NULL) {
            PostOrder(T->lchild);
            PostOrder(T->rchild);
            printf("%c ", T->data);
        }
    }
    
    int Depth(BiTree T) {
        if(T == NULL) {
            return 0;
        } else {
            int m = Depth(T->lchild);
            int n = Depth(T->rchild);
            if (m > n) {
                return (m+1);
            }
            else {
                return (n+1);
            }
        }
    }

这里我建议你打开两个窗口来讲下面的解释和代码一一对应来看。  
Line 1 导入头文件  
Line 3~6 二叉树的数据结构，一个数据域，两个孩子结点的指针域  
Line 8~12 二叉树的创建（根据先序遍历序列），先序遍历，中序遍历，后序遍历，求深度  
Line 14~29 在main函数对这些函数测试  
Line 31~48 根据先序遍历序列进行创建树，这个可以先不用看具体的实现。不过如果你像看的化，我还是简单说下他是怎么实现的。这个函数每次接收一个字符，然后按照先序遍历调用函数，根据字符（是数据还是空指针，空指针用’\#'表示），如果是空指针就将传进来的指针置为空，如果不是空指针，则创建一个新的结点。  
Line 50~56 以先序遍历的方式遍历树，先访问根结点`printf("%c ", T->data);`，再访问左子树`PreOrder(T->lchild);`，右子树`PreOrder(T->lchild);`，这里为什么是左子树右子树，我想这就是递归的魅力了。 接下来我根据下面这张图，对先序遍历的过程（只对A结点及左子树的，不然要写太多了，你先看，记得对照图看）做个说明。（图中的灰色结点‘\#’平常不会画出来，这里我为了方便，才画出来的）  
![AB\#\#CD\#\#F\#\#][AB_CD_F]  
  其实递归调用会形成一个递归图，而这个递归图就是一棵树。所以你会发现先序遍历是有且只会一次访问结点（跟图的不一样，图还要设一个访问数组，来判断当前结点是否被访问过）。  
![先序遍历][SouthEast]  
  上面这张图，我把流向都给画出来了，其中的数字代表第几次被访问。  
  首先我们会传入根结点的指针到先序遍历中（在main函数中调用的，Line 18那里），也是图中的A结点，所以你看到图中的1，那个代表是A结点是第一个访问。然后我们用`printf("%c ", T->data);`把A结点的值给打印出来（算是A结点的访问，你也可以用A结点做别的事，但是这里为了举例，用了打印来表示访问）。  
  访问完A结点后，`PreOrder(T->lchild);`我们会执行这个语句，A函数因为没执行完又去执行别的函数了，所以入函数栈里，等它执行完的这个函数执行完毕后，A函数才会继续执行剩下的`PreOrder(T->rchild);`。  
那我们可以看到A结点的左孩子是B，所以我们会访问B，所以B是第2次访问的结点（图中标2）。  
  继续，B结点访问完，又调用了`PreOrder(T->lchild);`，同样的，B函数因为没执行完又去执行别的函数了，所以入函数栈里，我们现在栈里有两个函数，一个是访问A结点时的那个函数，一个是B结点时的那个函数。  
继续，B结点的左孩子是空，我在图中标记为\#，T为空时，不满足`if (T != NULL)`所以，函数执行完毕，所以我们会出函数栈，把B给弹出来，然后把B继续执行刚才未执行的语句。注意：这里我在图中把B的左孩子那个也写了个数字3，说明我们是第三次访问这个结点的，不过我们不做任何访问的操作（把它打印出来）。  
  我们回到访问B结点的那个函数，我们已经执行完`PreOrder(T->lchild);`（就是上面那个步骤），程序会继续执行`PreOrder(T->rchild);`，这时B还没有执行完毕，B压入栈。这时栈有访问A和B两个结点的函数。  
同样的，跟B结点的左孩子一样，不满足`if (T != NULL)`所以，函数执行完毕，所以我们会出函数栈，把访问B的那个函数给弹出来，然后继续执行刚才未执行完的代码。这时函数栈就A了。  
  这时访问的B结点的函数没有其它语句了，B结点的函数执行完毕，出栈，这时出来的是访问A的结点的函数，A结点刚才执行完`PreOrder(T->lchild);`了，接下来会继续访问`PreOrder(T->rchild);`，这是访问A结点的函数入栈，访问A的右结点C孩子…  
  不知道你看明白没，我希望你自己能把代码结合图走一遍，你就能理解这个递归遍历了。  
Line 58~64 以中序遍历的方式遍历树，你会发现将上面先序遍历访问结点的那句代码跟递归调用左孩子结点的那句代码交换下顺序就是中序遍历代码了  
Line 66~72 以后序遍历的方式遍历树，同理，将上面先序遍历访问结点的那句代码放在递归调用右孩子结点的那句代码的后面即可  
Line 74~88 求树的深度  
![求深度][SouthEast 1]  
求树的深度，我建议你先看完递归遍历，好好吸收一下递归的操作，然后根据代码在图里执行一遍。  
求深度的思想主要在于返回。  
Line 75~76 在遇到空指针时，会直接返回0。看下图的绿色部分。  
Line 78~79 在遇到非空指针时，会得到两个子树的深度，比如现在B结点的那个位置，他会得到左子树的深度0（LIne 75~76遇到的空指针返回0），右子树的深度0。  
Line 80~85 判断两者的哪个最大（因为Depth=max\{Depth(T->leftChild), Depth(T->rightChild)+1\},左右子树的最大深度加上当前结点的深度（1））  
以A结点来讲，你看图，A的左子树深度为1，右子树为2，那我们整棵树是3=右子树深度+1，返回给了main函数。  
![运行结果图][SouthEast 2]

[https_github.com_FlameCharmander_DataStructure]: https://github.com/FlameCharmander/DataStructure
[AB_CD_F]: /images/20220604/ef60f7c5bf5d423d8c73cdb3ddb92005.png
[SouthEast]: /images/20220604/4bc3d78caaa9457e98d24ef5e69d7881.png
[SouthEast 1]: /images/20220604/412b3f3bc494425a89924bcbb912d80a.png
[SouthEast 2]: /images/20220604/d077a65da10d4835b14264cf83ffcc96.png