二叉树及孩子兄弟二叉树的部分习题

2023-07-01 0 771

结构体：

为了使用方便，这里使用三叉线索树结构体代替普通二叉树

//三叉线索二叉树的定义
typedef struct TTNode{
    int data;
    int ltag,rtag;
    int weight;//权重 
    struct TTNode *lchild,*rchild,*parent;
}TTNode,*ThreadTree;

孩子兄弟二叉树结构体定义

//树的孩子兄弟二叉树的定义
typedef struct CSTreeNode{
	int data;
	struct CSTreeNode *firstchild,*nextsibling;
}CSTreeNode,*CSTree;

习题：

////二叉树的创建
ThreadTree createTree(){
	int data;
	scanf("%d",&data);
	if(data!=-1){
		ThreadTree t = (TTNode*)malloc(sizeof(TTNode));
		t->data = data;
		t->lchild = createTree();
		if(t->lchild){
			t->lchild->parent = t;
			t->ltag = 0;
		} 
		t->rchild = createTree();
		if(t->rchild){
			t->rchild->parent = t;
			t->rtag = 0;
		}
		return t;
	}else{
		return NULL;
	}
}

////二叉树的遍历 
///递归版本
//前序遍历
void preOrder(ThreadTree t){
	if(t){
		printf("%d ",t->data);
		preOrder(t->lchild);
		preOrder(t->rchild);
	}
}

//中序遍历
void inOrder(ThreadTree t){
	if(t){
		inOrder(t->lchild);
		printf("%d ",t->data);
		inOrder(t->rchild);
	}
} 

//后序遍历
void postOrder(ThreadTree t){
	if(t){
		printf("%d",t->data);
		postOrder(t->lchild);
		postOrder(t->rchild);
	}
} 

///非递归版本
//前序遍历 
void preOrderN(ThreadTree t){
	ThreadTree stack[MAXSIZE],p=t;int top = -1;
	while(p || top!=-1){
		if(p){
			printf("%d",p->data);
			stack[++top] = p;
			p = p->lchild;
		}else{
			p = stack[top--];
			p = p->rchild;
		}
	}
} 
//中序遍历
void inOrderN(ThreadTree t){
	ThreadTree stack[MAXSIZE],p=t;
	int top = -1;
	while(p || top!=-1){
		if(p){
			stack[++top]=p;
			p = p->lchild;
		}else{
			p = stack[top--];
			printf("%d",p->data);
			p = p->rchild;
		}
	}
} 

//后序遍历
void postOrderN(ThreadTree t){
	ThreadTree stack[MAXSIZE],p=t;
	int top=-1,tag[MAXSIZE] = {0};
	while(p || top!=-1){
		if(p){
			stack[++top] = p;
			p = p->lchild;
			tag[top] = 1;
		}else{
			p = stack[top];
			if(tag[top]==1){
				tag[top] = 2;
				p = p->rchild;
			}else{
				printf("%d",p->data);
				top--; //别掉了 
				p = NULL;
			}
		}
	}
}

//层序遍历
void levelOrder(ThreadTree t){
	ThreadTree Queue[MAXSIZE],p=t;
	int rear = -1,front = -1;
	Queue[++rear] = p;
	while(rear!=front){
		p = Queue[++front];
		printf("%d",p->data);
		if(p->lchild){
			Queue[++rear] = p->lchild; 
		}
		if(p->rchild){
			Queue[++rear] = p->rchild;
		}
	}
}

//1.给出二叉树自下而上，自右到左的层次遍历算法
//思路：利用栈后进先出的特点，层次遍历整棵树依次压入栈内，再将元素弹出栈
void printTreeByStack(ThreadTree t){
	ThreadTree Queue[MAXSIZE],Stack[MAXSIZE],p=t;
	int rear = -1,front = -1,top = -1;
	Queue[++rear] = p;
	while(rear!=front){
		p = Queue[++front];
		Stack[++top] = p;
		if(p->lchild){
			Queue[++rear] = p->lchild;
		}
		if(p->rchild){
			Queue[++rear] = p->rchild;
		}
	}
	while(top!=-1){
		p = Stack[top--];
		printf("%d",p->data);
	}
	 
}

//2.递归算法求解二叉树的高度
int getHeight(ThreadTree t){
	if(t){
	  	return getHeight(t->lchild) > getHeight(t->rchild)?getHeight(t->lchild)+1:getHeight(t->rchild)+1;
	}else{
		return 0;
	}
}

//3.非递归方法求解树的高度
//思路：利用后序非递归遍历整颗二叉树，栈内元素弹出时判断是否是叶子节点，
//是的话栈的元素个数+1就是高度，且每次到叶子节点需要取高度的最大值 
int getHeightN(ThreadTree t){
	ThreadTree Stack[MAXSIZE],p=t;
	int top = -1,height = -1,tag[MAXSIZE] = {0};
	while(p || top!=1){
		if(p){
			Stack[++top] = p;
			p = p->lchild;
			tag[top] = 1;
		}else{
			p = Stack[top];
			if(tag[top]==1){
				tag[top] = 2;
				p = p->rchild;
			}else{
				if(!p->lchild && !p->rchild){
					//为什么是top+1,请思考思考
					//答案:top数组的元素下标默认是从0开始的，此时栈内元素的个数应该是top+1 
					if(top+1>height)height=top+1;
				} 
				top--;
				p = NULL;
			}
		}
	}
	return height;
}

//4.求解树的结点所在的层
//思路:后序非递归方法，找到节点的时候返回栈长就是层高 
int getLevel(ThreadTree t,int e){
	ThreadTree Stack[MAXSIZE],p=t;
	int top = -1,height = -1,tag[MAXSIZE] = {0};
	while(p || top!=1){
		if(p){
			Stack[++top] = p;
			p = p->lchild;
			tag[top] = 1;
		}else{
			p = Stack[top];
			if(tag[top]==1){
				tag[top] = 2;
				p = p->rchild;
			}else{
				if(p->data == e){
					return top+1;
				} 
				top--;
				p = NULL;
			}
		}
	}
	return height;
}

//5.用递归方法求解树的结点所在的层
void getLevelByD(ThreadTree t,int e,int &h,int deep){
	if(t){
		if(t->data == e)h=deep+1;
		getLevelByD(t->lchild,e,h,deep+1);
		getLevelByD(t->rchild,e,h,deep+1);
	}
}

//6.使用递归方法求解树的高度（深度）
void getTreeHeight(ThreadTree t,int &h,int deep){
	if(t){
		if(!t->lchild&&!t->rchild){
			if(deep+1>h)h=deep+1;
		}
		getTreeHeight(t->lchild,h,deep+1);
		getTreeHeight(t->rchild,h,deep+1);
	}
}

//7.使用层序遍历求解树的高度
int getHeightByLeverOrder(ThreadTree t){
	ThreadTree Queue[MAXSIZE],p=t;
	int rear=-1,front=-1,deep=0,height=0;
	Queue[++rear] = p;
	while(rear!=front){
		p = Queue[++front];
		if(p->lchild){
			Queue[++rear] = p->lchild;
		}
		if(p->rchild){
			Queue[++rear] = p->rchild;
		}
		if(front = deep){
			deep = rear;
			height++;
		}
	}
	return height;
}

//8.求解树的宽度 （最大宽度）
int getTreeMaxWidth(ThreadTree t){
	ThreadTree Queue[MAXSIZE],p=t;
	int rear = -1,front = -1,deep = 0,maxwidth = -1;
	Queue[++rear] = p;
	while(rear!=front){
		p = Queue[++front];
		if(p->lchild){
			Queue[++rear] = p->lchild;
		}
		if(p->rchild){
			Queue[++rear] = p->rchild;
		}
		if(deep == front){
		  deep = rear;
		  if(rear-front > maxwidth)maxwidth = rear - front;
	    }
	}
	return maxwidth;
}

////难点题目 
//9.判断一棵树是否是一颗完全二叉树
bool isATBTree(ThreadTree t){
	ThreadTree Queue[MAXSIZE],p=t;
	int rear = -1,front = -1,deep = 0;
	Queue[++rear] = p;
	while(rear!=front){
		p = Queue[++front];
		//队内有元素 
		if(p){
			//入队，无论有无元素均入队 
			Queue[++rear] = p->lchild;
			Queue[++rear] = p->rchild; 
		}else{
			//完全二叉树的性质，若队列有节点为空，则该节点所在的层剩余节点应均为空 
			while(rear!=front){
				p = Queue[++front];
				if(p)return false;
			}
		} 
	}
	return true;
}

//10.计算二叉树的所有
//10.1双分支节点个数
void getTwoChildNode(ThreadTree t,int &node){
	if(t){
		if(t->lchild && t->rchild)node++;
		getTwoChildNode(t->lchild,node);
		getTwoChildNode(t->rchild,node);
	}
}
//10.2单分支节点个数
void getOneChildNode(ThreadTree t,int &node){
	if(t){
		if((t->lchild&&!t->rchild) || (t->rchild&&!t->lchild))node++;
		getOneChildNode(t->lchild,node);
		getOneChildNode(t->rchild,node);
	}
}

//10.3叶子节点个数
void getNoneChildNode(ThreadTree t,int &node){
	if(t){
		if(!t->lchild&&!t->rchild)node++;
		getNoneChildNode(t->lchild,node);
		getNoneChildNode(t->rchild,node);
	}
}

//11.递归返回方法求解树的双节点数
int getTreeTwoChildNode(ThreadTree t){
	if(t){
		if(t->lchild && t->rchild){
			return 1 + getTreeTwoChildNode(t->lchild) + getTreeTwoChildNode(t->rchild);
		}else{
			return getTreeTwoChildNode(t->lchild) + getTreeTwoChildNode(t->rchild);
		}
	}else{
		return 0;
	}
}

//12.使用非递归方法交换左右子树
void swithLRCTreeN(ThreadTree &t){
	ThreadTree Queue[MAXSIZE],p=t,temp;
	int rear = -1,front = -1;
	Queue[++rear] = p;
	while(rear!=front){
		p = Queue[++front];
		//交换 
		temp = p->lchild;
		p->lchild = p->rchild;
		p->rchild = temp;
		if(p->lchild)Queue[++rear] = p->lchild;
		if(p->rchild)Queue[++rear] = p->rchild;
	}
}

//13. 使用递归方法交换左右子树
void switchLRCTree(ThreadTree &t){
	if(t){
		ThreadTree temp = t->lchild;
		t->lchild = t->rchild;
		t->rchild = temp;
		if(t->lchild)switchLRCTree(t->lchild);
		if(t->rchild)switchLRCTree(t->rchild);
	}
}

//14.1先序遍历序列中第k个节点的值
//递归方式 seq初始化取0，k为查找的结点，e存储找到的元素 
void getPreOrderK(ThreadTree t,int &seq,int k,int &e){
	if(t){
		seq++;
		if(seq == k)e = t->data;
		getPreOrderK(t->lchild,seq,k,e);
		getPreOrderK(t->rchild,seq,k,e);
	}
} 

//非递归
int getPreOrderKN(ThreadTree t,int k){
	ThreadTree stack[MAXSIZE],p=t;
	int top = -1,c = 0;
	while(p || top!=-1){
		if(p){
			//思考这里是k-1还是k
			//k从0开始还是从1开始？ 
			if(c == k-1)return p->data;
			c++;
			stack[++top] = p;
			p = p->lchild;
		}else{
			p = stack[top--];
			p = p->rchild;
		}
	}
	return -1;
}

//14.2中序遍历序列中第k个节点的值
//递归方式 seq初始化取0，k为查找的结点，e存储找到的元素 
void getInOrderK(ThreadTree t,int &seq,int k,int &e){
	if(t){
		getInOrderK(t->lchild,seq,k,e);
		seq++;
		if(seq == k)e = t->data;
		getInOrderK(t->rchild,seq,k,e);
	}
} 

//非递归
int getInOrderKN(ThreadTree t,int k){
	ThreadTree stack[MAXSIZE],p=t;
	int top = -1,c = 0;
	while(p || top!=-1){
		if(p){
			stack[++top] = p;
			p = p->lchild;
		}else{
			p = stack[top--];
			//思考这里是k-1还是k
			//k从0开始还是从1开始？ 
			if(c == k-1)return p->data;
			c++;
			p = p->rchild;
		}
	}
	return -1;
}

//14.3后序遍历序列中第k个节点的值
//递归方式 seq初始化取0，k为查找的结点，e存储找到的元素 
void getPostOrderK(ThreadTree t,int &seq,int k,int &e){
	if(t){
		getPostOrderK(t->lchild,seq,k,e);
		getPostOrderK(t->rchild,seq,k,e);
		seq++;
		if(seq == k)e = t->data;
	}
} 
//非递归 
int getPostOrderKN(ThreadTree t,int k){
	ThreadTree stack[MAXSIZE],p=t;
	int top = -1,c = 0,tag[MAXSIZE] = {0};
	while(p || top!=-1){
		if(p){
			stack[++top] = p;
			tag[top] = 1;
			p = p->lchild;
		}else{
			p = stack[top];
		    if(tag[top]==1){
		    	tag[top] = 2;
		    	p = p->rchild;
			}else{
				if(c == k-1)return p->data;
				c++;
				top--;
				p = NULL;
			}
		}
	}
	return -1;
}

//14.4层次遍历序列中第k个节点的值
int getlevelOrderK(ThreadTree t,int k){
	ThreadTree Queue[MAXSIZE],p=t;
	int rear = -1,front = -1,c = 0;
	Queue[++rear] = p;
	while(rear!=front){
		p = Queue[++front];
		if(c == k-1)return p->data;
		c++;
		if(p->lchild){
			Queue[++rear] = p->lchild; 
		}
		if(p->rchild){
			Queue[++rear] = p->rchild;
		}
	}
	return -1;
}

//15.删除树中每个元素值为x的节点，并删除以它为根的子树
//子树删除函数
void deleteCTree(ThreadTree &t){
	if(t){
		deleteCTree(t->lchild);
		deleteCTree(t->rchild);
		free(t);
	}
} 
//寻找值为x的函数
void findXAndDelete(ThreadTree &t,int x){
	ThreadTree Queue[MAXSIZE],p=t;
	int rear = -1,front = -1;
	Queue[++rear] = p;
	while(rear!=front){
		p = Queue[++front];
		//注意删除条件
		if(p->lchild && p->lchild->data == x){
			deleteCTree(t->lchild);
			t->lchild = NULL;
		} 
		if(p->rchild && p->rchild->data == x){
			deleteCTree(t->rchild);
			t->rchild = NULL;
		}
		if(p->lchild){
			Queue[++rear] = p->lchild;
		}
		if(p->rchild){
			Queue[++rear] = p->rchild;
		}
	}
}

//16.打印节点x的所有的祖先
void printAllParentNode(ThreadTree t,int x){
	ThreadTree stack[MAXSIZE],p = t;
	int top = -1,tag[MAXSIZE] = {0};
	while(t || top!=-1){
		if(t){
			stack[++top] = t;
			tag[top] = 1;
			t = t->lchild;
		}else{
			p = stack[top];
			if(tag[top] == 1){
				tag[top] = 2;
				p = p->rchild;
			}else{
				if(p->data == x){
					int i = top; 
					while(i!=-1){
						//父节点就是栈内的剩余元素 
						printf("%d",stack[i--]->data);
					}
				}
				top--;
				p = NULL;
			}
		}
	}
}

//17.打印从根节点到某个节点的路径
void printXPath(ThreadTree t,int x){
	ThreadTree stack[MAXSIZE],p = t;
	int top = -1,tag[MAXSIZE] = {0};
	while(t || top!=-1){
		if(t){
			stack[++top] = t;
			tag[top] = 1;
			t = t->lchild;
		}else{
			p = stack[top];
			if(tag[top] == 1){
				tag[top] = 2;
				p = p->rchild;
			}else{
				if(p->data == x){
					int i = top; 
					while(i!=-1){
						//父节点就是栈内的剩余元素,相当于一条路径到根节点
						printf("%d ",p->data); 
						printf("%d ",stack[i--]->data);
					}
				}
				top--;
				p = NULL;
			}
		}
	}
}

//18.求从根节点到某个节点的路径长度及序列 （最大） 
//用17题的例子，做一个栈保存当前长度
//每次遇到这个节点比较路径长度并保存最长的值和序列 
int printAllParentNodes(ThreadTree t,int x){
	ThreadTree stack[MAXSIZE],maxseq[MAXSIZE],p = t;
	int top = -1,mtop = -1,tag[MAXSIZE] = {0},length = -1;
	
	while(t || top!=-1){
		if(t){
			stack[++top] = t;
			tag[top] = 1;
			t = t->lchild;
		}else{
			p = stack[top];
			if(tag[top] == 1){
				tag[top] = 2;
				p = p->rchild;
			}else{
				if(p->data == x){
					if(top+1 > length){
						length = top + 1;
						maxseq[++mtop] = p;
						int i = top;
						while(i!=-1){
							maxseq[++mtop] = stack[i--]; 
						} 
					}
				}
				top--;
				p = NULL;
			}
		}
	}
	//遍历结束，打印
	while(mtop!=-1){
		printf("%d",maxseq[mtop--]->data);
	} 
	return length;
}

//19.根节点到某个节点最大路径深度
int printRoutine(ThreadTree t,int x){
	ThreadTree Stack[MAXSIZE],p = t;
	int top=-1,tag[MAXSIZE]={0},maxdeep=-1;
	while(p || top!=-1){
		if(p){
			Stack[++top]=p;
			tag[top]=1;
			p = p->lchild;
		}else{
			p = Stack[top];
			if(tag[top]==1){
				tag[top]=2;
				p = p->rchild;
			}else{
				if(p->data = x){
					if(top+1>maxdeep) maxdeep=top+1;
				}
				top--;
				p = NULL;
			}
		}
	}
	return maxdeep;
}

//难点:20.求两个结点的最近公共祖先
ThreadTree printNearParent(ThreadTree t,int x,int y){
	ThreadTree stack[MAXSIZE],p = t,astack[MAXSIZE],bstack[MAXSIZE];
	int top=-1,atop=-1,btop=-1,tag[MAXSIZE]={0};
	while(p || top!=-1){
		if(p){
			stack[++top]=p;
			tag[top]=1;
			p = p->lchild;
		}else{
			p = stack[top];
			if(tag[top]==1){
				tag[top]=2;
				p = p->rchild;
			}else{
				if(p->data == x){
					for(int i=0;i<=top;i++){
						astack[++top] = stack[i];
					}
				}
				if(p->data == y){
					for(int i=0;i<=top;i++){
						bstack[++top] = stack[i];
					}
				}
				top--;
				p = NULL;
			}
		}
	}
	//修剪长度,方便判断 
	if(atop>btop){
		while(atop!=btop){
			atop--;
		}
	}else{
		while(btop!=atop){
			btop--;
		}
	}
	while(astack[atop--] != bstack[btop--]);
	//不可能找不到祖先的，不然构成不了二叉树
	return astack[atop];
}

//21.判断u是否为v的后代 v是为u的祖先
bool uIsVChild(ThreadTree t,ThreadTree u,ThreadTree v){
	ThreadTree Stack[MAXSIZE],p = t;
	int top=-1,tag[MAXSIZE]={0};
	while(p || top!=-1){
		if(p){
			Stack[++top]=p;
			tag[top]=1;
			p = p->lchild;
		}else{
			p = Stack[top];
			if(tag[top]==1){
				tag[top]=2;
				p = p->rchild;
			}else{
				if(p==u){
					int i = top;
					while(top!=-1){
						if(Stack[top--]==v)return true;
					}
				}
				top--;
				p = NULL;
			}
		}
	}
	return false;
}

//22.1判断两颗二叉树是否相等 
bool isEqualTree(ThreadTree a,ThreadTree b){
	if(!a || !b)return false;
	else if(a->data!=b->data)return false;
	else if(!a && !b)return true;
	else return isEqualTree(a->lchild,b->lchild) && isEqualTree(a->rchild,b->rchild);
}

//22.忘记。判断两颗二叉树是否相似
bool isLikeTree(ThreadTree a,ThreadTree b){
	if(!a || !b)return false;
	else if(!a && !b)return true;
	else return isLikeTree(a->lchild,b->lchild) && isLikeTree(a->rchild,b->rchild);
	
}

//23.将叶子节点串成一个单链表，用叶子节点的rchild，作next
void linkLNode(ThreadTree &t,ThreadTree pre){
	if(t){
		if(!t->lchild && !t->rchild){
			if(!pre){
				pre = t;
			}else{
				t->rchild = pre;
				pre = t;
			}
		}
		linkLNode(t->lchild,t);
	    linkLNode(t->rchild,t);
	}
}

//24.带权结点路径计算
int computeWPL(ThreadTree t,int &wpl,int &height){
	if(t){
	    wpl +=(height-1)*t->weight;
	    height++;
	    computeWPL(t->lchild,wpl,height);
	    computeWPL(t->rchild,wpl,height);
	
	} 
}

//25.在中序线索二叉树中查找指定节点在后序里面的前驱
ThreadTree findPreNodeInInorderseq(ThreadTree x){
	if(x->rtag == 0)return x->rchild;
	else if(x->ltag == 0)return x->lchild;
	else{
		while(x->lchild && x->ltag == 1)x=x->lchild;
		//思考这里是否是x->lchild? 
		if(x->ltag==0)return x;
		return NULL;
	}
}

//26.(难点)中缀表达式树加括号
void addBracket(ThreadTree &t,int deep){
	if(!t)return;
	else if(!t->lchild && !t->rchild){
		printf("%d",t->data);
	}else{
		if(deep>1)printf("(");
		deep++;
		addBracket(t->lchild,deep);
		printf("%d",t->data);
		deep++; 
		addBracket(t->rchild,deep);
		if(deep>1)printf(")");
	}
}

//27.(难点)表达式树的计算
int calculateTree(ThreadTree t){
	if(!t)return 0;
	if(!t->lchild && !t->rchild)return t->data;
	else if(t->lchild && t->rchild){
		int lvalue = calculateTree(t->lchild);
		int rvalue = calculateTree(t->rchild);
		if(t->data == '+'){
			return lvalue + rvalue;
		}else{
			return lvalue - rvalue;
		}
	}

}

//28.(难点)求以孩子兄弟表示法存储的森林的叶子节点数
int getCSTreeLNode(CSTree t,int count){
	if(t){
		//没有孩子的节点就是叶节点 
		if(!t->firstchild){
			count++;
		}
		getCSTreeLNode(t->firstchild,count);
		getCSTreeLNode(t->nextsibling,count);
	}
} 
//第二种方法，返回取值
int getleavesbyreturn(CSTree t){
	//无节点 
	if(!t)return 0;
	//是叶子节点 
	if(!t->firstchild)return 1+getleavesbyreturn(t->nextsibing);
	//持续遍历 
	else{
		return getleavesbyreturn(t->firstchild)+getleavesbyreturn(t->nextsibing);
	}
}

//29.孩子兄弟表示法，表示的存储结构，求树的高度
int getCSTreeHeight(CSTree t){
  if(!t)return 0;
  int left = getCSTreeHeight(t->firstchild);
  int right = getCSTreeHeight(t->nextsibling);
  return left>=right?left+1:right+1;
}

收藏 (0) 打赏

感谢您的支持，我会继续努力的!

打开微信扫一扫，即可进行扫码打赏哦，分享从这里开始，精彩与您同在

本站部分资源收集自互联网，我站仅分享内容，仅供用户个人研究，不提供商业使用，如有侵权下架处理，觉得资源内容不错请您在官方渠道购买正版，您在阅读的同时下载的内容本站不承担任何法律责任！Some resources of this website are collected from the Internet. We only share the content, which is only for personal research of users, and not for commercial use. If there is infringement and off shelf processing, please purchase the authentic version of the resource content from the official channel if you think it is good. We will not bear any legal responsibility for the content you download while reading!

橙凰素材-精品源码下载|正版主题更新学习交流二叉树及孩子兄弟二叉树的部分习题 https://b.bqzmz.com/2023/07/01/%e4%ba%8c%e5%8f%89%e6%a0%91%e5%8f%8a%e5%ad%a9%e5%ad%90%e5%85%84%e5%bc%9f%e4%ba%8c%e5%8f%89%e6%a0%91%e7%9a%84%e9%83%a8%e5%88%86%e4%b9%a0%e9%a2%98/