C语言数据结构二叉树递归的方法

本篇内容介绍了“C语言数据结构二叉树递归的方法”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

一、二叉树的遍历算法

二叉树的精髓在于遍历。遍历掌握了后，剩下的问题迎刃而解。

1.构造二叉树

“工欲善其事必利其器”

所以先创建一个结构体。

手动先构造一颗如图所示的二叉树。

typedef int BTDataType;//定义二叉树结构体typedef struct BinaryTreenode{<!--{C}%3C!%2D%2D%20%2D%2D%3E-->int data;//节点数据struct BinartTreeNode* left;//左子树struct BinartTreeNode* right;//右子树}BTNode;//构造一棵二叉树BTNode* BuyBTNode(BTDataType x){<!--{C}%3C!%2D%2D%20%2D%2D%3E-->BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){<!--{C}%3C!%2D%2D%20%2D%2D%3E-->printf("malloc fail\n");exit(-1);}node->data = x;node->left = NULL;node->right = NULL;return node;}BTNode* CreatBinaryTree(){<!--{C}%3C!%2D%2D%20%2D%2D%3E-->BTNode* node1 = BuyBTNode(1);BTNode* node2 = BuyBTNode(2);BTNode* node3 = BuyBTNode(3);BTNode* node4 = BuyBTNode(4);BTNode* node5 = BuyBTNode(5);BTNode* node6 = BuyBTNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;}int main(){<!--{C}%3C!%2D%2D%20%2D%2D%3E-->BTNode* tree = CreatBinaryTree();return 0;}typedef int BTDataType;//定义二叉树结构体typedef struct BinaryTreeNode{int data;//节点数据struct BinartTreeNode* left;//左子树struct BinartTreeNode* right;//右子树}BTNode;//构造一棵二叉树BTNode* BuyBTNode(BTDataType x){BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){printf("malloc fail\n");exit(-1);}node->data = x;node->left = NULL;node->right = NULL;return node;}BTNode* CreatBinaryTree(){BTNode* node1 = BuyBTNode(1);BTNode* node2 = BuyBTNode(2);BTNode* node3 = BuyBTNode(3);BTNode* node4 = BuyBTNode(4);BTNode* node5 = BuyBTNode(5);BTNode* node6 = BuyBTNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;}int main(){BTNode* tree = CreatBinaryTree();return 0;}

2.前序遍历(递归图是重点.)

遍历顺序：根 左子树 右子树

思路：

把每个节点都想成是一棵树。

当树为空时。

当树不为空时，先遍历左子树，后遍历右子树

注意：前中后序遍历不同处只在printf打印的顺序的位置。

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

打印结果：

1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL

递归分析图：

递归题目的万能的解法。就是画递归图。

二叉树的所有题目，假如你不会，赶快 画递归图 吧

由于递归太庞大，图片太小看不清，所以我把左子树和右子树分开又截了图

红线部分代表压栈递归。

绿线部分代表 返回

左子树

右子树

3.中序遍历

遍历顺序：左子树 根 右子树

void InOrder(BTNode* root){if (root == NULL){printf("NULL ");return;}InOrder(root->left);//打印在中间printf("%d ", root->data);InOrder(root->right);}

打印结果

NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL

4.后序遍历

遍历顺序：左子树 右子树 根

void PostOrder(BTNode* root){if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);//打印在最后printf("%d ", root->data);}

打印结果

NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1

层序遍历

思路：

借助先进先出的性质，上一层节点出的时候，带下一层的节点进去。

先把根入队列。

根节点出来的时候，左右孩子进去。

// 层序遍历void LevelOrder(BTNode* root){//初始化队列，注意队列里面存的是 指针类型。Queue q;QueueInit(&q);//如果树不为空开始入队if (root){QueuePush(&q, root);}//树不为空开始出对头数据，同时入队左子树和右子树，直到队列为空。while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->data);//如果还有左右子树，继续入队，否则不入队if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}//记得销毁队列printf("\n");QueueDestory(&q);}

二、二叉树遍历算法的应用

1.求节点个数

思想：把大问题逐步分割为子问题。

思路：

树为空时返回0个节点。(树为空不意味着才开始就是空树，而是递归到最后一个为NULL的树返回)

树不为空时返回自己的1个节点+上一颗树返回的节点的个数。

// 二叉树节点个数int BinaryTreeSize(BTNode* root){//当树为空时if (root == NULL)return 0;//当树不为空时return BinaryTreeSize(root->left) +BinaryTreeSize(root->right) + 1;}

求叶子节点个数

思路：

树为NULL时，返回0.

两颗子树都不为NULL时，返回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层节点个数

思想：求上图第3层节点个数。

站在第1层来看，就是求第3层节点的个数

站在第2层的角度来看，就是求第2层节点的个数

站在第3层的角度来看，就是求第1层节点的个数

思路：

当树为空时返回0

当k为1时返回1。

不满足1和2，继续递归左右子树。

// 二叉树第k层节点个数int BinaryTreeLevelkSize(BTNode* root, int k){//当树为空时if (root == NULL)return 0;//当k为1时if (k == 1)return 1;//程序能走到这一行，说明树不为空，k也不为1.继续递归return BinaryTreeLevelKSize(root->left, k-1)+BinaryTreeLevelKSize(root->right, k - 1);}

4.查找值为x的节点

思想：

把最小规模的问题写在最前面作为限制

不满足最小规模的问题，则继续递归。将问题一步一步拆分为不可分割的子问题。

// 二叉树查找值为x的节点BTNode* BinaryTreeFind(BTNode* root, BTDataType x){//当树为空时if (root == NULL)return NULL;//当树的值等于x时if (root->data == x)return root;BTNode* a = BinaryTreeFind(root->left, x);if (a){return a;}BTNode* b = BinaryTreeFind(root->right, x);if (b){return b;}//没有x，则返回空return NULL;}

5.二叉树销毁

思路：相当于二叉树的后序遍历。

先把左右子树遍历完后，开始遍历根，对根进行free。

// 二叉树销毁void BinaryTreeDestory(BTNode* root){if (root == NULL)return;BinaryTreeDestory(root->left);BinaryTreeDestory(root->right);//free掉根free(root);}

6.前序遍历构建二叉树

思路：

对一串字符进行先序遍历，递归遍历二叉树，当遇见#时开始返回 连接 树。

通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树

#include <stdio.h>#include <stdlib.h>typedef struct BTNodeTree{    struct BTNodeTree* left;    struct BTNodeTree* right;    char val;}BTNode;//创建二叉树BTNode* CreateTree(char* a, int* pi){//如果树为#则返回null    if(a[*pi] == '#')    {        (*pi)++;        return NULL;    }    //否则构建节点，同时让pi++,以便继续递归    BTNode* root = (BTNode*)malloc(sizeof(BTNode));    root->val = a[(*pi)++];    //构建左右子树    root->left = CreateTree(a, pi);    root->right = CreateTree(a, pi);    //构建完后返回根节点。    return root;}//中序遍历打印。void inorder(BTNode* root){    if(root == NULL)        return;    inorder(root->left);    printf("%c ", root->val);    inorder(root->right);}int main(){    char a[100];    scanf("%s", a);    int i = 0;    BTNode* tree = CreateTree(a, &i);    inorder(tree);    return 0;}

7.判断二叉树是否是完全二叉树

思路：

层序遍历，空节点也进队列

出到空节点以后，出队列中所有数据，如果全是空，则是完全二叉树

8.求二叉树的深度

思路：二叉树的最大深度等价于：左右子树的最大深度 + 1

int maxDepth(struct TreeNode* root){    if(root == NULL)     {        return 0;    }    size_t left = maxDepth(root->left) + 1;    size_t right = maxDepth(root->right) + 1;    if(right > left)     {        return right;    }    return left;}

//判断二叉树是否是完全二叉树bool BTreeComplete(BTNode* root){Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL)break;QueuePush(&q, front->left);QueuePush(&q, front->right);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);//空后面出到非空，那说明不是完全二叉树if (front)return false;}//否则是完全二叉树return true;}

三、二叉树LeetCode题目

以下题目均属于LeetCode的 简单 题目

1.单值二叉树

如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时，才返回 true；否则返回 false。

思想：

看一棵树的三个部分是否相同，相同则继续递归下一颗树，直到树为空。

bool isUnivalTree(struct TreeNode* root){    //当树为空时。    if(root == NULL)    {        return true;    }    //当右树不为空，并且 根 != 左树    //当右树不为空，并且 根 != 右树时    if(root->left != NULL && root->val != root->left->val)    return false;    if(root->right != NULL && root->val != root->right->val)    return false;    //能走到这一行，说明第一层树的值相同了。接着递归左右子树。    return isUnivalTree(root->left) &&             isUnivalTree(root->right);}

2. 检查两颗树是否相同

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

bool isSameTree(struct TreeNode* p, struct TreeNode* q){    //当两树都为空时    if(p == NULL && q== NULL)        return true;    //当其中一个树为空时    if(p == NULL || q == NULL)        return false;    //走到这里说明两树存在，比较两树的值    if(p->val != q->val)        return false;    //走到这里说明两树的根节点相同，继续递归，直到判断完左右子树为止。    return isSameTree(p->left, q->left)     && isSameTree(p->right, q->right);}

3. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

bool isSym(struct TreeNode* q, struct TreeNode* p){      //当只有一个根节点时    if(q == NULL && p == NULL)         return true;    //当其中一个子树为空时    if(q == NULL ||p ==NULL)         return false;    //程序走到一这行，说明左右节点存在。当两个根节点不相等时    if(q->val != p->val)    return false;    //走到这一步说明左右节点相同，开始递归左右子树    return isSym(q->left, p->right) && isSym(q->right, p->left); }bool isSymmetric(struct TreeNode* root){    //当是空树时    if(root == NULL)        return true;    return isSym(root->left, root->right);}

4.另一颗树的子树

思路：

用到了上一题判断两棵树是否相同的思想。

bool isSameTree(struct TreeNode* p, struct TreeNode* q){    //当两树都为空时    if(p == NULL && q== NULL)        return true;    //当其中一个树为空时    if(p == NULL || q == NULL)        return false;    //走到这里说明两树存在，比较两树的值    if(p->val != q->val)        return false;    //走到这里说明两树的根节点相同，继续递归    return isSameTree(p->left, q->left)     && isSameTree(p->right, q->right);}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){    //递归结束条件。当根为空时，并不是说明没有节点，可能是所有的子树都遍历过了。然后不相等返回false    if(root == NULL)    return false;//走到这里说明子树不为空，开始比较子树和sub相同不。    bool a = isSameTree(root, subRoot);    if(a)    return a;    //走到这里说明不相同，继续递归左子树和右子树，其中一个相同就返回true。    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);}

二叉树的前序遍历

题目思路

求节点个数，开辟数组大小。

前序遍历存放到数组中

 int treeSize(struct TreeNode* root) {     if(root == NULL)        return 0;     return treeSize(root->left) + treeSize(root->right)+1;  } void preorder(int* a, struct TreeNode* root, int* i) {     if(root == NULL)     {          return;     }     a[(*i)++] = root->val;     preorder(a,root->left, i);     preorder(a,root->right, i); }int* preorderTraversal(struct TreeNode* root, int* returnSize){    //计算树有几个节点,然后开辟相应的空间    int size = treeSize(root);    int* a = (int*)malloc(sizeof(int)* size);    int i = 0;//设置下标i    *returnSize = size;//需要返回的数组大小    //前序遍历依次存放到数组中。    preorder(a, root, &i);    return a;}

6.反转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

我犯的BUG：只是对二叉树里面的值进行交换，但是无法避免空指针。一直都是空指针的错误，因为root总会为空，root->data总会遇见空指针

所以以后尽量要多想着交换地址。

void _invertTree(struct TreeNode* root){    if(root)    {        struct TreeNode* tmp = root->left;        root->left = root->right;        root->right = tmp;        _invertTree(root->left);        _invertTree(root->right);    }}struct TreeNode* invertTree(struct TreeNode* root){    _invertTree(root);    return root;}

“C语言数据结构二叉树递归的方法”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注编程网网站，小编将为大家输出更多高质量的实用文章！