java二叉樹刪除_數據結構 java編寫二叉樹的增加刪除與修改

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;
}
}

導航:首頁 > 編程語言 > java二叉樹刪除

java二叉樹刪除

與java二叉樹刪除相關的資料