本文共 5477 字，大约阅读时间需要 18 分钟。

判断两棵二叉树是否相等

题目描述：给定两颗二叉树，如果它们结构一致，且节点值相同，则为相同。

//二叉树节点结构体struct BinaryNode{       int data;    BinaryNode* lc;    BinaryNode* rc;}*BTree;//判断二叉树是否相等的函数bool isEqual(BTree T1,BTree T2){       if(T1 == NULL && T2 == NULL)        return true;//都为空，相等。    if(T1==NULL||T2==NULL)    //由于上面的判断不成立，则T1，T2至少有一个不为空        return false;//一个空，一个不空，不相等    if(T1->data == T2->data) //如果根节点相等        return isEqual(T1->lc,T2->lc) && isEqual(T1->rc,T2->rc);//判断左右子树是否都相等    else //根节点不相等        return false;}

int judgebitree(bitree *bt1,bitree *bt2)//判断两个二叉树是否相同。{     	if (bt1==NULL && bt2==NULL)//两棵树对应位置都为空返回1  		return true;  	else if (bt1==NULL || bt2==NULL || bt1->data!=bt2->data) //两棵树的当前节点只有一个为空或者两棵树的当前节点的值不同。	  	return false;  	else 	  	return judgebitree(bt1->lchild,bt2->lchild)&&judgebitree(bt1->rchild,bt2->rchild//判断左右子树是否都相等}

给定一棵二叉树，判断它是否是镜像对称的

boolean isSymmetrical(BiNode* root1, BiNode* root2) {       if (root1 == null && root2 == null) {           return true;    }    else if(root1 == null || root2 == null || root1->val != root2->val) {           return false;//两棵树的当前节点只有一个为空或者两棵树的当前节点的值不同。    }    else{       //判断A的左边和B的右边是否相等，判断A的右边和B的左边是否相等，都相等就满足    return isSymmetrical(root1->lchild, root2->rchild) && isSymmetrical(root1->rchild, root2->lchild);    }}

计算给定二叉树的所有左叶子之和。（力扣）

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {   public:    int sum = 0; //全局变量    int sumOfLeftLeaves(TreeNode* root) {          getLeftLeave(root);         return sum;    }    void getLeftLeave(TreeNode* root){           //递归终止条件        if(root == NULL){               return ;        }        //找到左叶子节点         //  1.首先判断根节点有左孩子        //  2.再判断该左孩子是叶子节点（无子节点）        if(root->left!=NULL && root->left->left == NULL && root->left->right==NULL ){               sum += root->left->val;        }        //否则，继续递归判断他的左孩子与右孩子        getLeftLeave(root->left);        getLeftLeave(root->right);    }};

判断一个二叉树是否为完全二叉树

bool isCBT(BiTree root)//判断以root为头节点的二叉树是否为完全二叉树{       if(root==null)        return true;    bool isLeaf= false;//leaf变量用来标记一个状态是否发生（只要当前节点的左孩子和右孩子都为空或者左孩子不为空，右孩子为空时，这个状态就发生，只要发生了这个状态，以后访问到的节点必须都是叶节点）    queue<BiNode> queue;//通过队列q实现二叉树的层次遍历，通过层次遍历来判断是否为完全二叉树    queue.push(root);//根节点入队    while (!queue.empty())    {           BiNode p=queue.front();        queue.pop();        if((isLeaf&&(p->left!=NULL||p->right!=NULL))||(p->left==NULL&&p->right!=NULL)) // 如果之前(上)层遍历的结点没有右孩子，且当前的结点有左或右孩子，直接返回false// 如果当前结点有右孩子却没有左孩子，直接返回false            return false ;        if(p->left!=NULL)//左孩子不为空，加入到队列中去            queue.push(p->left);        if(p->right!=NULL){   //右孩子不为空，加入到队列中去            queue.push(p->right);        }        if((p->left!=NULL&&p->right==NULL)||(p->left==NULL&&p->right==NULL))//只有左孩子 或 是叶子节点            isLeaf=true;    }    return true;}

对于函数间的信息传递有三种方式：
(1)、主函数向被调用函数传参（普通参数：指针或引用类型）
(2)、被调用参数向主函数返回值
(3)、使用全局变量

其中对于全局变量来说，它一般用于整个树。即，它的信息对于整个树是公用的。任何结点都可以改变其值来传递给其他所有结点。（这里说的结点改变其值指的是对应的调用递归函数层次）。比如说在算结点个数、输出第k个结点的值等等。

对于被调用函数向主函数返回值，在二叉树中就是一般子结点向父节点（被调用函数向调用函数）返回信息。比如说是从左子树返回还是从右子树返回等。

对于第（1）种情况，引用较多的是传递引用或指针类型。这样，既可以父结点向子结点传递参数，也可以用同一个变量，子结点向父节点返回一些信息。一般上面二中能实现的，传递引用参数都能实现，不过每次都要传递对应参数而已。

在二叉树中删除以值x为根节点的子树

方法一

//传引用：递归删除二叉树中以x为根的子树（flag为标志）int DelRoot(BiTree &T, int x, int flag){     if(T == NULL)    return 0;  else  {       if(T->data == x)  //如果当前节点的值为x，则更改标志位，在下面将向递归子函数中传递flag值    {         flag = 1;    }    int leftmsg = DelRoot(T->lchild,x,flag); //递归左子树，lef_ret为从左子树中返回的信息    int rightmsg = DelRoot(T->rchild,x,flag); //递归右子树，rig_ret为从右子树中返回的信息    if(flag == 1){      //如果标志为1，说明其祖父结点中有x，也就是说当前结点需要删除      if(T->data == x)//如果就是x结点，则需要向上层结点传递信息，以便其父节点将对应的指针域赋空        return 1;      delete T;    }    else{          if(leftmsg == 1)  //从子结点接受收的信息，即如果其子结点为x，需要将其指针域赋空         T->lchild = NULL;       if(rightmsg == 1)  //从子结点接受收的信息，即如果其子结点为x，需要将其指针域赋空         T->rchild = NULL;    }  }  return 0;}//原文链接：https://blog.csdn.net/plm199513100/article/details/78509144

方法二

//删除以值ch为根节点的子树void deletex(BiTree &T, char ch){       if(T!=NULL){           Release(T);        T=NULL;    }    else{           deletex(T->lchild, ch);        deletex(T->rchild, ch);    }}void Release(BiTree T)//删除二叉树{       if(T!=NULL){           Release(T->lchild);        Release(T->rchild);        delete(T);    }}

输入节点值，找双亲节点：

BiTree Parent(BiTree T, char ch){   	if(T==NULL)        return NULL;    else{           if(T->data == ch){               return NULL;//要找的值刚好是根节点（根节点无双亲）        }        //左孩子是ch或者右孩子是ch        if(T->lchild!=NULL&&T->lchild->data==ch || T->rchild!=NULL&&T->rchild->data==ch){               return T;        }        else{               BiTree temp = new BiNode;            temp=Parent(T->lchild, ch);//递归在左子树里面找            temp=Parent(T->rchild, ch);            return temp;        }    }}

交换二叉树

BiTree Exchange(BiTree T)//返回指针类型{   	if(T==NULL)        return NULL;    else{           BiTree r = NULL;        r=T->lchild;        T->lchild=r->lchild;        T->rhild=r;        if(T->lchild!=NULL){               Exchange(T->lchild);        }        if(T->rchild){               Exchange(T->rchild);        }        return T;    }  }

二叉链表转顺序储存

void toArray(BiTree T, char A[], int i)//储存到A数组中{       if(T!=NULL){           A[i] = T->data;        toArray(T->lchild, A, 2*i);        toArray(T->rchild, A, 2*i+1);    }    else{       	A[i] = '#';//若T为空，说明上个节点的左或右孩子中必有空的情况       }}