㈠ 如何删除一棵普通二叉树的叶子结点
首先我们应该知道要删除的子节点的地址和其父节点的地址，父节点的地址应该在建树过程中存储。此时一个二叉树的节点中应该有三个指针：指向其左子结点的指针，指向其右子节点的指针还有指向其父节点的指针（在结构体定义时要注意啊）。当找到其父节点时，通过叶子节点的地址判断这个叶子节点是其父节点的左子结点还是右子节点。如果是其左子结点，那么将父节点指向左子结点的指针值赋为NULL，否则将其父节点指向右子节点的指针值赋为NULL。之后就可以释放我们要删除的叶子节点了。基本的删除思路就是这样的，建议自己建立二叉树并用代码实现。
㈡ 数据结构 二叉树 用二叉链链表存储结构 写出删除二叉树所有的叶子节点的算法
//下面有运行结果
#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
------------------------------
*/
㈢ 二叉树删除叶结点的问题
删除节点后，取其左子树的最大元素填充该节点，留下的空缺由它的下层元素填充。
如果无左子树，则直接用右孩子填充。
删30：
60
/
\
20
80
\
\
40
90
/
/
35
85
/
\
32
88
删80：
60
/
\
30
90
/
\
/
20
40
85
/
\
35
88
/
32
删60：
40
/
\
30
80
/
\
\
20
35
90
/
/
32
85
\
88
实现上述二叉搜索树删除操作的函数为：
bstree
delete(
elementtype
x,bstree
t)
{
position
tmpcell;
if(t==null)
error("要删除的元素x未找到");
else
if(x<t->element)
/*go
left
*/
t->left=delete(x,t->left);/*
在左子树递归删除*/
else
if(x>t->element)
/*go
right
*/
t->right=delete(x,t->right);/*
在右子树递归删除*/
else
/*找到要删除的节点*/
if(t->left!=null)
/*删除节点有左子树*/
{
/*在左子树中找最小的元素填充删除节点*/
tmpcell=findmax(t->left);
t->element=tmpcell->element;
t->left=delete(t->element,t->left);/*在删除节点的左子树中删除最大元素*/
}
else
/*删除节点无左子树*/
{
t=t->left;
free(tmpcell);
}
return
t;
}