㈠ 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}
㈩ 怎麼刪除二叉樹根結點
怎麼刪除二叉樹根結點
叉樹的根節點當然可以刪除啊，當左右子樹都為空時，可以刪除，強制性刪除也可以啊，不過要從樹的左子樹下選一個結點來當根節點，不然，就會破壞二叉樹的結構！