}

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;}}
}

}

**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;

}

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);

}

}

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;}}}
}

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.判断二叉树是否为完全二叉树