1：假设二叉树中每个结点的值为单个字符，设计一个算法将一棵以二叉链方式存储的二叉树 b 转换成对应的顺序存储结构 a。

代码：

void Ctree(BTNode *b,SqBTree a,int i){if(b!=NULL){a[i]=b->data;Ctree(b->lchild,a,2*i);Ctree(b->rchild,a,2*i+1);}else a[i]='#';
} 

2： 假设二叉树中每个结点值为单个字符，采用顺序存储结构存储。设计一个算法， 求二叉树 t 中的叶子结点个数。

思想：用 i 遍历所有的结点，当 i 大于等于 MaxSize 时，返回 0。当 t[i]是空结点时返回 0； 当 t[i]是非空结点时，若它为叶子结点，num 增 1；否则递归调用 num1=LeftNode(t，2*i) ，求出左子树的叶子结点个数 num1，再递归调用 num2=LeftNode(t，2*i+1)求出右子树的叶 子结点个数 num2，置 num+=num1+num2。最后返回 num。

代码：

int LeafNode(SqBTree t,int i){//i初始值为1int numl,numr,num=0;if(i<MaxSize){if(t[i]!='#'){if(t[2i]=='#'&&t[2i+1]=='#'){num++;}else{numl=LeafNode(t,2*i);numr=LeafNode(t,2*i+1);num=numl+numr;}return num;}return 0;}else{return 0;} 
}

3：假设二叉树中每个结点值为单个字符，采用二叉链存储结构存储。设计一个算法 计算一棵给定二叉树 b 中的所有单分支结点个数。

代码：

int isonebranch(BTNode *b){int numl,numr,n;if(b==NULL){return 0;}else if((b->lchild==NULL&&b->rchild!=null)||(b->lchild!=NULL&&b->rchild==NULL)){n=1;}else{n=0;}numl=isonebranch(b,b->lchild);numr=isonebranch(b,b->rchild);return    (numl+numr+n); 
}

4：假设二叉树中每个结点值为单个字符，采用二叉链存储结构存储。设计一个算法求二叉树 b 中最小值的结点值。

代码：

void FindMinNode(BTNode *b,char &min){if(b->data<min){min=b->data;}else{FindMinNode(b,b->lchild);FindMinNode(b,b->rchild);}
}
void MinNode(BTNode *b){if(b!=NULL){char min=b->data;FindMinNode(b,min);printf("Min=&c\n",min);}
}

5： 假设二叉树中每个结点值为单个字符，采用二叉链存储结构存储。设计一个算法将二叉链 b1 复制到二叉链 b2 中。

思想：当 b1 为空时，置 b2 为空树。当 b1 不为空时，建立 b2 结点（b2 为根结点），置 b2->data=b1->data；递归调用 Copy(b1->lchild，b2->lchild)，由 b1 的左子树建立 b2 的左 子树；递归调用 Copy(b1->rchild，b2->rchild)，由 b1 的右子树建立 b2 的右子树。

代码：

void copy(BTNode *b1,BTNode *b2){if(b1==NULL){b2=NULL;}else{b2=(BTNode*)malloc(sizeof(BTNode));b2->data=b1->data;copy(b1->lchild,b2->lchild);copy(b1->rchild,b2->rchild);}
}

6：假设二叉树中每个结点值为单个字符，采用二叉链存储结构存储。设计一个算法， 求二叉树 b 中第 k 层上叶子结点个数。

思想：采用先序遍历方法，当 b 为空时返回 0。置 num 为 0。若 b 不为空，当前结点的 层次为 k，并且 b 为叶子结点，则 num 增 1，递归调用 num1=LevelkCount(b->lchild，k，h+1) 求出左子树中第 k 层的结点个数 num1，递归调用 num2=LevelkCount(b->rchild，k，h+1)求出右子树中第 k 层的结点个数 num2，置 num+=num1+num2，最后返回 num。

代码：

int LevelKCount(BTNode *b,int k,int h){int numl,numr,n=0;if(b!=NULL){if(h==k&&b->lchild==NULL&&b->rchild==NULL){num++;}else{numl=LeveKCount(b->lchild,k,h+1);numr=LeveKCount(b->rchild,k,h+1);num += numl+numr;return num;}}return 0;
}int Levelkleaf(BTNode *b,int k){return Leve;KCount(b,k,1);
}

 7：假设二叉树中每个结点值为单个字符，采用二叉链存储结构存储。设计一个算法， 判断值为 x 的结点与值为 y 的结点是否互为兄弟，假设这样的结点值是唯一的。

思想：采用先序遍历方法，当 b 为空时直接返回 false；否则，若当前结点 b 是双分支结

点，且有两个互为兄弟的结点 x、y，则返回 true；否则，递归调用 flag=Brother(b->lchild，

x，y)，求出 x、y 在左子树中是否互为兄弟，若 flag 为 true，则返回 true；否则递归调用

Brother(b->rchild，x，y)，求出 x、y 在右子树中是否互为兄弟，并返回其结果。

代码：

bool Brother(BTNode *b,char x,char y){bool flag;if(b==NULL){return false;}else{if(b->lchid!=NULL && b->rchild!=NULL){if((b->lchild->data==n&&b->rchild->data==y)||(b->lchild->data==y&&b->rchild==x)){return true;}flag=Brother(b->lchild,x,y);if(flag==true){return true;}else{return Brother(b->rchild,x,y);}}}
}

8：

假设二叉树中每个结点值为单个字符，采用二叉链存储结构存储。设计一个算法，采用先序遍历方法求二叉树 b 中值为 x 的结点的子孙，假设值为 x 的结点是唯一的。

思想：设计 Output(p)算法输出以 p 为根结点的所有结点。首先在二叉树 b 中查找值为 x

的结点，当前 b 结点是这样的结点，调用 Output(b->lchild)输出其左子树中所有结点，调用

Output(b->rchild)输出其右子树中所有结点，并返回；否则，递归调用 Child(b->lchild，x)

在左子树中查找值为 x 的结点，递归调用 Child(b->rchild，x)在右子树中查找值为 x 的结点。

代码：

void Output(BTNode *p){if(p!=NULL){printf("%c",p->data);Output(p->lchild);Output(p->rchild);}
}
void Child(BTNode *b,char x){if(b!=NULL){if(b->data==x){if(b->lchild!=NULL){Output(b->lchild);}if(b->rchild!=NULL){Output(b->rchild);return;}}Child(b->lchild,x);Child(b->rchild,x);}
}

9：假设二叉树采用二叉链存储结构，设计一个算法把二叉树 b 的左、右子树进行交 换。要求不破坏原二叉树。

//方法一
void Swap(BTNode *b,BTNode *&b1){if(b==NULL){b1=NULL;}else{b1=(BTNode *)malloc(sizeof(BTNode));b1->data=b->data;Swap(b->lchild,b1->rchild);Swap(b->rchild,b1->lchild);}
}//方法二：力扣226
struct TreeNode* invertTree(struct TreeNode* root) {if(root==NULL){return root;}struct TreeNode* temp=NULL;temp=root->left;root->left=root->right;root->right=temp;if(root->left != NULL){invertTree(root->left);}if(root->right != NULL){invertTree(root->right);}return root;}

bool Symm(BTNode *b1,BTNode *b2){if(b1==NULL&&b2==NULL){return true; }else if(b1==NULL || b2==NULL){return false;}else{return (Symm(b1->lchild,b2->lchild)&&Symm(b1->rchild,b2->rchild));}
}bool Symmtree(BTNode *b){if(b==NULL){return true;}else{return Symm(b->lchild,rchild);}
}

bool CompBTNode(BTNode *b){BTNode *Qu[MAXsize],*p;int front=0,rear=0;//环形队列的队头和队尾指针 bool cm=true;//为真，则表示二叉树 bool bj=true;//为真，表示到目前为止所有结点均有左右孩子if(b==NULL) return true;//空树为完全二叉树 rear++;Q[rear]=b;//根节点进队 while(front!=rear){//队列不为空 front=(front+1)%MaxSize;p=Qu[front];//p结点出队 if(p->lchild==NULL){//p结点没有左孩子 bj=false;if(p->rchild!=NULL){//没有左孩子还是有右孩子 cm=false;}}else{if(bj==false) cm=false;//bj为假，而p还有左孩子时 rear=(rear+1)%MaxSize;Qu[rear]=p->lchild;//左孩子进队 if(rchild==NULL){bj=fase;//没有右孩子 } else{rear=(rear+1)%MaxSize;//右孩子进队 Qu[rear]=p->rchild;}}return cm;} 
}