数据结构 二叉树 用二叉链链表存储结构 写出删除二叉树所有的叶子节点的算法

Question

如题所述

Answer 1

//下面有运行结果
#include<stdio.h>
#include<stdlib.h>
#define OVERFLOW 0
#define ERROR 0
#define OK 1
typedef char TElemType;
typedef int Status;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status InitTree(BiTree &T)
{
T=(BiTree)malloc(sizeof(BiTNode));
T->lchild=NULL;
T->rchild=NULL;
if(!T) exit(OVERFLOW);
else printf("二叉树初始化成功!\n");
return OK;
}
Status CreateBiTree(BiTree &T)
{
char ch;
scanf("%c",&ch);
if(ch=='#')
T=NULL;
else
{
if(!(T=(BiTree)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
//初始条件：二叉树T存在，Visit是对结点操作的应用函数
//操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次
void PreOrderTraverse(BiTree T)
{
if (T)//T不空
{
printf("%c",T->data);//先访问根结点
PreOrderTraverse(T->lchild);//再先序遍历左子树
PreOrderTraverse(T->rchild);//最后先序遍历右子树
}
}
Status free_Leaf(BiTree &T)
{
if(T)
{
free_Leaf(T->lchild);
if (!T->lchild && !T->rchild)
{
T->data = ' ';//属于假删除，将叶子结点的值置为空
//free(T);
//T = NULL;
}
else
free_Leaf(T->rchild);
}
return OK;
}
int main()
{
BiTree T;
InitTree(T);
printf("按先序顺序输入你要建立的二叉树(#代表空)：");
CreateBiTree(T);
printf("先序遍历所创建的二叉树：\n");
PreOrderTraverse(T);
printf("\n删除其所有的叶子结点...\n");
free_Leaf(T);

printf("\n删除所有叶子结点后重新遍历该二叉树\n");
if (T)
PreOrderTraverse(T);
printf("\n");
return 0;
}
/*
输出结果：
------------------------
二叉树初始化成功!
按先序顺序输入你要建立的二叉树(#代表空)：abc###d##
先序遍历所创建的二叉树：
abcd
删除其所有的叶子结点...
删除所有叶子结点后重新遍历该二叉树
ab
Press any key to continue
------------------------------
*/

Answer 2

bool* deleteLeaf(Node * curNode)
{
if(curNode==null)

return false;

if(deleteLeaf(curNode->left)==null&&deleteLeaf(curNode->right==null))
{
//此时说明当前节点为叶子节点，故删除该节点

delete curNode;
return ture;

}
}来自：求助得到的回答本回答被网友采纳

Answer 3

，，，