二叉树习题
1.通过前序序列和中序序列构造二叉树
2.通过层次遍历序列和中序序列创建一棵二叉树
3.求一棵二叉树的结点个数
4.求一棵二叉树的叶子节点数
5.求一棵二叉树中度为1的节点个数
6.求二叉树的高度
7.求一棵二叉树中值为x的节点作为根节点的子树深度
8.判断两棵树是否相似，相似返回1，不相似返回0
9.设计算法利用叶子结点中的空指针域将所有叶子结点链接成一个带头结的双链表
10.假设一个仅包含二元运算的算术表达式以二叉链表形式存放在二叉树T,设计算法求解算术表达式
11.判断二叉树是否为完全二叉树(二叉树的层序遍历)
12.求一棵二叉树的最大宽度

1.通过前序序列和中序序列构造二叉树

创建树的过程，就是明确子树的创建过程，明确子树的创建过程，就是明确根节点的创建过程

#include <stdio.h>
#include <stdlib.h>typedef char ElemType;
typedef struct BiTNode
{ElemType data;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;void preOrder(BiTree T)   //二叉树的前序遍历，传入一个二叉树
{if(T!=NULL)  //子树根节点不为空{printf("%c ",T->data);preOrder(T->lchild);preOrder(T->rchild);}
}BiTNode * creatBitree(ElemType preOrderList[],int preStartIndex,int preEndIndex,ElemType inOrderList[],int inStartIndex,int inEndIndex)
{//确定递归结束条件，先序序列循环一遍if(preStartIndex>preEndIndex){return NULL;}//创建一个根节点BiTNode *T=(BiTNode *)malloc(sizeof(BiTNode));T->data=preOrderList[preStartIndex];  //先序序列开始位置为根节点//找当前根节点在中序序列的位置，确定当前根节点的左右子树int rIndex=0;     //当前在中序遍历中找到的根节点的索引for(rIndex=inStartIndex;rIndex<=inEndIndex;rIndex++ ){if(inOrderList[rIndex]==T->data)break;}//此时要在中序序列中，确定左右子树//当前左子树，应该是instratIndex到rIndex-1//当前右子树，应该是rIndex+1到inEndIndex//此时的先序序列的左子树，preStartIndex+1到preStartIndex+length//先序序列的右子树，preStartIndex+length+1 preEndIndexint length=rIndex-inStartIndex;T->lchild=creatBitree(preOrderList, preStartIndex+1, preStartIndex+length, inOrderList, inStartIndex, rIndex-1);T->rchild= creatBitree(preOrderList, preStartIndex+length+1, preEndIndex, inOrderList, rIndex+1, inEndIndex);return T;  //把根节点返回回去
}int main() {char preOrderList[]={'A','B','D','E','C','F','G'};int preOrderListLength=7;char inOrderList[]={'D','B','E','A','F','C','G'};int inOrderListLength=7;BiTree T= creatBitree(preOrderList, 0, preOrderListLength-1, inOrderList, 0, inOrderListLength-1);preOrder(T);printf("\n");}

2.通过层次遍历序列和中序序列创建一棵二叉树

#include <stdio.h>
#include <stdlib.h>typedef char ElemType;
typedef struct BiTNode
{ElemType data;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;void preOrder(BiTree T)   //二叉树的前序遍历，传入一个二叉树
{if(T!=NULL)  //子树根节点不为空{printf("%c ",T->data);preOrder(T->lchild);preOrder(T->rchild);}
}BiTNode * secend_creatBitree(char leverOrderList[],int LevelstartIndex,int LevelendIndex,char inOrderList[],int inStartIndex,int inEndIndex)
{if(LevelstartIndex>LevelendIndex) return NULL;// 创建根节点BiTNode *T=(BiTNode *)malloc(sizeof(BiTNode));T->data=leverOrderList[LevelstartIndex];int rIndex=inStartIndex;for(;rIndex<inEndIndex;rIndex++){if(T->data==inOrderList[rIndex])break;}//在层次遍历中，找到左子树和右子树，因为层次遍历中，寻找的过程是跳跃的，所以需要重新赋值左子树序列和右子树序列//外层循环是层次遍历的序列，因为层次遍历的顺序是不改变的，只是中间会有右子树的结点，会跳跃//内层循环是中序遍历的序列，依次和层次序列比较，声明新的数组存放当前新的左子树的层次遍历序列char lftLevelOrderList[100];int lftLevelOrderListlength=0;for(int j=LevelstartIndex+1;j<=LevelendIndex;j++){for(int i=inStartIndex;i<=rIndex-1;i++){if(leverOrderList[j]==inOrderList[i]){lftLevelOrderList[lftLevelOrderListlength++]=leverOrderList[j];}}}//同理右子树也是这么找的char rgtLevelOrderList[100];int rgtLevelOrderListlength=0;for(int j=LevelstartIndex+1;j<=LevelendIndex;j++){for(int i=rIndex+1;i<=inEndIndex;i++){if(leverOrderList[j]==inOrderList[i]){rgtLevelOrderList[rgtLevelOrderListlength++]=leverOrderList[j];}}}T->lchild=secend_creatBitree(lftLevelOrderList, 0, lftLevelOrderListlength-1, inOrderList, inStartIndex, rIndex-1);T->rchild=secend_creatBitree(rgtLevelOrderList, 0, rgtLevelOrderListlength-1, inOrderList,rIndex+1, inEndIndex);return T;
}int main() {char preOrderList[]={'A','B','D','E','C','F','G'};int preOrderListLength=7;char inOrderList[]={'D','B','E','A','F','C','G'};int inOrderListLength=7;char leverOrderList[]={'A','B','C','D','E','F','G'};int levelOrderListlength=7;BiTree T= secend_creatBitree(leverOrderList, 0, levelOrderListlength-1, inOrderList, 0, inOrderListLength-1);preOrder(T);printf("\n");}

3.求一棵二叉树的结点个数

思路如下:本质就是二叉树的遍历，每次访问到根的时候，用全局变量记录长度+1

int treelength=0;  //treelength是一个全局变量
void tree_length(BiTree T)
{if(T==NULL) return;treelength++;tree_length(T->lchild);tree_length(T->rchild);
}

4.求一棵二叉树的叶子节点数

思路:使用先序遍历访问二叉树的每一个结点，如果访问的结点为叶子结点，则二叉树叶子结点总数加1

int leafnodenum=0;  //这是全局变量
void leafnode_num(BiTree T)
{if(T==NULL) return;if(T->lchild==NULL&&T->rchild==NULL)leafnodenum++;leafnode_num(T->lchild);leafnode_num(T->rchild);
}

5.求一棵二叉树中度为1的节点个数

int singlenodenum=0;void getSinglenodenum(BiTree T)
{if(T==NULL) return;if(T->lchild==NULL||T->rchild==NULL){if(T->lchild!=NULL||T->rchild!=NULL) singlenodenum++;}getSinglenodenum(T->lchild);getSinglenodenum(T->rchild);
}

6.求二叉树的高度

大总结：
关于二叉树的高度与二叉树的深度：

明确什么是高度什么是深度？

明确二叉树的高度用什么遍历，二叉树的深度用什么遍历？
二叉树的高度用后序遍历，子结点把它的高度返回给它的父节点。
二叉树的深度用前序遍历

二叉树的最大深度其实就是二叉树根节点的高度

求二叉树高度的模版

伪代码:
左 int leftheight=getheight(node->left);
右 int rightheight=getheight(node->right);
根 return 1+max(leftheight+rightheight);伪代码精简版(不推荐，因为没有后序的过程)
return 1+max(getheight(node->left),getheight(node->right))

实际代码如下:

int getheight(BiTree T)
{if(T==NULL) return 0;int leftheight=getheight(T->lchild);int rightheight=getheight(T->rchild);int hegiht=0;if(leftheight>=rightheight)hegiht=leftheight;else hegiht=rightheight;return hegiht+1;
}

利用三目运算符精简如下:

int getheight(BiTree T)
{if(T==NULL) return 0;int leftheight=getheight(T->lchild);int rightheight=getheight(T->rchild);return leftheight>rightheight?leftheight+1:rightheight+1;
}

7.求一棵二叉树中值为x的节点作为根节点的子树深度

思路如下：
找到二叉树中值为x的节点，若值不存在，则返回0，如存在，用计算二叉树的高度模板，找节点的深度。
数据检验：输入B，看是否=2

int getheight(BiTree T)
{if(T==NULL) return 0;int leftheight=getheight(T->lchild);int rightheight=getheight(T->rchild);return leftheight>rightheight?leftheight+1:rightheight+1;
}BiTNode * seek_node(BiTNode*T, char x)
{if(T==NULL) return NULL;if(T->data==x) return T;BiTNode *temp=seek_node(T->lchild, x);if(temp!=NULL) return temp;return seek_node(T->rchild, x);}主函数：if(seek_node(T, 'B')!=NULL){printf("子树深度为：%d",getheight(seek_node(T, 'B'))) ;}else{printf("没有该结点");}

复盘总结:

seek_node寻找二叉树中，值为x的结点
框架是二叉树的前序遍历，根节点那块用来判断
当判断为一棵子树的左子树后，要判断是否返回左子树的结果，因为左子树和右子树的结果要选择一个返回给他们的父亲，故需要判断左子树结果是否满足，满足就返回左子树，此时就不遍历他兄弟，也就是右子树，若不满足，也不需要判断左子树是否满足了，直接返回右子树即可。

深度思考：
1.目标节点是左子树的最左结点，他的返回过程是什么样的？
找到最左结点，返回它，此时一直传到根节点的左子树判断，存在不为空，返回它，函数结束

2.目标结点是左子树的最右结点，他的返回过程是什么样的？
每一层都会返回return T reutrn T

8.判断两棵树是否相似，相似返回1，不相似返回0

基本思路：

树的问题=根节点的解+左右子树的解
出口：考虑判断空树
根节点的解:
若两棵树都是空树，则他们相似，return 1
若一棵树是空树另一棵不是空树，则他们不相似，return 0
左右子树的解：
根节点的解判断完毕，判断左右子树的解
判断左子树是否相似，isSimilar(r->lchild); 相似得到1，不相似得到0
判断右子树是否相似，isSimilar(r->rchild); 相似得到1，不相似得到0
左右子树都相似才算相似,才是完整解
root1->lchild, root2->lchild) && isSimilar(root1->rchild, root2->rchild
return 左右子树的解

// 判断两棵二叉树是否相似
int isSimilar(BiTNode *root1, BiTNode *root2) {// 如果两棵树的节点都是空的，则它们相似if (root1 == NULL && root2 == NULL) {return 1;}// 如果一个节点为空，另一个节点不为空，则它们不相似if (root1 == NULL || root2 == NULL) {return 0;}// 递归判断左子树和右子树是否相似return isSimilar(root1->lchild, root2->lchild) && isSimilar(root1->rchild, root2->rchild);
}

9.设计算法利用叶子结点中的空指针域将所有叶子结点链接成一个带头结的双链表

注意：双链表一定要使用尾插

void preOrderTraverse(BiTNode *&tail,BiTree T)
{if(T==NULL) return;//判断根节点if(T->lchild==NULL&&T->rchild==NULL){T->lchild=tail;tail->rchild=T;tail=T;}else{preOrderTraverse(tail, T->lchild);preOrderTraverse(tail, T->rchild);}}主函数+测试// 定义一个链表表头和尾指针BiTNode *head=(BiTNode *)malloc(sizeof(BiTNode));head->lchild=NULL;head->rchild=NULL;BiTNode *tail=head;BiTNode *p=head;preOrderTraverse(tail, T);while(p->rchild!=NULL){printf("%c ",p->rchild->data);p=p->rchild;}printf("\n");

注意点:这个else，最开始写代码的过程中，我没有写else，实际上不能不写，如果不写，会出线传入NULL，NULL==NULL是无法被判断的

10.假设一个仅包含二元运算的算术表达式以二叉链表形式存放在二叉树T,设计算法求解算术表达式

层序遍历：* + 3 1 2
中序遍历: 1 + 2 * 3
构造数据

int operatorFunc(char oprt,int left,int right)
{switch (oprt) {case '+':return left+right;break;case '-':return left-right;break;case '*':return left*right;break;case '/':return left/right;break;default:return 0;}
}int getResult(BiTree T)
{//表达式求值，是唯一一个后序遍历if(T==NULL) return 0;if(T->lchild==NULL&&T->rchild==NULL) //如果节点是叶子节点 ，返回它的值{return T->data-'0';}else   //如果不是叶子节点，是操作符，操作它的左右子树{return operatorFunc(T->data, getResult(T->lchild), getResult(T->rchild));}
}

11.判断二叉树是否为完全二叉树(二叉树的层序遍历)

思路：二叉树的层序遍历模版来解决该问题，因为用层序遍历我们不难发现当二叉树层序遍历到空结点后完全二叉树后面都应该为空结点。

二叉树的层次遍历：

注意变量是树的结点，是地址，是存放地址的指针变量。

二叉树的层序遍历主要代码思路：
首先要创建一个队列，将头结点放入队列中。
然后开始循环，若队列为空，则结束遍历。
队列不为空，先拿出队头元素，用中间变量把它存储起来，输出中间变量的值，删除这个队头元素，将中间变量所指向的左右孩子加入进队列，直到循环结束。

注意几个判空，元素加入队列的时候要判空
首先就是要判断是否存在根节点，再加入队列。
其次是，在加入左右孩子结点时，要注意，别加入空指针。

typedef struct BiTNode
{ElemType data;struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;typedef struct Queue
{BiTNode** Plist;  //该指针用于指向存储二叉树中每个结点地址的数组，该数组中的每个元素是一个地址int front;   //队头int rear; //队尾
}Queue;
//队列的建立
void initailQueue(Queue &Q)
{Q.Plist=(BiTNode**)malloc(sizeof(Queue)*100);Q.front=0;Q.rear=0;
}
//入队,循环队列
void enQueue(Queue &Q,BiTNode *e)
{Q.Plist[Q.rear]=e;Q.rear=(Q.rear+1)%100;
}
//出队
void deQueue(Queue &Q,BiTNode** e)
{*e=Q.Plist[Q.front];Q.front=(Q.front+1)%100;
}
//队列判空
int isemptyQueue(Queue Q)
{if(Q.front==Q.rear)return  1;else return 0;}
//当前队列的长度 头尾指针做差即可//二叉树的层序遍历开始
void levelOrderTraverse(BiTree T)
{Queue Q;initailQueue(Q);if(T!=NULL){enQueue(Q, T);}while(!isemptyQueue(Q)) //如果队列非空{//取出头结点front(),再pop()掉BiTNode *p=NULL;deQueue(Q,&p) ;   //注意这里的传入参数，是p指针的地址printf("%c ",p->data);  //这里开始输出层序遍历if(p->lchild!=NULL) enQueue(Q, p->lchild);          //子树不为空的时候加入子树if(p->lchild!=NULL) enQueue(Q, p->rchild);;}
}

问题的继续思考?

在该问题中，我们直接在循环中输出的二叉树，我们也可以声明一个动态数组，来储存每一次的结果，最后拿到主函数中，进行遍历输出。

---

判断二叉树是否为完全二叉树？
核心代码思路：
假如我们要加入队列的左右孩子结点，其中有空的，就弹出当前循环，以后再有结点加入队列，就不是完全二叉树。

给出一个非完全二叉树的例子：

int is_complete_bitree(BiTree T)
{//第一步，寻找第一个空树结点，用层序遍历Queue Q;initailQueue(Q);if(T!=NULL) enQueue(Q, T);while (!isemptyQueue(Q)) {BiTNode *p=NULL;deQueue(Q, &p);if(p->lchild!=NULL){enQueue(Q, p->lchild);}else{break;}if(p->rchild!=NULL){enQueue(Q, p->rchild);}else{break;}}  //找到了第一棵空子树while (!isemptyQueue(Q)) {BiTNode *p=NULL;deQueue(Q, &p);if(p->lchild!=NULL){return 0;}if(p->rchild!=NULL){return 0;}}    //若队列中，存在还有孩子的，就return 0//队列已为空return 1;
}

12.求一棵二叉树的最大宽度

二叉树的最大宽度，关键在于记录二叉树的是否同层的问题
该问题，是解决结点处理不同层结点问题的模版

原理图如下：

代码如下:

//二叉树的最大宽度
int max_bitree_width(BiTree T)
{Queue Q;initailQueue(Q);if(T!=NULL) enQueue(Q, T);int width_max=0;while(!isemptyQueue(Q)){int size=(Q.rear - Q.front + 100) % 100;   // size就是当前层的元素数if(size>width_max) width_max=size;for(int i=1;i<=size;i++){BiTNode *p=NULL;deQueue(Q, &p);if(p->lchild!=NULL) enQueue(Q,p->lchild);if(p->rchild!=NULL) enQueue(Q,p->rchild);}}return width_max;
}