㈠ 如何刪除一棵普通二叉樹的葉子結點
首先我們應該知道要刪除的子節點的地址和其父節點的地址，父節點的地址應該在建樹過程中存儲。此時一個二叉樹的節點中應該有三個指針：指向其左子結點的指針，指向其右子節點的指針還有指向其父節點的指針（在結構體定義時要注意啊）。當找到其父節點時，通過葉子節點的地址判斷這個葉子節點是其父節點的左子結點還是右子節點。如果是其左子結點，那麼將父節點指向左子結點的指針值賦為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;
}