已知一棵以二叉链表存储的二叉树，按从右到左的次序，利用叶子结点建立一个带头结点的双向链表。
（1）从键盘输入扩展的先序结点数据，建立二叉树。
（2）找叶子结点，找到后从二叉树中删除，然后插入到双向链表中。
（3）要求程序通过一个主菜单进行控制，通过选择菜单项序号调用各功能函数。
[提示]
前序、中序、后序遍历二叉树，访问叶子结点的相对次序都是从左至右。因此，可以采用头插法建立双向链表。
树的二叉链表的结点与双向链表的结点结构相同，只是对两个指针域的解释不同。
typedef struct tree {
char data;
struct tree *Llink;//左儿子 前驱节点
struct tree *Rlink;//右儿子 后继节点
struct tree *Parent;//父节点
} BTNode,*BinTree,DNode,*DoubleList;
测试数据，其扩展的先序遍历序列为ABC..DE.G..F..H..，建立二叉树的遍历叶子结点的次序为：C G F H。 所建立的双向链表为：
L-> <=>H<=>F<=>G<=>C
代码实现
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define MAXSIZE 50
#define scanf_s scanf
//二叉树节点
typedef struct tree {
char data;
struct tree *Llink;//左儿子 前驱节点
struct tree *Rlink;//右儿子 后继节点
struct tree *Parent;//父节点
} BTNode,*BinTree,DNode,*DoubleList;
int Select_menu() {
int sn;
printf(" 二叉树打印n");
printf("-------------------------------------------n");
printf("1.利用扩展的先序序列建立二叉树n");
printf("2 找叶子结点，找到后从二叉树中删除，然后插入到双向链表中并打印 。n");
printf("0.退出系统n");
printf("===============================n");
printf(" 请输入0--2: n");
for (;;) {
scanf_s("%d", &sn);
getchar();
if (sn > 2 || sn < 0)
printf("输入错误，请重新输入：n");
else
break;
}
return sn;
}
//按照层打印二叉树
void PrintBinTree(BinTree bt) {
if(bt==NULL){
printf("树为空n");
return;
}
printf("按照层打印二叉树为:");
BinTree p;
BinTree *q[MAXSIZE];
int head = 0, tail = 0;
if (bt) {
tail = (tail + 1) % MAXSIZE;
q[tail] = bt;
}
while (head != tail) {
head = (head + 1) % MAXSIZE;
p = q[head];
printf("%c ", p->data);
if (p->Llink != NULL) {
tail = (tail + 1) % MAXSIZE;
q[tail] = p->Llink;
}
if (p->Rlink != NULL) {
tail = (tail + 1) % MAXSIZE;
q[tail] = p->Rlink;
}
}
printf("n");
return;
}
//打印循双向链表
void PrintDoubleList(DoubleList dl) {
if(dl==NULL || dl->Rlink==NULL){
printf("双向链表为空n");
return;
}
printf("双向环链为:");
//遍历链表，表头不存值
while (dl->Rlink) {
dl = dl->Rlink;
printf("%c ", dl->data);
}
printf("n");
return;
}
//按照层打印二叉树后打印循双向链表
void printAll(BinTree bt,DoubleList dl){
PrintBinTree(bt);
PrintDoubleList(dl);
}
//叶子节点个数
int LeafCount(BTNode* pnode)
{
static int count;
if (pnode != NULL)
{
if (pnode->Llink == NULL && pnode->Rlink == NULL)
{
count++;
}
LeafCount(pnode->Llink);
LeafCount(pnode->Rlink);
}
return count;
}
//计算二叉树深度
int treeDepth(BTNode *t) {
int deep = 0;
int left = 0;
int right = 0;
if (t == NULL) {
return deep;
}
left = treeDepth(t->Llink);
right = treeDepth(t->Rlink);
deep = right > left ? right : left;
deep++;
return deep;
}
void CreateTree(BinTree *bt) {
char ch;
ch=getchar();
if(ch=='.') *bt=NULL;
else
{
*bt=(BinTree)malloc(sizeof(BTNode));
if(*bt==NULL) return 0;
(*bt)->data=ch;
CreateTree(&(*bt)->Llink);
CreateTree(&(*bt)->Rlink);
}
return;
}
void setParent(BinTree p,BinTree q)
{
if(p==NULL) return ;
else{
if(p->Llink!=NULL) p->Llink->Parent=p;
if(p->Rlink!=NULL) p->Rlink->Parent=p;
}
setParent(p->Llink,q);
setParent(p->Rlink,q);
}
void CreateDListFromLeaves(BinTree bt,DoubleList dl){
//新建带头结点的双向链表
dl = (DoubleList)malloc(sizeof(DNode));
dl->data=0;
dl->Llink=NULL;
dl->Rlink=NULL;
//查出叶子节点个数
int leaves = LeafCount(bt);
int depth = treeDepth(bt);
if(leaves == 0 || depth==1){
printAll(bt,dl);
return;
}
//从二叉树中删除，然后用头插法插入到双向链表中
LeafTraversal(bt,dl,2);
//遍历二叉树叶子节点,用头插法插入到双向链表中
printAll(bt,dl);
}
void LeafTraversal(BTNode* pnode,DoubleList dl,int LeftOrRight)
{
if(NULL==pnode) return;
LeafTraversal(pnode->Llink,dl,0);
if(pnode->Llink==NULL&&pnode->Rlink==NULL&&pnode->data!='P')
{
if(LeftOrRight==0) pnode->Parent->Llink=NULL;
else if(LeftOrRight==1) pnode->Parent->Rlink=NULL;
DoubleList s;
s = (DoubleList)malloc(sizeof(DNode));
s->data=pnode->data;
s->Rlink=dl->Rlink;
dl->Rlink=s;
}
LeafTraversal(pnode->Rlink,dl,1);
return;
}
int main(void) {
BinTree bt = NULL;
DoubleList dl = NULL;
BinTree *btnull = NULL;
for (;;) {
switch (Select_menu()) {
case 1:
printf("请使用前序遍历的方式输入字符串，用.代替空值n");
CreateTree(&bt);
setParent(bt,btnull);
break;
case 2:
CreateDListFromLeaves(bt,dl);
break;
case 0:
printf("再见！n");
free(bt);
free(dl);
return 0;
}
}
}
暑期编程PK赛 得CSDN机械键盘等精美礼品！
