数据结构---二叉树例题讲解

***1.

//第一种方法是遍历，需要记录下一层返回的是true还是false

//第二种方法：用递归来实现

当前节点为空：返回0

当前节点不为空：判断该结点的值与左右节点的值是否相等

注意判断条件，判断相等的时候条件不好写，那就写当不相等的时候return false

bool isUnivalTree(struct TreeNode* root)
{
    if(root==NULL)
        return true;//记住这个地方可不是false啊
    //因为这个地方只是节点为空，代表遍历到空节点了
    //并不是遇到了不相等的情况，不需要结束程序
    if(root->left&&root->left->val!=root->val)
    {
        return false;
    }
    if(root->right&&root->right->val!=root->val)
    {
        return false;
    }
    //走到这里说明该结点的值和左右节点的值相等
    //那么就需要往更深处遍历了
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

***2.求二叉树第k层的节点数量

int TreeLevelKSize(BTNode* root,int k)
{
    if(root==NULL)
    {
        return 0;
    }
    if(k==1)
    {
        return 1;
    }
    //子问题
    //往深处递增k减小
    return TreeLevelKSize(root->left,k-1)+TreeLevelKSize(root->right,k-1);
}

***3.在二叉树中查找值为x的节点，然后返回该结点的指针

注意：隐含条件是找到一个节点之后就不再找了，因为函数只有一个返回值！！！

//错误操作：

指针赋值的基本概念可以追溯到计算机科学中，其中指针是一个变量，其值是另一个变量的地址。通过指针变量，我们可以直接访问和操作存储在其他位置的数值。指针赋值的具体操作包括：如果我们有一个指针p，它的值是变量a的地址，那么我们可以创建一个新指针q，并将p的值赋给它，这样q就指向了a。

这段代码，首先为ansleft和ansright开辟了空间，然后FinfX的返回值赋值给他们。这个过程相当于这两个指针首先指向malloc出来的那一块空间，然后又指向了返回值的那一块空间，malloc的那一块空间就没有指针指向，造成了内存泄漏！！！

//找节点6的递归展开图简图示例

//正确代码如下：

BTNode* TreeFind(BTNode* root,BTDataType n)
{
    if(root==NULL)
    {
        return NULL;
    }
    if(root->val==n)
    {
        return root;
    }
    //保存下来是为了防止进行更多次的查找
//否则在回溯的过程中还需要一次次地递归到查找到的那个节点
    BTNode* ret1=TreeFind(root->left,n);
    if(ret1)
        return ret1;
    BTNode* ret2=TreeFind(root->right,n);
    if(ret2)
        return ret2;
    //每种情况必须要有返回值
    return NULL;
}

***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);
}

***5.检查二叉树是否对称

注意：左子树的右子树和右子树的左子树进行比较。是否是空树。其余代码与上一题一样。

bool _checkSymmetricTree(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 _checkSymmetricTree(p->left,q->right)&&_checkSymmetricTree(p->right,q->left);
}
bool checkSymmetricTree(struct TreeNode* root) {
//一定要注意空树的时候
    if(root==NULL)
        return true;
    return _checkSymmetricTree(root->left,root->right);
}

***6.二叉树的前序遍历

与之前不同的是需要将节点的值存进数组中然后输出

//给出的函数声明

//int* preorderTraversal(struct TreeNode* root, int* returnSize);

//注意：若i不传指针的话，下一层的i++不影响上一层i的值，造成错误的值的覆盖

int TreeSize(struct TreeNode* root)
{
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}
//这个地方pi是计数器，是记录此时遍历到数组a的哪一个位置，然后把节点的值存进去的
//pi不用地址的话，当一个节点有左右两个节点，当遍历左右这两个节点的时候，pi的值是相同的，就会发生覆盖
void PreOrder(struct TreeNode* root,int *a,int* pi)
{
    if(root==NULL)
        return;
    a[(*pi)++]=root->val;
    PreOrder(root->left,a,pi);
    PreOrder(root->right,a,pi);
}
//由于一个函数不可能会有不同的返回值，所以遍历需要重新写一个函数，不能用当前这个函数进行递归，当前函数递归最后只能返回一个节点
//这个returnSize是输出型参数，要把这个值带到main函数中，这个值记录了节点个数，所以可以遍历该二叉树求出这个值
//Note: The returned array must be malloced, assume caller calls free().
//上面提示的这句话提示我们要給用到的那个数组malloc一块空间
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize=TreeSize(root);
    int* a=(int*)malloc(sizeof(int)*(*returnSize));
    int i=0;
    PreOrder(root,a,&i);//这个地方切记要对i进行取地址
    return a;
}

***7.判断一棵树是否是另一棵树的子树

(相当于是把判断两棵树是否相等和查找二叉树中某个结点的代码结合起来）

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 isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
    return false;
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    if(root==NULL)
        return false;
    if(root->val==subRoot->val&&isSameTree(root,subRoot))
        return true;
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

***8.根据前序遍历的字母序列（#代表空节点）输出按照中序排列的节点（不含空节点）

（ps：代码如图片所示）

根据一段序列构建出的二叉树，遇到空就停止

//这个地方切忌写成 if(a[(*pi)++]=='#'),因为这个位置不一定是#，只有是#才往后++，否则就会越过此时的这个节点了

//不断递归创建左右子树

***9.二叉树的销毁

注意：要使用后序遍历法，否则把根节点销毁了就没法找到其左子树和右子树了

//这个root置空没意义，因为他改变不影响主调函数中的root，可以在main函数中给这个root置空。如果非要在这个函数中改变的话要传二级指针

***10.层序遍历（bfs）

借助队列实现，从根节点开始入队，根进去，然后把根拿出来，把根的左右孩子放进去（队尾进），再拿出队列的第一个元素（根的左孩子，没有左孩子就是右孩子），再把这个元素的左右孩子放进队尾，逐渐循环......

注意：队列中存的是节点的地址，当执行QueuePop的时候，删掉的那个节点是队列的节点，并不影响二叉树的相应节点。

***11.判断二叉树是否是完全二叉树

注意：完全二叉树！=满二叉树，不能通过比较高度和节点个数之间的关系得到规律

要抓住完全二叉树的定义：前h-1层是满的，最后一层可以满也可以不满，但是最后一层必须连续，中间不能有空缺。

（像下面这张图中右下方的树就不是完全二叉树，因为最后一层中间有空缺）

//思路：

1出来带2.4，2出来带3.6，4出来带空.空，3出来带空.空，6出来带空.空，下一个就到空出来了，空出来的时候队列中只剩下空的话，此时该二叉树就是完全二叉树；如果队列中不为空，那么该二叉树就不是完全二叉树。

//代码如下：