㈠ java写的关于二叉排序树的删除操作的问题
package ggg;
import java.math.BigDecimal;
import java.util.Scanner;
import java.util.Random;
import java.util.Stack;
/**
* 二叉排序树（又称二叉查找树）
* （1）可以是一颗空树
* （2）若左子树不空，则左子树上所有的结点的值均小于她的根节点的值
* （3）若右子树不空，则右子树上所有的结点的值均大于她的根节点的值
* （4）左、右子树也分别为二叉排序树
*
*
* 性能分析：
* 查找性能：
* 含有n个结点的二叉排序树的平均查找长度和树的形态有关，
* （最坏情况）当先后插入的关键字有序时，构成的二叉排序树蜕变为单枝树。查找性能为O(n)
* （最好情况）二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log2(n)成正比
*
*
* 插入、删除性能：
* 插入、删除操作间复杂度都O(log(n))级的，
* 即经过O(log(n))时间搜索到了需插入删除节点位置和删除节点的位置
* 经O(1)级的时间直接插入和删除
* 与顺序表相比，比序顺序表插入删除O(n)(查找时间O(log(n))移动节点时间O(n))要快
* 与无序顺序表插入时间O(1)，删除时间O(n)相比，因为是有序的，所查找速度要快很多
*
*
*
* 作者：小菜鸟
* 创建时间：2014-08-17
*
*/
public class BinarySortTree {
private Node root = null;
/**查找二叉排序树中是否有key值*/
public boolean searchBST(int key){
Node current = root;
while(current != null){
if(key == current.getValue())
return true;
else if(key < current.getValue())
current = current.getLeft();
else
current = current.getRight();
}
return false;
}
/**向二叉排序树中插入结点*/
public void insertBST(int key){
Node p = root;
/**记录查找结点的前一个结点*/
Node prev = null;
/**一直查找下去，直到到达满足条件的结点位置*/
while(p != null){
prev = p;
if(key < p.getValue())
p = p.getLeft();
else if(key > p.getValue())
p = p.getRight();
else
return;
}
/**prve是要安放结点的父节点，根据结点值得大小，放在相应的位置*/
if(root == null)
root = new Node(key);
else if(key < prev.getValue())
prev.setLeft(new Node(key));
else prev.setRight(new Node(key));
}
/**
* 删除二叉排序树中的结点
* 分为三种情况：（删除结点为*p ，其父结点为*f）
* （1）要删除的*p结点是叶子结点，只需要修改它的双亲结点的指针为空
* （2）若*p只有左子树或者只有右子树，直接让左子树/右子树代替*p
* （3）若*p既有左子树，又有右子树
* 用p左子树中最大的那个值（即最右端S）代替P，删除s，重接其左子树
* */
public void deleteBST(int key){
deleteBST(root, key);
}
private boolean deleteBST(Node node, int key) {
if(node == null) return false;
else{
if(key == node.getValue()){
return delete(node);
}
else if(key < node.getValue()){
return deleteBST(node.getLeft(), key);
}
else{
return deleteBST(node.getRight(), key);
}
}
}
private boolean delete(Node node) {
Node temp = null;
/**右子树空，只需要重接它的左子树
* 如果是叶子结点，在这里也把叶子结点删除了
* */
if(node.getRight() == null){
temp = node;
node = node.getLeft();
}
/**左子树空， 重接它的右子树*/
else if(node.getLeft() == null){
temp = node;
node = node.getRight();
}
/**左右子树均不为空*/
else{
temp = node;
Node s = node;
/**转向左子树，然后向右走到“尽头”*/
s = s.getLeft();
while(s.getRight() != null){
temp = s;
s = s.getRight();
}
node.setValue(s.getValue());
if(temp != node){
temp.setRight(s.getLeft());
}
else{
temp.setLeft(s.getLeft());
}
}
return true;
}
/**中序非递归遍历二叉树
* 获得有序序列
* */
public void nrInOrderTraverse(){
Stack<Node> stack = new Stack<Node>();
Node 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 static void main(String[] args){
BinarySortTree bst = new BinarySortTree();
/**构建的二叉树没有相同元素*/
int[] num = {4,7,2,1,10,6,9,3,8,11,2, 0, -2};
for(int i = 0; i < num.length; i++){
bst.insertBST(num[i]);
}
bst.nrInOrderTraverse();
System.out.println(bst.searchBST(10));
bst.deleteBST(2);
bst.nrInOrderTraverse();
}
/**二叉树的结点定义*/
public class Node{
private int value;
private Node left;
private Node right;
public Node(){
}
public Node(Node left, Node right, int value){
this.left = left;
this.right = right;
this.value = value;
}
public Node(int value){
this(null, null, value);
}
public Node getLeft(){
return this.left;
}
public void setLeft(Node left){
this.left = left;
}
public Node getRight(){
return this.right;
}
public void setRight(Node right){
this.right = right;
}
public int getValue(){
return this.value;
}
public void setValue(int value){
this.value = value;
}
}
}
㈡ 数据结构 二叉树 用二叉链链表存储结构 写出删除二叉树所有的叶子节点的算法
//下面有运行结果
#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
------------------------------
*/
㈢ 求排序二叉树删除结点的算法
首先判断有没有父节点（若没有父节点，则需要在修改fp的对应子节点的地方改动一下）
然后删除节点有没有子节点
1.如果都没有 直接删了 父节点fp的对应子节点改为null释放p就行了
2.如果只有一个子节点也好办，直接将fp的对应子节点改为p的这个子节点 再释放p就可以了
3.最麻烦的是有2个子节点 这种情况你有2个选择，一个是从p的左子树删，就是在p的左子树找到最大的节点（即从p的左节点开始，一直向右，直到没有右子节点的那个就是），先删除该最大节点（只可能是1，2的情况），然后将这个最大节点替换树中p的位置（fp的对应子节点设为它，它的子节点设为p的2个子节点），然后释放p。从p的右子树删也一样，不过是从右子树寻找最小节点替换。
我手头只有java的 就不贴出来了
㈣ 二叉排序树的节点删除
p的双亲节点还是指向的p的地址，这没错，
因为p=p->lchild是把p指向p的左孩子的地址，所以p的双亲结点指向的p就是指到了删除前p的左孩子结点，然后用free(q)释放了p的内存，就完成了重接左子树
㈤ 请问二叉树的删除算法是不是很复杂啊
这取决于树要怎样用了，如果只是删除子节点的话，还是很容易的。如果要删除中间节点，而中间节点的子节点需要补上来，则很复杂了。
我是觉得，一般程序猿都避免写数据结构，像红黑树这种东西，显然应该找第三方写好的库吧...
㈥ 二叉树的根结点，能否删除，有什么条件
二叉树的根节点当然可以删除啊，当左右子树都为空时，可以删除，强制性删除也可以啊，不过要从树的左子树下选一个结点来当根节点，不然，就会破坏二叉树的结构！
㈦ 二叉树的程序设计结点的增加删除修改查询
这样的代码网上有很多，这里我再VS运行成功的C语言代码供参考吧。也是自己学习二叉树创建查找的资料。
/*************************************************************************
这是一个二叉查找树，实现了以下操作：插入结点、构造二叉树、删除结点、查找、
查找最大值、查找最小值、查找指定结点的前驱和后继。上述所有操作时间复杂度
均为o(h),其中h是树的高度
注释很详细，具体内容就看代码吧
*************************************************************************/
#include<stdio.h>
#include<stdlib.h>
//二叉查找树结点描述
typedefintKeyType;
typedefstructNode
{
KeyTypekey;//关键字
structNode*left;//左孩子指针
structNode*right;//右孩子指针
structNode*parent;//指向父节点指针
}Node,*PNode;
//往二叉查找树中插入结点
//插入的话，可能要改变根结点的地址，所以传的是二级指针
voidinseart(PNode*root,KeyTypekey)
{
//初始化插入结点
PNodep=(PNode)malloc(sizeof(Node));
p->key=key;
p->left=p->right=p->parent=NULL;
//空树时，直接作为根结点
if((*root)==NULL){
*root=p;
return;
}
//插入到当前结点（*root）的左孩子
if((*root)->left==NULL&&(*root)->key>key){
p->parent=(*root);
(*root)->left=p;
return;
}
//插入到当前结点（*root）的右孩子
if((*root)->right==NULL&&(*root)->key<key){
p->parent=(*root);
(*root)->right=p;
return;
}
if((*root)->key>key)
inseart(&(*root)->left,key);
elseif((*root)->key<key)
inseart(&(*root)->right,key);
else
return;
}
//查找元素,找到返回关键字的结点指针，没找到返回NULL
PNodesearch(PNoderoot,KeyTypekey)
{
if(root==NULL)
returnNULL;
if(key>root->key)//查找右子树
returnsearch(root->right,key);
elseif(key<root->key)//查找左子树
returnsearch(root->left,key);
else
returnroot;
}
//查找最小关键字,空树时返回NULL
PNodesearchMin(PNoderoot)
{
if(root==NULL)
returnNULL;
if(root->left==NULL)
returnroot;
else//一直往左孩子找，直到没有左孩子的结点
returnsearchMin(root->left);
}
//非递推查找最小关键字
PNodesearchMin2(PNoderoot)
{
if(root==NULL)
returnNULL;
while(root->left!=NULL)
root=root->left;
returnroot;
}
//查找最大关键字,空树时返回NULL
PNodesearchMax(PNoderoot)
{
if(root==NULL)
returnNULL;
if(root->right==NULL)
returnroot;
else//一直往右孩子找，直到没有右孩子的结点
returnsearchMax(root->right);
}
//查找某个结点的前驱
PNodesearchPredecessor(PNodep)
{
//空树
if(p==NULL)
returnp;
//有左子树、左子树中最大的那个
if(p->left)
returnsearchMax(p->left);
//无左子树,查找某个结点的右子树遍历完了
else{
if(p->parent==NULL)
returnNULL;
//向上寻找前驱
while(p){
if(p->parent->right==p)
break;
p=p->parent;
}
returnp->parent;
}
}
//查找某个结点的后继
PNodesearchSuccessor(PNodep)
{
//空树
if(p==NULL)
returnp;
//有右子树、右子树中最小的那个
if(p->right)
returnsearchMin(p->right);
//无右子树,查找某个结点的左子树遍历完了
else{
if(p->parent==NULL)
returnNULL;
//向上寻找后继
while(p){
if(p->parent->left==p)
break;
p=p->parent;
}
returnp->parent;
}
}
//根据关键字删除某个结点,删除成功返回1,否则返回0
//如果把根结点删掉，那么要改变根结点的地址，所以传二级指针
intdeleteNode(PNode*root,KeyTypekey)
{
PNodeq;
//查找到要删除的结点
PNodep=search(*root,key);
KeyTypetemp;//暂存后继结点的值
//没查到此关键字
if(!p)
return0;
//1.被删结点是叶子结点，直接删除
if(p->left==NULL&&p->right==NULL){
//只有一个元素，删完之后变成一颗空树
if(p->parent==NULL){
free(p);
(*root)=NULL;
}else{
//删除的结点是父节点的左孩子
if(p->parent->left==p)
p->parent->left=NULL;
else//删除的结点是父节点的右孩子
p->parent->right=NULL;
free(p);
}
}
//2.被删结点只有左子树
elseif(p->left&&!(p->right)){
p->left->parent=p->parent;
//如果删除是父结点，要改变父节点指针
if(p->parent==NULL)
*root=p->left;
//删除的结点是父节点的左孩子
elseif(p->parent->left==p)
p->parent->left=p->left;
else//删除的结点是父节点的右孩子
p->parent->right=p->left;
free(p);
}
//3.被删结点只有右孩子
elseif(p->right&&!(p->left)){
p->right->parent=p->parent;
//如果删除是父结点，要改变父节点指针
if(p->parent==NULL)
*root=p->right;
//删除的结点是父节点的左孩子
elseif(p->parent->left==p)
p->parent->left=p->right;
else//删除的结点是父节点的右孩子
p->parent->right=p->right;
free(p);
}
//4.被删除的结点既有左孩子，又有右孩子
//该结点的后继结点肯定无左子树(参考上面查找后继结点函数)
//删掉后继结点,后继结点的值代替该结点
else{
//找到要删除结点的后继
q=searchSuccessor(p);
temp=q->key;
//删除后继结点
deleteNode(root,q->key);
p->key=temp;
}
return1;
}
//创建一棵二叉查找树
voidcreate(PNode*root,KeyType*keyArray,intlength)
{
inti;
//逐个结点插入二叉树中
for(i=0;i<length;i++)
inseart(root,keyArray[i]);
}
intmain3(void)
{
inti;
PNoderoot=NULL;
KeyTypenodeArray[11]={15,6,18,3,7,17,20,2,4,13,9};
create(&root,nodeArray,11);
for(i=0;i<2;i++)
deleteNode(&root,nodeArray[i]);
printf("%d ",searchPredecessor(root)->key);
printf("%d ",searchSuccessor(root)->key);
printf("%d ",searchMin(root)->key);
printf("%d ",searchMin2(root)->key);
printf("%d ",searchMax(root)->key);
printf("%d ",search(root,13)->key);
system("pause");
return0;
}
㈧ 数据结构 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;
}
}
㈨ 求一个排序二叉树删除操作
包括二叉排序树的创建；先序遍历，中序遍历，后序遍历的递归和非递归算法；
结点的插入，查找和删除，其中删除算法有两种和一个优化算法；还有层序遍历算法；
输出二叉树，分别使用先序和后序算法计算二叉树的深度等。
较为全面的介绍了二叉排序树的基本算法。
*/}
PROGRAM BinaryTree (input, output);
TYPE
element = char;
Btree = ^node;
node = record
data : element;
lc, rc : Btree;
end;
CONST
MAX = 1000; {最大结点数量}
WIDTH = 2; {输出元素值宽度}
ENDTAG = '#';
VAR
root, obj : Btree;
height, depth : integer;
data : element;{向一个二叉排序树b中插入一个结点s}
FUNCTION InsertNode(var t : Btree; s : Btree) : boolean;
begin
if t = nil then
begin
t := s;
InsertNode := true;
end {if}
else if t^.data > s^.data then {把s所指结点插入到左子树中}
InsertNode := InsertNode(t^.lc, s)
else if t^.data < s^.data then {把s所指结点插入到右子树中}
InsertNode := InsertNode(t^.rc, s)
else {若s->data等于b的根结点的数据域之值，则什么也不做}
InsertNode := false;
end; {InsertNode}{生成一棵二叉排序树（以ENDTAG为结束标志）}
PROCEDURE CreateTree(var t : Btree);
var
data : element;
s : Btree;
begin
t := nil;
read(data);
while data <> ENDTAG do
begin
new(s);
s^.data := data;
s^.lc := nil;
s^.rc := nil;
if not(InsertNode(t, s)) then
dispose(s);{插入一个结点s}
read(data);
end;
end;{销毁一棵二叉排序树}
PROCEDURE DestroyTree(var t : Btree);
begin
if t <> nil then
begin
DestroyTree(t^.lc);
DestroyTree(t^.rc);
dispose(t);
t := nil;
end; {if}
end; {DestroyTree}{递归算法:}
{先序遍历}
PROCEDURE Preorder_1(t : Btree);
begin
if t <> nil then
begin
write(t^.data:WIDTH); {输出该结点（根结点）}
Preorder_1(t^.lc); {遍历左子树}
Preorder_1(t^.rc); {遍历右子树}
end;
end;{中序遍历}
PROCEDURE Inorder_1(t : Btree);
begin
if t <> nil then
begin
Inorder_1(t^.lc); {遍历左子树}
write(t^.data:WIDTH); {输出该结点（根结点）}
Inorder_1(t^.rc); {遍历右子树}
end;
end;{后序遍历}
PROCEDURE Postorder_1(t : Btree);
begin
if t <> nil then
begin
Postorder_1(t^.lc); {遍历左子树}
Postorder_1(t^.rc); {遍历右子树}
write(t^.data:WIDTH); {输出该结点（根结点）}
end;
end;{非递归算法（使用栈存储树）}
{先序遍历}
PROCEDURE Preorder_2(t : Btree);
var
p : Btree; {p表示当前结点}
stack : array [1..MAX] of Btree; {栈stack[]用来存储结点}
top : integer;
begin
top := 1;
if t <> nil then {先判断是否为空树}
begin
stack[top] := t; {根结点入栈}
while top >= 1 do {栈内还有元素}
begin
p := stack[top]; {栈顶元素出栈}
dec(top);
write(p^.data:WIDTH);
if p^.rc <> nil then {如果该结点有右孩子，将右孩子入栈}
begin
inc(top);
stack[top] := p^.rc;
end; {if}
if p^.lc <> nil then{如果该结点有左孩子，将左孩子入栈，按照后入先出原则，左孩子先出栈}
begin
inc(top);
stack[top] := p^.lc;
end; {if}
end; {while}
end;{if}
end;{Preorder_2}
㈩ 怎么删除二叉树根结点
怎么删除二叉树根结点
叉树的根节点当然可以删除啊，当左右子树都为空时，可以删除，强制性删除也可以啊，不过要从树的左子树下选一个结点来当根节点，不然，就会破坏二叉树的结构！