二叉树刷题

	n++;
		if(num==k)
		count(L);
	DeQueue(S,p)
	if(p->lchild!=NULL)
	Enqueue(S,p);
	if(p->rchild!=NULL)
	Enqueue(S,p->rchild);

}
1
2
3
4
5
6
7
8
9
10

return q;
1

	}
	if(--last==0)
	{
		last=width;
		if(max

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

}

5.设二叉树以二叉链表作为存储结构，且二叉树中结点的数据域的值互不相同，设计一个算法将数据域值为x的结点的所有祖先结点的数据域的值输出来。
void Postorder(Bitree T，int x)
{
InitStack(S)
Bitree p=T;
Bitree r
while(p||!Isempty(S))
{
if§
{
Push(S,p);
p=p->lchild;
}

	 else{
	 	  Gettop(S,p)
	 	  if(p->data==x)
	 	 {
		    while(!Isempty(S))
	 	  {
	 	  	pop(s,p);
	 	  	visit(p);
		   }
		   return 0;
	  }
		   if(p->rchild&&p->rchild!=r)
	 	   p=p->rchild;
	 	   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

}

**6.编写一个非递归的算法，按关键字由大到小遍历一棵二叉排序树。
结点类型定义如下:
typedef int datatype; /数据元素的类型/
typedef struct node
{ datatype data; /数据域/
struct node lchild, rchild; /左、右指针域/
} bitree; /结点的类型/
void Reverse(Bitree &T){
Initstack(S1);
Initstack(S2)
Bitree p =T;
while(p||!isempty(S1))
{
if§
{
push(S,p);
p=p->lchild;
}
else
{
Pop(S,p);
Push(S2,P);
p=p->rchild;
}
}

while(!Isempty(S2))
{
pop(S2,p);
}
}

7. 二叉树采用二叉链表存储，设计一个算法求一棵给定二叉树的双孩子结点数。
其节点结构为如下，节点类型名为 BiNode，结点指针类型名为 BiTree。
int Inorder(Bitree T)
{
static int n=0;
if(T==NULL)
return 0;
else
{
if(T->lchild!=NULL&&T->rchild!=NULL)
n++;
Inorder(T->lchild);
Inorder(T->rchild);

}
return n;
1
2

}

8.编写算法根据二叉树的前序序列和中序序列建立二叉树的二叉链表存储结构

9.二叉排序树采用二叉链表存储，设计算法，按关键字递减的顺序输出各结
点的值typedef int datatype; /数据元素的类型/
typedef struct node
{ datatype data; /数据域/
struct node lchild, rchild; /左、右指针域/
} bitree; /结点的类型/
void Reverse(Bitree &T){
Initstack(S1);
Initstack(S2)
Bitree p =T;
while(p||!isempty(S1))
{
if§
{
push(S,p);
p=p->lchild;
}
else
{
Pop(S,p);
Push(S2,P);
p=p->rchild;
}
}

while(!Isempty(S2))
{
pop(S2,p);
printf(“%d”,p->data);
}
}

10.二叉树采用二叉链表存储。设计算法，基于层次遍历，统计树中叶子的数目。
void Level(Bitree T)
{ int n=0;
InitQueue(Q);
Bitree p;
EnQueue(Q);
while(!Isempty(Q))
{
DeQueue(Q,p);
if(p->lchildNULL&&p->rchildNULL)
n++;
if(p->lchild)
EnQueue(T->lchild);
if(p->rchild)
EnQueue(T->rchild);

}
1

}

11.链表建立二叉排序树
void Insert(Bitree &T,int k)
{
if(T==NULL)
{
Bitree p=(Bitee)malloc(sizeof(BiNode));
p->data=k;
p->rchild=p->lchild=NULL;
}
else if(T->data>k)
{
Insert(T->lchild,k);
}
else
Insert(T->rchild,k);
}

void Create_BSF(Bitree &T,int str[],int n)
{
T=NULL;
int i=0;
while(i {
Insert(T,str[i]);
}
}

12.已知n个结点的完全二叉树用顺序存储，设计非递归算法，对该完全二叉树进行中序遍历

13.写算法在中序线索二叉树上T查找值为x的结点

14.已知一颗二叉树采用二叉链表存储，定义二叉树中结点x的根路径为从根结点到x结点的一条路径
void print_path(BiTree &T)
{
if(T!=NULL)
{
printf(“%d”,T->data);
if(Height(T->lchild)>Height(T->rchild))
print_path(T->lchild);
else
print_path(T->rchild);
}
}

int Height(Bitree T)
{
if(T==NULL)
return 0;
else
return Max(Height(T->lchild),Height(T->rchild))+1 ;
}

15.设二叉树的存储结构为二叉链表，试写出算法，求二叉树中一条最长的路径长度，并输出此路径上各结点
//同用求最长路径
void print_path(BiTree &T)
{
if(T!=NULL)
{
printf(“%d”,T->data);
if(Height(T->lchild)>Height(T->rchild))
print_path(T->lchild);
else
print_path(T->rchild);
}
}

int Height(Bitree T)
{
if(T==NULL)
return 0;
else
return Max(Height(T->lchild),Height(T->rchild))+1 ;
}

16.设计求结点在二叉排序树中层次的算法
int Height(BiTree T,BiTree x)
{ BiTree p=T;
static int n=1;
while§
{
if(p==x)
return n;
else if(p->data>x>data)
{
p=p->lchild;
n++;
}
else
{
p=p->rchild;
n++;
}
}

}

17. 试编写一算法，在给定的二叉排序树上，找出任意两个不同结点最近的公共祖先

18.设计一个算法，要求该算法把二叉树的叶子结点从左往右连成单链表，表头指针为head
void Linklist(Bitree &T)
{
Initstack(S);
Bitree p=T;
Bitree r=NULL;
int n=0;
while(p||!isempty(S))
{
if§
{
push(s,p);
p=p->lchild;
}
else
{
pop(S,p);
if(p->lchildNULL&&p->rchild)
{
if(n0)
{
head->next=p;
r=p;

			   n=1;	
			}
			else
			  {
			  	r->next=p;
			  	r=p;
			  }
			
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11

19.查找一个结点x在二叉树中的双亲结点

Bitree find_parent(Bitree T,Bitree x)
{
if(T->NULL)
{
if(T->lchildx||T->rchildx)
return T;
else{
find_parent(T->lchild);
find_parent(T->rchild);
}
}
}

20.判断二叉树是否为完全二叉树
bool isbitree(Bitree &T)
{
Initstack(Q);
Bitree p=T;
Enqueue(Q,p);
while(!Isempty(Q))
{
Dequeue(Q,p);
if§
{
Enqueue(Q,p->lchild);
Enqueue(Q,p->rchild);
}
else{
if(!Dequeue(Q,p))
{
if§
return false;
}
}

}
return true;
1
2

}

21，求所有叶子结点到根结点的路径
void displaypath(Bitree &p,int path[],int len) //len从o开始
{
if(p->lchildNULL&&p->rchildNULL)
{
for(i=len-1;i>=0;i–)
printf(“%d”,path[i])
}
else{
path[len++]=p->data;
display(p->lchild,path[],len);
display(p->rchild,path[],len);
len–;
}

}

22试编写二叉树的自下而上，从右往左的层次遍历
本质是用栈
void Level(Bitree T)
{
Bitree p=T;
initstack(S);
initqueue(Q);
Enqueue(Q,p);
while(!isempty(Q))
{
Dequeue(Q,p);
push(S,p);
if(p->lchild!=NULL)
Enqueue(Q,p->lchild);
if(p->rchild!=NULL)
Enqueue(Q,p->rchild);
}

while(!isempty(S))
{
	Pop(S,p);
}
1
2
3
4

}

23.假设二叉树采用二叉链表存储结构，设计一个算法把树b的左右子树进行交换，空间0（1）
：典型的以时间换空间
后序遍历
void swap(Bitree p)
{ Bitree q;
if§
{
swap(p->lchild);
swap(p->rchild);
q=p->lchild;
p->lchild=p->rchild;
p->rchild=q
}

}

24.求wpl的权值
void Wpl(Bitree &T,int deep)
{ static wpl=0;
if(T->lchildNULL&&T->rchildNULL)
wpl=wpl+T->data*deep;
else
{ if(T->lchild!=NULL)
Wpl(T->lchild,deep+1);
if(T->rchild!=NULL)
Wpl(T->rchild,deep+1);
}
}

25.给定二叉树转换为等价的中缀表达式

中序遍历
根结点 叶子结点不加
其他都加
void Exchange(Bitree T,int deep)
{
if(rootNULL)
return ;
else if(root->lchildNULL&&root->rchild==NULL)
printf(“%d”,root->data);
else
{
if(deep>1)printf(“(”);
Exchange(T->lchild,deep+1);
printf(“%d”,root->data);
Exchange(T->rchild,deep+1);
if(deep>1)printf(“)”);
}

}

26.判断两个二叉树是否相似
int Same(Bitree A,Bitree B)
{
Bitree p=A;
Bitree q=B;

	if(p==NULL&&q==NULL)
	return 1;
	else if(p||q)
	return 0;
	else{
		return Same(p->lchild&&q->lchild)&&Same(p->rchild&&q->rchild) ;
	} 
1
2
3
4
5
6
7

}

27.二叉排序树按关键字递减
void Display(Bitree &T)
{
Bitree p=T;
Initstack(S);
while(p||!isempty(S))
{
if§
{
push(s,p);
p=p->rchild;
}
else{
popo(s,p);
printf(“%d”,p->data);
p=p->lchild;
}
}
}