【数据结构】二叉树的链式实现及遍历

拼搏现实的明天。 2024-03-02 02:35 48阅读 0赞

#### 文章目录 ####

*  一、二叉树的遍历
 *   *  1、前序遍历
     *  2、中序遍历
     *  3、后序遍历
     *  4、层序遍历
 *  二、二叉树结点个数及高度
 *   *  1、二叉树节点个数
     *  2、二叉树叶子节点个数
     *  3、二叉树第k层节点个数
     *  4、二叉树查找值为x的节点
 *  三、二叉树创建及销毁
 *   *  1、通过前序遍历数组创建二叉树
     *  2、二叉树的销毁
     *  3、判断是否为完全二叉树
 *  四、测试代码

![在这里插入图片描述][598668fc2bfb4483a83b7ad293f6d6a9.png]

## 一、二叉树的遍历 ##

后文所有代码中的二叉树结点：

typedef char BTDataType;
    //二叉树结点结构体
    typedef struct BinaryTreeNode
    {
        
    	BTDataType data;
    	struct BinaryTreeNode* left;
    	struct BinaryTreeNode* right;
    }BTNode;

### 1、前序遍历 ###

前，中，后序遍历都可以采用分治递归的思想解决，将根节点和它的孩子结点分别处理。

// 二叉树前序遍历 
    void BinaryTreePrevOrder(BTNode* root)
    {
        
        if (root == NULL)
        {
        
            printf("NULL ");
            return;
        }
    
        printf("%c ", root->data);
        BinaryTreePrevOrder(root->left);
        BinaryTreePrevOrder(root->right);
    }

此处仅利用递归展开图分析前序遍历，中序和后序也是相同的思想：

![在这里插入图片描述][c25c902084d84e129e13b2abb5dcdb9c.png]

![在这里插入图片描述][7b9fa3ab9a99449a83e1e6344b5fc977.png]

### 2、中序遍历 ###

// 二叉树中序遍历
    void BinaryTreeInOrder(BTNode* root)
    {
        
        if (root == NULL)
        {
        
            printf("NULL ");
            return;
        }
    
        BinaryTreeInOrder(root->left);
        printf("%c ", root->data);
        BinaryTreeInOrder(root->right);
    }

### 3、后序遍历 ###

// 二叉树后序遍历
    void BinaryTreePostOrder(BTNode* root)
    {
        
        if (root == NULL)
        {
        
            printf("NULL ");
            return;
        }
    
        BinaryTreePostOrder(root->left);
        BinaryTreePostOrder(root->right);
        printf("%c ", root->data);
    }

### 4、层序遍历 ###

层序遍历需要利用队列来进行，如果二叉树跟结点不为空，则让指向它的一个指针入队，然后将队头结点记录下来，先将它的值打印，然后判断它的左右孩子为非空则入队，然后删掉队头换下一个继续记录打印…直到队列为空则遍历完成。

例如对如图这个二叉树：

层序遍历结果为：12345  
![在这里插入图片描述][20c623fb072546f28f4075f48e4a3d71.png]  
先将根节点1入队，打印1

![在这里插入图片描述][48d12fdea8c74b958999f6444e189e79.png]

然后将1的左右孩子2和3入队  
![在这里插入图片描述][17cf0fb3190c484483b38d953dbdad06.png]

删掉队头1，front换为2，打印2  
![在这里插入图片描述][62a1adb654f04520bd26bfcfffd4fdee.png]

然后将2的左孩子4入队  
![在这里插入图片描述][82a7cb9ac74e4e26998d32c337279f79.png]

删掉队头2，front换为3，打印3  
![在这里插入图片描述][bd831e7a7e334a8ba3a877c8db693df6.png]

然后将3的右孩子5入队  
![在这里插入图片描述][db10f385037241abb0004335e39e7359.png]

… …

接着按这样打印4，5便完成了二叉树的层序遍历

![在这里插入图片描述][64a5b8a7c9ba4970836cf12e27f8f5c0.png]

程序代码利用了自己创建的队列,代码如下:

//层序遍历
    void LevelOrder(BTNode* root)
    {
        
        //创建队列
        Que q;
        QueueInit(&q);
    
        //如果根节点不为空，则放进队列
        if (root)
            QueuePush(&q, root);
    
        while (!QueueEmpty(&q))
        {
        
            //将队头打印
            BTNode* front = QueueFront(&q);
            printf("%c ", front->data);
            //判断front左右节点不为空则入队
            if (front->left)
                QueuePush(&q, front->left);
    
            if (front->right)
                QueuePush(&q, front->right);
            
            QueuePop(&q);
        }
        printf("\n");
    
        QueueDestroy(&q);
    }

## 二、二叉树结点个数及高度 ##

### 1、二叉树节点个数 ###

采用分治法递归实现，当根节点为空时返回值为0，不为空则返回左右子树上的节点数加上自身1。

int BinaryTreeSize(BTNode* root)
    {
        
        return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
    }

### 2、二叉树叶子节点个数 ###

采用分治法递归实现，根节点为空时返回0，当根节点没有孩子结点时说明它是叶子节点，返回1，其他情况时只需左右子树上的叶子节点相加即可。

int BinaryTreeLeafSize(BTNode* root)
    {
        
        if (root == NULL)
        {
        
            return 0;
        }
        if (root->left == NULL && root->right == NULL)
        {
        
            return 1;
        }
        return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
    }

### 3、二叉树第k层节点个数 ###

需要保证k大于0才可，当根节点为空，则返回0，当k等于1时只有一层一个节点，返回1，k>1时第k层节点数就相当于它左右孩子的第k-1层节点数相加。

int BinaryTreeLevelKSize(BTNode* root, int k)
    {
        
        assert(k > 0);
    
        if (root == NULL)
        {
        
            return 0;
        }
        if (k == 1)
        {
        
            return 1;
        }
        return BinaryTreeLevelKSize(root->left, k - 1)
            + BinaryTreeLevelKSize(root->right, k - 1);
    }

### 4、二叉树查找值为x的节点 ###

跟节点为空则找不到返回NULL，当根节点的值为要找的值时返回该节点，不相等则分别判断它的左右孩子节点，直到找到为止。

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
    {
        
        if (root == NULL)
        {
        
            return NULL;
        }
        if (root->data == x)
        {
        
            return root;
        }
        BTNode* ret = BinaryTreeFind(root->left,x);
        if (ret)
        {
        
            return ret;
        }
        return BinaryTreeFind(root->right, x);
    }

## 三、二叉树创建及销毁 ##

### 1、通过前序遍历数组创建二叉树 ###

读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC\#\#DE\#G\#\#F\#\#\# 其中“\#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

#include <stdio.h>
    #include<stdlib.h>
    typedef char BTDataType;
    
    typedef struct BinaryTreeNode {
        
        BTDataType data;
        struct BinaryTreeNode* left;
        struct BinaryTreeNode* right;
    } BTNode;
    BTNode* BinaryTreeCreate(BTDataType* a, int* pi) {
        
        if (a[*pi] == '#') {
        
            ++*pi;
            return NULL;
        }
    
        BTNode* root = (BTNode*)malloc(sizeof(BTDataType));
        root->data = a[*pi];
        ++*pi;
    
        root->left = BinaryTreeCreate(a, pi);
        root->right = BinaryTreeCreate(a, pi);
    
        return root;
    }
    //中序遍历
    void InOrder(BTNode* root)
    {
        
        if(root==NULL)
        {
        
            return;
        }
        InOrder(root->left);
        printf("%c ",root->data);
        InOrder(root->right);
    }
    int main() {
        
        char a[100];
        scanf("%s",a);
        int pi=0;
        BTNode* root=BinaryTreeCreate(a, &pi);
        InOrder(root);
        return 0;
    }

### 2、二叉树的销毁 ###

void BinaryTreeDestory(BTNode* root)
    {
        
        if (root == NULL)
        {
        
            return;
        }
    
        BinaryTreeDestory(root->left);
        BinaryTreeDestory(root->right);
        free(root);
    }

### 3、判断是否为完全二叉树 ###

在二叉树层序遍历的基础上修改一下，让空节点也进入队列，遍历时遇到空节点则退出，继续遍历如果结束前还有非空节点则不是完全二叉树。

int BinaryTreeComplete(BTNode* root)
    {
        
        //创建队列
        Que q;
        QueueInit(&q);
    
        //如果根节点不为空，则放进队列
        if (root)
            QueuePush(&q, root);
    
        while (!QueueEmpty(&q))
        {
        
            BTNode* front = QueueFront(&q);
            if (front == NULL)
            {
        
                break;
            }
            QueuePush(&q, front->left);
            QueuePush(&q, front->right);
            QueuePop(&q);
        }
        //此时已经遇到空节点，如果再遇到非空节点则不是完全二叉树
        while (!QueueEmpty(&q))
        {
        
            BTNode* front = QueueFront(&q);
            if (front)
            {
        
                QueueDestroy(&q);
                return false;
            }
            QueuePop(&q);
        }
    
        QueueDestroy(&q);
        return true;
    }

## 四、测试代码 ##

手动构建一个如下图的二叉树，对代码进行测试：  
![在这里插入图片描述][9268bd6a1d3340c8bf34c783463a7088.png]  
测试结果应该为：

前序：123874569  
中序：832715469  
后序：837259641

是否为完全二叉树：0  
节点数：9  
叶子节点数：4

BTNode* BuyNode(BTDataType x)
    {
        
        BTNode* node = (BTNode*)malloc(sizeof(BTNode));
        if (node == NULL)
        {
        
            perror("malloc fail");
            exit(-1);
        }
    
        node->data = x;
        node->left = NULL;
        node->right = NULL;
    
        return node;
    }
    
    
    int main()
    {
        
        	// 手动构建
    	BTNode* node1 = BuyNode('1');
    	BTNode* node2 = BuyNode('2');
    	BTNode* node3 = BuyNode('3');
    	BTNode* node4 = BuyNode('4');
    	BTNode* node5 = BuyNode('5');
    	BTNode* node6 = BuyNode('6');
    	BTNode* node7 = BuyNode('7');
    	BTNode* node8 = BuyNode('8');
    	BTNode* node9 = BuyNode('9');
    
    	node1->left = node2;
    	node1->right = node4;
    	node2->left = node3;
    	node4->left = node5;
    	node4->right = node6;
    
    	node2->right = node7;
    	node3->left = node8;
    	node6->right = node9;
    
        printf("前序遍历：");
        BinaryTreePrevOrder(node1);
    	printf("\n");
    
        printf("中序遍历：");
        BinaryTreeInOrder(node1);
    	printf("\n");
    
        printf("后序遍历：");
        BinaryTreePostOrder(node1);
    	printf("\n");
    
        printf("层序遍历：");
        LevelOrder(node1);
        printf("\n");
    
        printf("BinaryTreeComplete：%d\n", BinaryTreeComplete(node1));
        printf("BinaryTreeSize：%d\n", BinaryTreeSize(node1));
        printf("BinaryTreeLeafSize：%d\n", BinaryTreeLeafSize(node1));
    
        BinaryTreeDestory(node1);
    	node1 = NULL;
    
        return 0;
    }

运行结果：

![在这里插入图片描述][881866884816493386c15ed2826d8d73.png]  
运行结果与预测结果一致。

[598668fc2bfb4483a83b7ad293f6d6a9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/c8b96b6b722b40fab03a1253c18dd433.png
[c25c902084d84e129e13b2abb5dcdb9c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/e1137e59b07b45cfb8b132660148041a.png
[7b9fa3ab9a99449a83e1e6344b5fc977.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/886e95cab2d645fbb5590ce6c975ef35.png
[20c623fb072546f28f4075f48e4a3d71.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/4da8b3a5faa94f9b8c6b79298ba2f19a.png
[48d12fdea8c74b958999f6444e189e79.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/9949b4923bea44cf8e102e345a66493b.png
[17cf0fb3190c484483b38d953dbdad06.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/6895e40f5c2c49f098f53fd34cf05216.png
[62a1adb654f04520bd26bfcfffd4fdee.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/258e47de160f460197bf788cdd2e6d1e.png
[82a7cb9ac74e4e26998d32c337279f79.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/f8018c27cc644e2384bdce6070118cc4.png
[bd831e7a7e334a8ba3a877c8db693df6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/17048bcb5dff475685acc4b2f1b8ff51.png
[db10f385037241abb0004335e39e7359.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/d8473b073caa4113837b1cb8c59d8c79.png
[64a5b8a7c9ba4970836cf12e27f8f5c0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/2c7ad483cd83484a8ac5f01b9bea85dc.png
[9268bd6a1d3340c8bf34c783463a7088.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/47b17a58143849679eca566c3d267caf.png
[881866884816493386c15ed2826d8d73.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/02/72af3f3ec63645ddae6660171f39f27d.png