二叉树+oj

• 什么是链式结构？
• • 二叉树操作的思路
  • • • 二叉树的前/后/中序遍历
      • 二叉树的层序遍历
• 二叉树的节点个数
• • 二叉树叶子节点的个数
  • • 二叉树第k层节点的个数
    • • 查找二叉树中值为X的节点
      • 判断二叉树是否是完全二叉树
    • 二叉树的高度
    • 二叉树的销毁
    • oj

什么是链式结构？

二叉树我之前阐述过了，有两种储存方式，具体的可以在我这篇博客了解：二叉树入门详解
链式结构中一个节点内有数值和左孩子以及右孩子的指针，我目前创建二叉树还是直接手动创建的，这篇博客主要讲的是我对二叉树的的具体操作！
我将构造这个二叉树，下面除oj题外所有操作都是基于我构造的这个二叉树的

typedef int BTDataType;typedef struct BinaryTreeNode{BTDataType val;struct BinaryTreeNode* left;struct BinaryTreeNode* right;}BTN;BTN* BuyBinaryTreeNode(BTDataType x)//申请一个节点的空间{BTN* tam = (BTN*)malloc(sizeof(BTN));if (tam == NULL){printf("malloc fail\n");exit(-1);}tam->val = x;tam->left = NULL;tam->right = NULL;}BTN* CreatBinaryTree(){BTN* node1 = BuyBinaryTreeNode(1);BTN* node2 = BuyBinaryTreeNode(2);BTN* node3 = BuyBinaryTreeNode(3);BTN* node4 = BuyBinaryTreeNode(4);BTN* node5 = BuyBinaryTreeNode(5);BTN* node6 = BuyBinaryTreeNode(6);BTN* node7 = BuyBinaryTreeNode(7);node1->left = node2;node1->right = node3;node2->left = node4;node2->right = node5;node3->left = node6;node3->right = node7;return node1;   }int main(){BTN* tree = CreatBinaryTree();return 0;}

二叉树操作的思路

二叉树的结构我们思考一下，大致是一个根节点然后带两个子树，子树又可以分为一个根节点加两个子树（子树有可能是空节点）

根据结构我们可以发现解决有关二叉树的问题时，我们可以用递归来解决，我们都可以从：根节点+左子树+右子树出发，一直递归，并且递归的终止条件就是遇到空节点

二叉树的前/后/中序遍历

相同点：都是把整个二叉树遍历一遍
不同点：遍历的顺序不同

前序：根节点+左子树+右子树
中序：左子树+根节点+右子树
后序：左子树+右子树+根节点
注意前面三个遍历指的是每个结点都是这样的
层序：设根节点为第一层，然后从上到下访问每一层的所有结点。
注：我们下面的操作都是以上面直接构造的二叉树为例的

我在这边画一下谦虚遍历的情况，中序以及后序遍历思想都是一样的
下面是前序遍历的数字顺序：

要点：我们将每个结点都看作是一个根节点，然后根据前序遍历的规则：跟+左+右遍历整个二叉树

void PrevOrder(BTN* root)//前序遍历{if (root == NULL)//首先判断一下该节点是否为空结点{printf("NULL ");return;}//不是NULLprintf("%d ", root->val);//根节点PrevOrder(root->left);//左子树PrevOrder(root->right);//右子树}void InOrder(BTN* root)//中序遍历{if (root == NULL)//首先判断一下该节点是否为空结点{printf("NULL ");return;}//不是NULLInOrder(root->left);//左子树printf("%d ", root->val);//根节点InOrder(root->right);//右子树}void PostOrder(BTN* root)//后序遍历{if (root == NULL)//首先判断一下该节点是否为空结点{printf("NULL ");return;}//不是NULLPostOrder(root->left);//左子树PostOrder(root->right);//右子树printf("%d ", root->val);//根节点}

前面画了一张前序数字的遍历图，下面画一张中序遍历的函数栈帧！

**注：**由于是递归，我们先判断递归的结束条件，防止栈溢出无限递归的出现。

二叉树的层序遍历

层序：设根节点为第一层，然后从上到下访问每一层的所有结点。

思路：
层序遍历不能用递归的思想，而是用得借用队列先进先出的性质。
1，头结点入队
2.上一个结点入队的时候，下一结点出队
3，注意：入队的时候必须是非空
注意：因为用的是C语言，所以我们还要自己构造队列
其实跟我们之前写的队列差不多，只需要改这个tyepedef
struct BinaryTreeNode*QDataType表示此时队列的元素是指针

Queue.h

#pragma once #include#include#include#includetypedef struct BinaryTreeNode* QDataType;//注意这个时候队列的元素变成了结构体指针typedef struct QueueNode{QDataType data;struct QueueNode* next;}QueueNode;typedef struct Queue{QueueNode* front;QueueNode* rear;}Queue;void QueueInit(Queue* ps);//队列的初始化void QueueDestory(Queue* ps);//队列的销毁void QueuePush(Queue* ps, QDataType x);//入队void QueuePop(Queue* ps);//出队bool QueueEmpty(Queue* ps);//判断队列是否为空size_t QueueSize(Queue* ps);//返回队列中元素的个数QDataType QueueFront(Queue* ps);//返回队头元素QDataType QueueRear(Queue* ps);//返回队尾元素

Queue.c

 #define _CRT_SECURE_NO_WARNINGS 1#include"QUeue.h"void QueueInit(Queue* ps)//队列的初始化{    assert(ps);//如果储存指针的地址都为空的话，肯定是错误的    //刚开始的头指针与尾指针肯定是相等的，并且都是NULL    ps->front = ps->rear = NULL;}void QueueDestory(Queue* ps)//队列的销毁{    assert(ps);    QueueNode* cur = ps->front;    while (cur)    { QueueNode* ret = cur->next; free(cur); cur = ret;    }    ps->front = ps->rear = NULL;}void QueuePush(Queue* ps, QDataType x)//入队{    assert(ps);//入队肯定是与尾指针rear有关的 先申请一个空间    QueueNode* cur = (QueueNode*)malloc(sizeof(QueueNode));    if (cur == NULL)    { printf("malloc fail\n"); exit(-1);    }    cur->data = x;    cur->next = NULL;    /* QueueNode* ret = ps->rear->next;     ps->rear = cur;这样写的话很有问题，没有判断当两个指针都为空指针的情况     ps->rear = ret;*/    if (ps->rear == NULL)    { assert(ps->front == NULL);//当尾指针为空的时候，头指针不可能不为空 ps->front = ps->rear = cur;    }    else    { ps->rear->next = cur; ps->rear = cur;    }}void QueuePop(Queue* ps)//出队{    assert(ps);//出队也是头删    assert(ps->front != NULL);//如果头指针为空的话肯定是错误的    //队列中只有一个结点    if (ps->front == ps->rear) ps->front = ps->rear = NULL;    else    { //ps->front = ps->front->next;这样写的话涉及到内存泄露 QueueNode* ret = ps->front->next; free(ps->front); ps->front = ret;//这样写的话就不会涉及到什么内存泄露啦    }}bool QueueEmpty(Queue* ps)//判断队列是否为空{    assert(ps);    //当头指针为空的时候，队列就是空的    return ps->front == NULL;}size_t QueueSize(Queue* ps)//返回队列中元素的个数{    assert(ps);    int sum = 0;    QueueNode* cur = ps->front;    while (cur)    { sum++; cur = cur->next;    }    return sum;}QDataType QueueFront(Queue* ps)//返回队头元素{    assert(ps);    assert(ps->front != NULL);    return ps->front->data;}QDataType QueueRear(Queue* ps)//返回队尾元素{    assert(ps);    assert(ps->rear != NULL);    return ps->rear->data;}

层序遍历：

void LevelOrder(BTN* root){Queue st;QueueInit(&st);//此时队列中元素表示的是指针QueuePush(&st, root);while (!QueueEmpty(&st))//当队列非空的时候{//上一个节点出队的时候，该节点的子节点入队（但是要求子节点非空）BTN* cur = QueueFront(&st);QueuePop(&st);//弹出该节点if (cur == NULL)break;printf("%d ", cur->val);if (cur->left != NULL)QueuePush(&st, cur->left);if (cur->right != NULL)QueuePush(&st, cur->right);}}

二叉树的节点个数

思路：
节点个数 = 根节点+左子树节点个数+右子树节点个数

int BinaryTreeSize(BTN* root)//二叉树的节点个数{if (root == NULL)return 0;return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);}

二叉树叶子节点的个数

思路:返回左子树叶子节点以及右子树叶子节点

int BinaryTreeLeafSize(BTN* root)//叶子节点必须保证左子树为NULL 右子树为NULL{if (root == NULL)//空节点直接返回return 0;if (root->left == NULL && root->right == NULL)return 1;return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);}

二叉树第k层节点的个数

思路：
查找第k层的节点个数
假设k = 1层，直接返回第一层的节点个数
k = 2时，返回的是以第二层的节点为根节点的第一层的节点个数
(这个思路可能没解释清楚）
结合下面的代码思考一下，当k = 2的时候，返回的不就是第一个节点的左右子树的结点数嘛?
注：我们的参数就是一个指针，只能返回1，但是最终的返回值是左右两边的和

意思是两个参数，当k的那个参数为1的时候，返回该层的个数即可

int BinaryTreeLevelKSize(BTN* root, int k){if (root == NULL)return 0;//当k = 1的时候，返回1即可if(k==1)return 1;//当k不等于1的时候return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);//返回的是k = 1的时候左右子树的节点个数}

查找二叉树中值为X的节点

思路：
查询根节点，若根节点不符合，查询左子树，查询右子树
递归即可！

BTN* BinaryTreeFind(BTN* root, BTDataType x){if (root == NULL)//当指针为空指针的时候return NULL;if (root->val == x)return root;BTN* tal = BinaryTreeFind(root->left, x);if (tal)//当查询左子树的返回值不为空的时候，直接返回即可，就不用区查询右子树return tal;/*BTN* tar = BinaryTreeFind(root->right, x);if (tar)return tar;*///还可以这样写return BinaryTreeFind(root->right, x);}

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

思路：其实和层序遍历类似，也是要先写一个队列结构，然后上一个元素出队列的时候，其子节点入队，然后当出队的元素是NULL时，跳出循环，然后遍历剩余队列，如果队列后面还有数字，那么就不是完全二叉树
**注意：此时不上一个节点只要出队了，其子节点就要入队，不用管其子节点是否为空节点

bool BinaryTreeComplete(BTN* root)//判断二叉树是否为完全二叉树{if (root == NULL)return false;Queue st;QueueInit(&st);QueuePush(&st, root);while (!QueueEmpty(&st)){BTN* cur = QueueFront(&st);//因为要出队，所以我们要记录此时的队列首元素QueuePop(&st);if (cur == NULL)break;//如果元素是NULL便跳出循环 否则入队//此时入队与层序遍历不同，不论是否为NULL都得入QueuePush(&st, cur->left);QueuePush(&st, cur->right);}while (!QueueEmpty(&st))//此时依次遍历队列，观察每个队列中是否有数字{BTN* cur = QueueFront(&st);//因为要出队，所以我们要记录此时的队列首元素QueuePop(&st);if (cur != NULL)return false;}//此时说明队列全部出完了，此时证明为完全二叉树return true;}

二叉树的高度

思路：
二叉树的高度 = max（左子树的高度，右子树的高度）+1（根节点）

int BrnaryTreeHigh(BTN* root)//计算树的高度{if (root == NULL)//递归到空节点时返回0return 0;return max(1 + BrnaryTreeHigh(root->left), 1 + BrnaryTreeHigh(root->right));}

二叉树的销毁

思路：我们直到，二叉树的构建是从上到下的，但是二叉树的销毁不能也是这样，因为如果我们先销毁根节点的话，那么我们的子节点就找不到了，所以我们应该先销毁左子树，再销毁右子树，最后销毁根节点的顺序来实施

oj

单值二叉树

思路：只要父节点的值不等于孩子的值就返回false

bool isUnivalTree(struct TreeNode* root){if(root==NULL) return true; //注意：做子树有可能是没有的！ if(root->left&&root->val!=root->left->val) return false; if(root->right&&root->val!=root->right->val) return false; return isUnivalTree(root->left)&&isUnivalTree(root->right);}

相同的树
思路直接写在代码里

bool isSameTree(struct TreeNode* p, struct TreeNode* q){ //如果两个节点都为空节点，那么返回true if(p==NULL&&q==NULL) return true; //如果只有一个节点为空节点，返回false if(p==NULL||q==NULL) return false; //现在两个节点都不是空节点了，判断一下值是否相等 //如果不相等直接返回false if(p->val!=q->val) return false; //该节点判断完毕，然后判断一下左右子树 return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);}

另一棵树的子树
思路：
依次遍历树的每一个节点，然后以该节点为根节点，跟另一棵树比较是否相等，就是套用一下上一题的代码，easy

bool checksame(struct TreeNode*p1,struct TreeNode*p2){   //这个函数判断的就是两个树是否相等    if(p1==NULL&&p2==NULL)//两棵树都为空的时候    return true;    if(p1==NULL||p2==NULL)//一棵为空，另外一颗不为空的时候    return false;    if(p1->val!=p2->val)    return false;    //接下来判断树的左右两颗子树是否相等    return checksame(p1->left,p2->left)    &&checksame(p1->right,p2->right);}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){   if(root==NULL)   return false;    //遍历每个以每个节点为根的子树  if(checksame(root,subRoot))  return true;  return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot); }

二叉树遍历

思路：
还是递归：
先判断该节点是否为空，如果不为空，赋值，然后判断左右子树

#include#includetypedef char BTDataType;typedef struct TreeNode {BTDataType val;struct TreeNode* left;struct TreeNode* right;}BTN;BTN* CreatBinaryTree(BTDataType *a,int*pi){    //当字符是'#'的时候，是空指针    if(a[*pi]=='#')    { (*pi)++; return NULL;    }  //此时字符不是'#'的时    BTN*tam = (BTN*)malloc(sizeof(BTN));    if(tam==NULL)    {    printf("malloc fail\n");    exit(-1);    }    tam->val = a[(*pi)++];//开辟了根节点之后    tam->left = CreatBinaryTree(a,pi);//理解这个。此时是以该节点的左孩子为根节点   //递归创造！    tam->right = CreatBinaryTree(a,pi);    return tam;} void InOrder(BTN*root) {     if(root==NULL)  return ;     InOrder(root->left);     printf("%c ",root->val);      InOrder(root->right);      }int main(){    char arr[100] = {0};    scanf("%s",arr);    int i = 0;    BTN*tree = CreatBinaryTree(arr,&i);    //这边一定记得是传地址，因为需要改变i的值    InOrder(tree);    return 0;}

欢迎三连！！！多谢铁子支持！！！

闲鱼礼物网