目录
Data structure advanced training course notes and algorithm exercises 数据结构进阶实训课程笔记和算法练习
Source Code: https://github.com/MysticalGuest/DataStructure/tree/master/AdvancedJuniorTraining
题目1
判断二叉树是否为正则二叉树。
- 正则二叉树的定义：指在二叉树中不存在度为1的分支点。
1.1 算法设计思想
利用二叉树遍历递归的思想；
先判断当前节点是否正则；
然后递归判断该节点的左右子树。
1.2 源代码
// 1代表是正则二叉树，0代表不是
int IsRegular(BiTree T){
if(T==NULL)
return 1;
else if(T->LChild==NULL ^ T->RChild==NULL)
return 0;
else{
IsRegular(T->LChild);
IsRegular(T->RChild);
}
}
1.3 运行情况截图
题目2
判断二叉树是否为完全二叉树？
2.1 算法设计思想
一个树是否为完全二叉树，每个节点有以下4中情况：
情况一： 情况二： 情况三： 情况四：
A A A A
/ \ / \ / \ / \
B C B NULL NULL B NULL NULL
规律是：
（1）如果当前访问的节点的左右孩子是情况三，说明不是完全二叉树，直接返回false；
（2）如果当前访问的节点的左右孩子是情况1，继续访问其他节点；
（3）如果当前访问的节点的左右孩子是情况2或者情况4，那么我们定义一个状态（接下来访问的所有节点必须全部是叶子节点）。只要遇到情况2或者情况4，这个状态就开启了。
算法就是层次遍历所有节点并做判断。
2.2 源代码
BOOL IsCBT(BiTree bt){
if(bt==NULL) // 空树
return TRUE;
BOOL leaf = FALSE;
SeqQueue Q;
BiTree p;
InitQueue(&Q);
EnterQueue(&Q, bt);
while(!IsEmpty(Q)){
DeleteQueue(&Q, &p);
if(p->LChild==NULL && p->RChild!=NULL) // 情况3: 当前节点有右孩子，没有左孩子
return FALSE;
//上述的状态已经发生，但是当前访问到的节点不是叶节点（有左孩子或者右孩子）
if(leaf && (p->LChild!=NULL||p->RChild!=NULL))
return FALSE;
if(p->LChild!=NULL) //左孩子不为空，加入到队列中去
EnterQueue(&Q, p->LChild);
if(p->RChild!=NULL) //右孩子不为空，加入到队列中去
EnterQueue(&Q, p->RChild);
//这个if语句就是判断状态是否要发生
if((p->LChild!=NULL && p->RChild==NULL)||(p->LChild==NULL && p->RChild==NULL))
leaf=TRUE;
}
return TRUE;
}
2.3 运行情况截图
题目3
二叉树二叉链表存储，结点数据域的值为整数，且取值各不相同。
编写代码判断该二叉树是否为二叉排序树。
二叉排序树，又称二叉查找树。它或者是一颗空树，或者是具有下列性质的二叉树。
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的的左、右子树也分别为二叉排序树。
3.1 算法设计思想
由于二叉排序树的中序遍历得到的是一个单调递增的序列；
所以根据这个想法，我们可以中序遍历这个二叉树，将得到的序列存入temp数组；
通过检验temp数组的单调递增性来判断这个二叉树是否为二叉排序树。
3.2 源代码
#define N 100
int temp[N];
int i = 0;
void inorder(BiTree root){
if(root == NULL)
return;
if(root->LChild != NULL)
inorder(root->LChild);
temp[i++] = root->data;
if(root->RChild != NULL)
inorder(root->RChild);
}
int ISBST(int temp[], int k){
int flag=0;
for(int i=1; i<k; i++)
if(temp[i]<temp[i-1])
return 0;
return 1;
}
3.3 运行情况截图
题目4
二叉树二叉链表存储，结点数据域的值为整数，且取值各不相同。
编写代码判断该二叉排序树是否为平衡二叉排序树。
- 平衡二叉树，是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。
4.1 算法设计思想
通过平衡二叉树的定义可以将判断平衡二叉树的条件分为以下2个：
（1）首先是一颗二叉排序树；
（2）每个节点的左右子树的高度差至多为1；
基于以上两个条件写两个方法；
第一个条件思想和上一题一样，判断二叉排序树；
第二个条件通过递归判断每个节点的左右子树高度；
将两个条件返回值综合，就可以判断出。
4.2 源代码
int Deep(BiTree bt){
int ld=0,rd=0;
if(bt){
ld=Deep(bt->LChild)+1;
rd=Deep(bt->RChild)+1;
}
return ld >= rd?ld:rd;
}
BiTree pre=NULL;
BOOL ISAVL(BiTree root){
int lcd=0,rcd=0;
if(root!=NULL){
int l = ISAVL(root->LChild);
// printf("pre: %d\n", pre->data);
lcd=Deep(root->LChild); // 左子树的深度
rcd=Deep(root->RChild); // 右子树的深度
// printf("Deep(root->LChild): %d\n", Deep(root->LChild));
// printf("Deep(root->RChild): %d\n", Deep(root->RChild));
// printf("root: %d\n", root->data);
if(abs(lcd-rcd)>1){ // 条件1:每一个节点的左子树和右子树的高度差至多等于1
return FALSE;
}
if(pre!=NULL){
if(pre->data > root->data){ // 条件2:中序遍历的前驱节点大于后面节点的值,就不是平衡二叉树
return FALSE;
}
}
pre=root;
int r = ISAVL(root->RChild);
return l && r;
}
return TRUE;
}
4.3 运行情况截图
题目5
编写代码完成：输入一棵二叉树，输出它的镜像。
5.1 算法设计思想
利用二叉树遍历递归的思想；
先交换左右子树；
然后分别镜像左右子树。
5.2 源代码
void swap(BiTree *node1, BiTree *node2){
BiTree temp;
temp = *node1;
*node1=*node2;
*node2=temp;
}
void Mirror(BiTree *bt){
if((*bt)==NULL)
return;
swap(&((*bt)->LChild), &((*bt)->RChild));
Mirror(&((*bt)->LChild));
Mirror(&((*bt)->RChild));
}
5.3 运行情况截图
题目6
输入：一个整数和一棵二叉树（树中结点的数据值为int）；
输出：二叉树中结点值的和为输入的的整数的所有路径。
路径的定义：从树的根结点开始往下一直到叶子结点形成的，称为一条路径。
6.1 算法设计思想
用先序遍历的方式访问节点，使用栈数组ResultStack存储满足条件的路径，使用栈SeqStack存储当前路径节点。
遍历二叉树的过程：按先序遍历顺序访问每一个节点，访问每个结点时，将结点添加到SeqStack中。
如果当前结点是叶子结点，则判断当前路径是否是符合条件的路径，符合条件的路径存入到栈数组ResultStack；
如果当前结点不是叶子结点，则递归当前节点的左右子节点。
6.2 源代码
SeqStack ResultStack[10];
int i=0;
void SumPath(BiTree bt, SeqStack *S, int value){
BiTree p;
Push(S, bt);
if(bt){
if(!bt->LChild && !bt->LChild){
if(value == bt->data){
ResultStack[i] = *S;
i++;
}
}
else{
SumPath(bt->LChild, S, value-bt->data);
SumPath(bt->RChild, S, value-bt->data);
}
if(!IsEmpty(*S))
Pop(S, &p);
}
}
6.3 运行情况截图
题目7
输入：一个整数数组，判断该数组是否为某二叉排序树的后序遍历序列；
输出：若是，则返回true，若不是，则返回false；
假设该数组中的任何两个数值都互不相同。
7.1 算法设计思想
后续遍历中，最后一个数字是根结点，将数组中的数字分为两部分：
第一部分是左子树的值，它的值都比根结点小；
另一部分是右子树的值，它的值都比根结点大；
后续遍历（5,7,6,9,11,10,8）的最后一个结点是8，所以在这个数组中，5,7,6都比8小时该数的左子树；而9,11,10都比8大，是该树的右子树。
我们以同样的方法来分析其左子树和右子树5,7,6，其中6将左子树分为5和7两部分；10将右子树9和11分为两部分。所以这个序列就是一个后续遍历序列。但是（7,4,5,6）就不是它的一个后续遍历序列。因为6大于7，所以也就是说7,4,5都是其右子树，但是很不幸还有4比6小，所以不可能是一个后续遍历。
7.2 源代码
BOOL VerifySequenceOfBST(int *array,int length){
if(array==NULL || length<=0)
return FALSE;
int root=array[length-1];
int i=0; //左子树的结点小于根节点；
for(;i<length-1;i++){
if(array[i]>root)
break; //找完了全部的左子树的序列；
}
int j=i;//右子树的结点大于根结点；
for(;j<length-1;j++){
if(array[j]<root)
return FALSE;
}
BOOL left=TRUE;
if(i>0)
left=VerifySequenceOfBST(array,i);
BOOL right=TRUE;
if(j<length-1)
right=VerifySequenceOfBST(array+i,length-i-1);
return left && right;
}
7.3 运行情况截图
京公网安备 11010502036488号