当前位置:   article > 正文

二叉树题集

二叉树题集

王道数据结构

二叉树遍历

//先序遍历
void preOrder(BiTree T){
	if(T!=NULL){
		visit(T);
		preOrder(T->lchild);
		preOrder(T->rchild);
	}
}

void PreOrder(BiTree T){
	InitStack(s);
	BiTree p=T;
		while(p || !isEmpty(s)){
		if(p){
			visit(p);//先序
			push(s,p);
			p=p->lchild;
		}
		else{
			pop(s,p);
			p=p->rchild;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
//中序遍历
void inOrder(BiTree T){
	if(T!=NULL){
		inOrder(T->lchild);
		visit(T);
		inOrder(T->rchild);
	}
}

void InOrder(BiTree T){
	InitStack(S);
	BiTree p=T;
	while(p || isEmpty(s)){
		if(p){
			push(s,p);
			p=p->lchild;
		}
		else{
			pop(s,p);
			visit(p);//中序
			p=p->rchild;
	}
	
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
//后序遍历
void postOrder(BiTree T){
	if(T!=NULL){
		postOrder(T->lchild);
		postOrder(T->rchild);
		visit(T);
	}
}

void PostOrder(BiTree T){
	InitStack(S);
	BiTree p=T
	r=NULL;
	while(p || !isEmpty(S)){
		if(p){
			push(S,p);
			p=p->lchild;	
		}
		else{
			getTop(S,p);
			if(p->rchild && p->rchild!=r){
				p=p->rchild;
				push(S,p);
				p=p->lchild;
			}
			else{
				pop(S,p);
				visit(p->data);//后序
				r=p;
				p=NULL;
			}
		}
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
//层次遍历
void level(BiTree T){
	InitQueue(Q);
	BiTree p;
	EnQueue(Q,T);
	while(!isEmpty(Q)){
		DeQueue(Q,p);
		visit(p);
		if(p->lchild){
			EnQueue(Q,p->lchild);	
		}
		if(p->rchild){
			EnQueue(Q,p->rchild);	
		}
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

线索二叉树

//存储结构
typedef struct ThreadNode{
	ElemType data;//数据元素
	struct ThreadNode *lchild,*rchld;//左右线索指针
	int ltag,rtag;//左右线索标志
}

//中序遍历线索化
void InThread(ThreadTree &p,ThreadTree &pre){
	if(p!=NULL){
		InTread(p->lchild);
		if(p->lchild==NULL){
			p->lchild=pre;
			p->ltag=1;
		}
		if(pre!=NULL && pre->rchild==NULL){
			pre->rchild=pre;
			pre->rtag=1;
		}
		pre=p;
		InThread(p->rchild);
}

//中序线索二叉树的遍历
ThreadNode *Firstnode(ThreadNode *p){//中序序列下第一个结点
	while(ltag=0){
		p=p->lchild;
	return p;
}
ThreadNode *NextNode(ThreadNoode *p){//中序序列结点的后继
	if(p->rtag==0FirstNode(p->rchild);
	else 	return p->rchild;
}
ThreadNode *NextNode(ThreadNoode *p){//中序二叉树最后一个结点
	
}
ThreadNode *NextNode(ThreadNoode *p){//中序序列结点p的前驱

}

//不含头结点的中序线索二叉树的中序遍历算法
void InOrder(ThreadNode *T){
	for(ThreadNode *p=Firstnode(T);p!=NULL;p=NextNode(p))
		visit(p);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46

中序遍历应用

 
  • 1
15满二叉树已知先序序列,求后序序列
16二叉树叶节点从左到右形成单链表
17判断2二叉树是否相似
18求中序线索二叉树查找指定结点在后序的前驱结点算法。
19.求带权路径长度
20转换中缀表达式
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
.删去二叉树中值为k的结点,删去以它为根的子树
  • 1
void DeleteXTree(BiTree bt){
	if(bt){
		DeleteXTree(BiTree bt)
			if(bt){
				DeleteXTree(bt->lchild);
				DeleteXTree(bt->rchild);
				free(bt);
			}
	}
}

void search(BiTree bt,int x){
	BiTree  Q[];
	if(bt){
		if(bt->data==x){
			DeleteXTree(bt);
			exit(0);
		}
		InitQueue(Q);
		EnQueue(Q,bt);
		while(!isEmpty(Q)){
			DeQueue(Q,p);
			if(p->lchild){
				if(p->lchild->data==x){
					DeleteXTree(p->lchild);
					p->lchild=NULL;
				}
				else{
					EnQueue(Q,p->lchild);
				}
			}
			if(p->lchild){
				//同理操作
			}
		}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
打印值为x的结点的所有祖先
  • 1
typedef struct{
	BiTree t;
	int tag;
}stack;//tag=0表示,左子女被访问,tag=1表示右子女被访问
void search(BiTree bt,int k){
	stack s[];
	top=0;
	while(p || s.top>0){
		while(bt!=NULL && bt->data!=k){
			s[++top].t=bt;
			s[top].tag=0;
			bt=bt->lchild;
		}
		if(bt->data==x){
			printf("所查结点的所有祖先的值为:/n");
			for(int i=0;i<=top;i++){
				printf("%d",s[i].t->data);
				exit(1);
			}
		}
		while(top!=0 && s[top].tag==1){
			top--;	
		}
		if(top!=0){
			s[top].tag=1;
			bt=s[top].t->rchild;
		}
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
最近公共祖先结点
  • 1
typedef struct{
	BiTree t;
	int tag;
}stack;//tag=0表示,左子女被访问,tag=1表示右子女被访问
void Ancestor(BiTree root,BitNode *p,BiTNode *q){
	stack s[],s1[];
	top=0;
	BitNode *bt=root;
	while(bt || s.top>0){
		while(bt!=NULL && bt!=p && bt!=q){
			while(bt!=NULL){
				s[++top].t=bt;
				s[top].tag=0;
				bt=bt->lchild;
			}
		}
		while(top!=0&&s[top].tag==1){
		if(s[top].t==p){
			for(int i=0;i<=top;i++){
				s1[i]=s[i];
				top1=top;
			}
		}
		if(s[top].t==q){
			for(i=top;i>0;i--){
				if(s1[j].t==s[i].t)
					return s[i].t
			}
			top--;
		}
		if(top!=0){
			s[top].tag=1;
			bt=s[top].t->rchild;
		}
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36

递归

二叉树左右子树交换
  • 1
//二叉树左右子树交换
void swap(BiTree T){
	if(T){
		swap(T->lchild);
		swap(T->rchild);
		temp=T->lchild;
		T->lchild=T->rchild;
		T-rchild=temp;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
双分支结点个数
  • 1
void DsonNodes(BiTree b){
if(b=NULL){
	return 0;
}
else if(b->lchild!=NULL&&b->rchild!=NULL)
{
	return DsonNodes(b->lchild)+DsonNodes(b->rchild)+1;
}
else 
	return DsonNodes(b->lchild)+DsonNodes(b->rchild);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
先序遍历序列中第k个结点的值
  • 1
int i=1;
int PreNode(BiTree b,int k){
	if(b=NULL){
		return '#';
	if(k==i){
		return b->data;
	}
	i++;
	ch=PreNode(b->lchild,k);
	if(ch!='#')
		return ch;
	ch=PreNode(b->rchild,k);
		return ch;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
满二叉树已知先序序列求后序序列
  • 1
void PreToPost(int pre[],int l1,int h1,int post[],int l2,int h2){
	int half;
	if(h1>=l1){
		post[h2]=pre[l1];
		half=(l1-l1)/2;
		PreToPost(pre,l1+1,l1+half,post,l2,l2+half-1);
		PreToPost(pre,l1+half+1,h1,l2+half,h2-1);
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
先序、中序序列唯一确定二叉树
  • 1
BiTree PreInCreat(int A[],int B[],int l1,int h1,int l2,int h2){
	root=(BiTNode*)malloc(sizeof(BiTNode));
	root->data=A[l1];
	for(i=l2;B[i]!=root->data;i++){
		llen=i-l2;//左子树结点序列
		rlen=h2-i;//右子树结点序列
		if(llen)
			root->lchild=PreInCreat(A,B,l1+1,l1+llen,l2,l2+llen-1);
		else
			root->lchild=NULL;
		if(rlen)
			root->lchild=PreInCreat(A,B,h1-rlen+1,h1,h2-rlen+1,h2);
		else 
			root->rchild=NULL;
		return root;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
判断二叉树是否相似
  • 1
int similar(BiTree T1,BiTree T2){
	int leftS,rightS;
	if(T1==NULL && T2==NULL){
		return 1;
	}
	else if(T1==NULL || T2==NULL){
		return 0;
	}
	else{
		leftS=similar(T1->lchild,T2->lchild);
		rightS=similar(T1->rchild,T2->rchild);
		return leftS && rightS;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

中序遍历应用

叶结点连成单链表(递归)
  • 1
LinkList head,pre=NULL;
LinkList inOrder(BiTree bt){
	if(bt){
		InOrder(bt->lchild);
		if(bt->lchild==NULL&&bt->rchild==NULL){
			if(pre==NULL){
				head=bt;
				pre=bt;
			}
			else{
				pre->rchild=bt;
				pre=bt;
			}
		}
		InOrder(bt->rchild);
		pre->rchild=NULL;
	}
	return head;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
中序线索二叉树查找指定结点在后序的前驱
  • 1
BiThrTree InPostPre(BiThrTree t,BiThTree p){
	BiThTree q;
	if(p->rtag==0){
		q=p->rchild;	
	}
	else if(p->ltag==0){
		q=p->lchild;
	}
	else if(p->lchild==NULL){
		q=NULL;
	}
	else{
		while(p->ltag==1&&p->rchild!=NULL){
			p=p->lchild;
		}
		if(p->ltag==0){
			q=p->lchild;
		}
		else {
			q=NULL;
		}
	}
	return q;	
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

层次遍历应用

二叉树自下而上,从左到右的层次遍历
  • 1
void level(BiTree T){
	BiTree p=T;
	InitQueue(q);
	InitStack(S);
	EnQueue(q,p);
	while(!isEmpty(q)){
		DeQueue(q,p);
		push(s,p);
		if(p->lchild){
			EnQueue(q,p->lchild);	
		}
		else(p->rchild){
			EnQueue(p->rchild);
		}
	}
	while(!isEmpty(s)){
		pop(s,p);
		visit(p->data);
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
非递归求二叉树高度
  • 1
void levelhigh(BiTree T){
	BiTree Q[MAXSIZE];
	BiTree p=T;
	int rear=-1;front=-1;
	int last=0;level=0;
	Q[++rear]=p;
	while(front<rear){
		p=Q[front++];
		if(p->lchild){
			Q[++rear]=p->lchild;
		}
		else{
			Q[++rear]=p->rchild;
		}
		if(front==last){
			level++;
			last=rear;
		}
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
二叉树按二叉链表存储,判别给定二叉树是否是完全二叉树
  • 1
void isComplete(BiTree T){
	InitQueue(Q);
	if(!T){
		return 1;
	}
	EnQueue(Q,T);
	BiTree p=T;
	while(!isEmpty(Q)){
		DeQueue(Q,p);
		if(p){
			//这里判断左右子树是否存在并且入队
		}
		else
			while(!isEmpty(Q)){
				DeQueue(Q,p);
				if(p)	return 0;
				else 	return 1;
			}	
		}
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
非空二叉树b的宽度
  • 1
typedef struct{
	BiTree data[MaxSize];
	int level[MaxSize];
	int front,rear;
}Qu;
int BTWidth(BiTree T){
	BiTree p;
	int max,k,i,n;//最大宽度/层数/遍历每层多少个元素的变量/每层的元素个数
	Qu.rear=-1;
	Qu.front=-1;
	Qu.data[++Qu.rear]=T;//元素入队
	Qu.level[Qu.rear]=1;
	while(Qu.front<Qu.rear){
		p=Qu.data[++Qu.front];
		k=Qu.level[++Qu.front];
		if(p->lchild){
			Qu.data[++Qu.rear]=p->lchild;
			Qu.level[++Qu.rear]=k+1;	
		}
		if(p->rchild){
			Qu.data[++Qu.rear]=p->rchild;
			Qu.level[++Qu.rear]=k+1;	
		}
	}
	max=0;i=0;
	while(i<=Qu.rear){
		n=0;
		while(i<Qu.rear&&Qu.level[i]==k){
			n++;
			i++
		}
		k=Qu.level[i];下一层第一个结点的level
		if(n>max)	max=n;
	}
	return max;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
计算带权路径长度(2015)
  • 1
#define MaxSize 100;
int wpl_levelOrder(BiTree root){
	BiTree q[MaxSize];
	int end1=0,end2=0;
	int wpl=0,deep=0;
	BiTree lastNode,newlastNode;
	lastNode=root;
	newlastNode=NULL;
	q[end2++]=root;
	while(end1!=end2){
		BiTree t=q[end1++];
		if(t->lchild==NULL && t->rchild==NULL){
			wpl+=deep*t->weight;
		}
		if(t->lchild!=NULL){
			q[end2++]=t->lchild;
			newlastNode=t->lchild;
		}
		if(t->rchild!=NULL){
			//同理
		}
		if(t==lastNode){
			lastNode=newlastNode;
			deep+=1;
		}
	}
	return wpl;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

先序遍历应用

计算带权路径长度
  • 1
typedef struct BitNode{
	int weight;
	struct BiTNode *lchild,*rchild;
}BitNode,*BiTree;
int WPL(BiTree root){
	return wpl_PreOrder(root,0);
}
int wpl_PreOrder(BiTree root,int deep){
	static int wpl=0;
	if(root->lchild==NULL && root->lchild==NULL){
		wpl+=deep*root->weight;	
	}
	if(root->rchild==NULL){
		wpl_PreOrder(root->lchild,deep+1);
	}
	if(root->rchild!=NULL){
		wpl_PreOrder(root->rchild,deep+1);
	}
	return wpl;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
先序遍历保存到数组,然后遍历数组,如果某节点的左孩子或右孩子的值是x则找到
typedef struct node{
	int data;
	struct node *lchild,*rchild;
}bitree;
bitree *q[20];int r=0,f=0,flag=;

void preOrder(bitree *bt,char x){
	if(bt!=0 && flag==0){
		if(bt->data==x)	
			flag=1;return;
		else{
			r=r(r+1)%20;q[r]=bt;preorder(bt->lchild,x);
			preorder(bt->rchild,x);
		}
	}
}

void parent(bitree *bt,char x){
	int i;
	preorder(bt,x);
	for(i=f+1,i<=r)
	if(q[i]->lchild->data==x || q[i]->rchild->data==x)		break;
	if(flag==0){
		print("not found x\n");
	else if(i<=r) 
		printf("%c",bt->data);
	else 
		printf("no parent";)	
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

二叉树试题

给定一个二叉树和其中一结点,找出中序遍历顺序中该结点的下一个结点并返回(2013)

思路:如果
  • 1


  • 1
  • 2

求二叉树指定结点层次(2019)

思路:如果
  • 1

  • 1

二叉树中查找值为x的结点,打印值为x 的所有祖先,假设x的结点不多于1个(2013)

思路:如果
  • 1


  • 1
  • 2

非递归二叉树先序遍历(2017)

思路:如果
  • 1
void preOrder(BiTree T){
	BiTree *p=T,r=NULL;
	InitStack(s);
	while(p || !isEmpty(s)){
		if(p){
			visit(p);
			push(s,p);
			p=p->lchild;
		}	
		else{
			pop(s,p);
			p=p->rchild;
		}
	}
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

递归先根遍历树(2013)

void preTree(CTree T,int v,void(*visit)(int e)){
	CTBox *p;
	p=T;
	visit(p);
	preTree(p->nodes[v].firstchild,int v,void(*visit)(int e));
	preTree(p->nodes[v].next,int v,void(*visit)(int e));
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

设指针p(非空)指向二叉树中的某个节点,且该节点的左右子树均非空,写出p所指结点的中序后继算法。(2012)

void search(BiTree T){

















































	BiTree *q;
	q=p->rchild;
	if(q->lchild)
		while(q->lchild){
		q=q->lchild;
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57

计算给定二叉树T中度为2结点个数(2012)

int A(BiTree T,int &count){
 	if(!T)  return NULL;
 	if(T->lchild &&T->rchild){
 		count++;
 		A(T->lchild,count);
 		A(T->rchild,count);
	
}

int countDegreeTwo(TreeNode *root)
{
	if (root == NULL)
		return 0;
	if (root->left != NULL && root->right != NULL){
		return 1 + countDegreeTwo(root->left) + countDegreeTwo(root->right);
	}
	return countDegreeTwo(root->left) + countDegreeTwo(root->right);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

二叉树的深度算法(2011)

int TreeDepth(BiTree T){
	if(T==NULL{
		return 0;
	}
	ldep=TreeDepth(T->lchild);
	rdep=TreeDepth(T->rchild);
	if(ldep>rdep)	return ldep+1;
	else 	return rdep+1;
}

//树的深度
int TreeDepth(CSTree T){
	int hc,hs;
	if(T==NULL{
		return 0;
	}
	hc=TreeDepth(T->firstchild);
	hs=TreeDepth(T->nextsibling);
	if(hc+1>hs)	return hc+1;
	else 	return hs;
} 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

在一颗已知的二叉树T中存在数据元素为e1的结点,则删除该节点的右子树p;若存在数据元素为e2的结点且该节点无右子树,则将p插入为该结点的右子树(2010)

    非空中序线索二叉树T(T指向头结点,头结点的做指针lchild指向根节点,头头结点的右指针指向中序线索二叉树中最后访问的结点),若p指向其中某一个结点,试写出插入p的中序后继s结点的算法 (2008)

    
    
    • 1

    设q为指向非空的中序线索二叉树上的某个结点的指针,编写算法找出q的后继 (2003)

    void search(BiTree T){
    	BiTree *p=T;
    	if(p->rtag==0){
    		q=p->rchild;
    		while(q->lchild){
    			q=q->lchild;
    		}
    	}
    	else {
    		while(p->ltag==1 && p->pre->rtag==p){
    			p=p->pre;
    		}
    		if(p==NULL)		return NULL;
    	}
    	return q;
    }
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    二叉排序树插入算法(2005)

    思路:如果
    
    • 1
    声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/700265
    推荐阅读
    相关标签
      

    闽ICP备14008679号