A. 如何删除一棵普通二叉树的叶子结点
首先我们应该知道要删除的子节点的地址和其父节点的地址,父节点的地址应该在建树过程中存储。此时一个二叉树的节点中应该有三个指针:指向其左子结点的指针,指向其右子节点的指针还有指向其父节点的指针(在结构体定义时要注意啊)。当找到其父节点时,通过叶子节点的地址判断这个叶子节点是其父节点的左子结点还是右子节点。如果是其左子结点,那么将父节点指向左子结点的指针值赋为NULL,否则将其父节点指向右子节点的指针值赋为NULL。之后就可以释放我们要删除的叶子节点了。基本的删除思路就是这样的,建议自己建立二叉树并用代码实现。
B. 关于删除二叉树的提问
deletetree()函数改为如下:
void
deletetree(bitree
**bt){
if(*bt!=NULL){
deletetree(&((*bt)->lchild));
deletetree(&((*bt)->rchild));
free((*bt));
*bt=NULL;
}
}
main()函数改为如下:
void
main(){
bitree
*b;
char
*s="a(b(d(g),e(h,i)),c(,f))";
creatree(&b,s);
printf("二叉树括号表示:");
printree(b);
printf("\n");
deletetree(&b);
/***********注意这里************/
printree(b);
printf("\n");
}
C. 如何删除二叉树中的一个结点.
有两种方法:
(1),中序直接前趋结点法:将欲删除结点的左子树中最大者向上提。
(2),中序直接后继结点法:将欲删除结点的右子树中最小者向上题。
此两种方式虽然得到不同的二叉树,但具有下列性质:
(1)二者都维持二叉树的特性。
(2)二者的中序遍历次序相同。
D. 怎样用java实现二叉树的建立,遍历和节点删除
回答:smile2me
学妹
6月13日 13:32 //BinaryTree.h
/* 二叉树的二叉链表结点定义 */
typedef char datatype;
typedef struct BiTNode
{
datatype data;
struct BiTNode * LChild , * RChild ;
} BiTNode , * BiTree ;
//数叶子结点的数目
/*
Author: WadeFelix RenV
*/
#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree.h"
int countLeaf( BiTree BT )
{
if( BT == NULL ) return 0;
if( BT->LChild==NULL && BT->RChild==NULL ) return 1;
return(countLeaf(BT->LChild)+countLeaf(BT->RChild));
}
//数非叶子结点的数目
int countNotLeaf( BiTree BT )
{
if( BT == NULL ) return 0;
if( BT->LChild==NULL && BT->RChild==NULL ) return 0;
return(1+countNotLeaf(BT->LChild)+countNotLeaf(BT->RChild));
}
//判断是否是排序二叉树
#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree.h"
int isPaiXu( BiTree BT )
{
if( BT == NULL )return 1;
if( BT->LChild && (BT->LChild->data > BT->data) )return 0;
if( BT->RChild && (BT->RChild->data < BT->data) )return 0;
return( isPaiXu(BT->LChild)&&isPaiXu(BT->RChild) );
}
E. 如何删除二叉树的节点(该节点有左右孩子,且左右孩子也有左右孩子)
// S_dt_ecpxs.cpp : 定义控制台应用程序的入口点。
//动态查找表 二叉排序树的插入和删除
#include "stdafx.h"
#include"stdio.h"
#include"string.h"
#include"malloc.h"
typedef int ElemType;
//定义
typedef struct BiTNode{
int data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//查找关键字是key的数据元素
//T是要查找的数 key是查找的值 f是双亲 p是该数据元素的结点
int SearchBST(BiTree T,int key,BiTree f,BiTree *p)
{
//查找不成功
if(!T){
*p=f;
return 0;
}else{
if(key==T->data){//查找成功
*p=T;
return 1;
}else{
if(key<T->data){
//在左子树中继续查找
return SearchBST(T->lchild,key,T,p);
}else{
//在右子树中继续查找
return SearchBST(T->rchild,key,T,p);
}
}
}
}
//添加
int InsertBST(BiTree *T,int key)
{
BiTree p,s;
//没有找到
if(!SearchBST(*T,key,NULL,&p)){
s=(BiTree)malloc(sizeof(BiTNode));
s->data=key;
s->lchild=s->rchild=NULL;
if(!p){ //被插结点*s为新的根节点
*T=s;
}else{
if(key<p->data) p->lchild=s; //被插结点*s为左孩子
else p->rchild=s; //被插结点*s为右孩子
}
return 1;
}else return 0;
}
//先序遍历
void ProOrderTraverse(BiTree T){
//如果为空 返回
if(T==NULL) return;
else{
printf("-->%d",T->data);
//printf("zuo:%d",T->lchild->data);
//遍历左孩子和右孩子
ProOrderTraverse(T->lchild);
ProOrderTraverse(T->rchild);
}
}
//删除操作
int Delete(BiTree *p)
{
BiTree q,s;
if(!(*p)->rchild){ //右子树为空 重接它的左子树
q=*p;
*p=(*p)->lchild;
free(q);
}else{
if(!(*p)->lchild){ //若左子树空 则重新接它的右子树
q=*p;
*p=(*p)->rchild;
}else{//若都不为空
q=*p;
s=(*p)->lchild;
while(s->rchild){ //转左 然后向右到尽头
q=s; s=s->rchild;
}
(*p)->data=s->data; //s指向被删除结点的前驱
if(q!=*p)
q->rchild=s->lchild; //重接q的右子树
else
q->lchild=s->lchild;//重接q的左子树
free(s);
}
}
return 1;
}
//在T中 删除key元素
int DeleteBST(BiTree *T,int key){
if(!*T) return 0;
else{
//如果成功找到 就删除
if(key==(*T)->data) return Delete(T);
else{
//否则 小于节点值 遍历左子树
if(key<(*T)->data)
return DeleteBST(&(*T)->lchild,key);
else
return DeleteBST(&(*T)->rchild,key);
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
BiTree T=NULL;
int i,e,count;
//输入二叉排序树的元素
printf("请输入元素个数:");
scanf("%d",&count);
for(i=0;i<count;i++){
printf("\n请输入元素:");
scanf("%d",&e);
//插入数据
InsertBST(&T,e);
}
printf("\n插入成功\n");
//先序遍历二叉排序树
printf("\n二叉排序树中的元素依次是:");
ProOrderTraverse(T);
//新添加一个元素
printf("\n\n请输入要添加的元素值:");
scanf("%d",&e);
//插入数据
InsertBST(&T,e);
printf("\n插入成功\n");
printf("\n添加之后二叉排序树中的元素依次是:");
ProOrderTraverse(T);
//删除二叉排序树的元素
printf("\n\n请输入要删除的元素值:");
scanf("%d",&e);
if(DeleteBST(&T,e)){
printf("\n删除成功\n");
}else{
printf("\n没有找到该元素值\n");
}
printf("\n删除之后二叉排序树中的元素依次是:");
ProOrderTraverse(T);
printf("\n");
scanf("%d",argc);
return 0;
}
我原来写过一个二叉排序树的代码 C语言的 vs下能运行
你借鉴一下把
F. 查找二叉树怎么删除节点
怎么又是你,我给你的代码没认真看么?那是二叉树函数库,一并具全。
searchtree delete(int
x,searchtree t)删除指定结点函数。你看着我给你的代码有这个东西没有。调用的时候delete(结点,树指针);就这样。二叉树和c语言都很复习,要认真研究。还有二叉树不就是二叉查找树吗?(多了查找功能罢了)。我怀疑我给你的代码都没看完,这个不能心急,我研究二叉树都花了几天时间,没有耐性不行的。
G. 二叉树删除叶结点的问题
删除节点后,取其左子树的最大元素填充该节点,留下的空缺由它的下层元素填充。
如果无左子树,则直接用右孩子填充。
删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;
}
H. 数据结构 java编写二叉树的增加删除与修改
亲,我没写出来,但是给你找了一个,感觉人家写的还不错,你参考下吧!~~~
package com.algorithm.tree;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;
public class Tree<T> {
private Node<T> root;
public Tree() {
}
public Tree(Node<T> root) {
this.root = root;
}
//创建二叉树
public void buildTree() {
Scanner scn = null;
try {
scn = new Scanner(new File("input.txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
root = createTree(root,scn);
}
//先序遍历创建二叉树
private Node<T> createTree(Node<T> node,Scanner scn) {
String temp = scn.next();
if (temp.trim().equals("#")) {
return null;
} else {
node = new Node<T>((T)temp);
node.setLeft(createTree(node.getLeft(), scn));
node.setRight(createTree(node.getRight(), scn));
return node;
}
}
//中序遍历(递归)
public void inOrderTraverse() {
inOrderTraverse(root);
}
public void inOrderTraverse(Node<T> node) {
if (node != null) {
inOrderTraverse(node.getLeft());
System.out.println(node.getValue());
inOrderTraverse(node.getRight());
}
}
//中序遍历(非递归)
public void nrInOrderTraverse() {
Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
node = stack.pop();
System.out.println(node.getValue());
node = node.getRight();
}
}
//先序遍历(递归)
public void preOrderTraverse() {
preOrderTraverse(root);
}
public void preOrderTraverse(Node<T> node) {
if (node != null) {
System.out.println(node.getValue());
preOrderTraverse(node.getLeft());
preOrderTraverse(node.getRight());
}
}
//先序遍历(非递归)
public void nrPreOrderTraverse() {
Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
System.out.println(node.getValue());
stack.push(node);
node = node.getLeft();
}
node = stack.pop();
node = node.getRight();
}
}
//后序遍历(递归)
public void postOrderTraverse() {
postOrderTraverse(root);
}
public void postOrderTraverse(Node<T> node) {
if (node != null) {
postOrderTraverse(node.getLeft());
postOrderTraverse(node.getRight());
System.out.println(node.getValue());
}
}
//后续遍历(非递归)
public void nrPostOrderTraverse() {
Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> node = root;
Node<T> preNode = null;//表示最近一次访问的节点
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
node = stack.peek();
if (node.getRight() == null || node.getRight() == preNode) {
System.out.println(node.getValue());
node = stack.pop();
preNode = node;
node = null;
} else {
node = node.getRight();
}
}
}
//按层次遍历
public void levelTraverse() {
levelTraverse(root);
}
public void levelTraverse(Node<T> node) {
Queue<Node<T>> queue = new LinkedBlockingQueue<Node<T>>();
queue.add(node);
while (!queue.isEmpty()) {
Node<T> temp = queue.poll();
if (temp != null) {
System.out.println(temp.getValue());
queue.add(temp.getLeft());
queue.add(temp.getRight());
}
}
}
}
//树的节点
class Node<T> {
private Node<T> left;
private Node<T> right;
private T value;
public Node() {
}
public Node(Node<T> left,Node<T> right,T value) {
this.left = left;
this.right = right;
this.value = value;
}
public Node(T value) {
this(null,null,value);
}
public Node<T> getLeft() {
return left;
}
public void setLeft(Node<T> left) {
this.left = left;
}
public Node<T> getRight() {
return right;
}
public void setRight(Node<T> right) {
this.right = right;
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}
}
I. 编写一个程序从二叉排序树中删除一个结点,使该二叉排序树仍为二叉树
1.用C++实现删除结点(*p)的辅助函数DeleteHelp:
templatte<class
KeyType,class
OtherInfoType>
void
BinarySortTree<KeyType,OtherInfoType>::DeleteHelp(BinTreeNode<ElemType<KeyType,OtheInfoType>>*&p)
{
BinTreeNode<ElemType<KeyType,OtherInfoType>>*tmpPtr,*tmpF;
if(p->leftChild==NULL&&p->righeChild==NULL)
{
delete
p;
p=NULL;
}
else
if(p->leftChild==NULL)
{
tmpPtr=p;
p=p->rightChild;
delete
tmpPtr;
]
else
if(p->rightChild==NULL)
{
tmpPtr=p;
p=p->leftChild;
delete
tmpPtr;
}
else
{
tmpF=p;
tmpPtr=p->leftChild;
while(tmpPtr->rightChild!=NULL)
{
tmpF=tmpPtr;
tmpPtr=tmpPtr->rightChild;
}
p->data=tmpPtr->data;
if(tmpF->rightChild==tmpPtr)
{
DeleteHelp(tmpF->rightChild);
}
esle
{
DeleteHelp(tmpF->leftChildO);
}
}
}
2.找到要删除的结点,再调用DeleteHelp删除就行
template<class
KeyType,class
OtherInfoType>
bool
BinaryTree,KeyType,OtherInType>::Delete(const
KeyType&key)
{
BinTreeNode<ElemType,KeyType,OtherInfoType>>*p,*f;
p=SearchHelp(key,f);
if(p==NULL)
{
return
false;
}
else
{
if(f==NULL)
{
DeleteHelp(p);
}
else
if(key<f->leftChild);
}
esle
{
DeleteHelp(f->rightChild);
}
return
true;
}
}