二叉树题集

王道数据结构

二叉树遍历

//先序遍历
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==0）	FirstNode(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