节点：
/*
 * 二叉树节点
 */
public class Node {
//数据项
public long data;
//数据项
public String sData;
//左子节点
public Node leftChild;
//右子节点
public Node rightChild;
/**
 * 构造方法
 * @param data
 */
public Node(long data,String sData) {
this.data = data;
this.sData = sData;
}
}
二叉树：
/*
 * 二叉树类
 */
public class Tree {
//根节点
public Node root;
/**
 * 插入节点
 * @param value
 */
public void insert(long value,String sValue) {
//封装节点
Node newNode = new Node(value,sValue);
//引用当前节点
Node current = root;
//引用父节点
Node parent;
//如果root为null，也就是第一插入的时候
if(root == null) {
root = newNode;
return;
} else {
while(true) {
//父节点指向当前节点
parent = current;
//如果当前指向的节点数据比插入的要大,则向左走
if(current.data > value) {
current = current.leftChild;
if(current == null) {
parent.leftChild = newNode;
return;
}
} else {
current = current.rightChild;
if(current == null) {
parent.rightChild = newNode;
return;
}
}
}
}
}
/**
 * 查找节点
 * @param value
 */
public Node find(long value) {
//引用当前节点，从根节点开始
Node current = root;
//循环，只要查找值不等于当前节点的数据项
while(current.data != value) {
//进行比较，比较查找值和当前节点的大小
if(current.data > value) {
current = current.leftChild;
} else {
current = current.rightChild;
}
//如果查找不到
if(current == null) {
return null;
}
}
return current;
}
/**
 * 删除节点
 * @param value
 */
public boolean delete(long value) {
//引用当前节点，从根节点开始
Node current = root;
//应用当前节点的父节点
Node parent = root;
//是否为左节点
boolean isLeftChild = true;
while(current.data != value) {
parent = current;
//进行比较，比较查找值和当前节点的大小
if(current.data > value) {
current = current.leftChild;
isLeftChild = true;
} else {
current = current.rightChild;
isLeftChild = false;
}
//如果查找不到
if(current == null) {
return false;
}
}
//删除叶子节点，也就是该节点没有子节点
if(current.leftChild == null && current.rightChild == null) {
if(current == root) {
root = null;
} else if(isLeftChild) {
parent.leftChild = null;
} else {
parent.rightChild = null;
}
} else if(current.rightChild == null) {
if(current == root) {
root = current.leftChild;
}else if(isLeftChild) {
parent.leftChild = current.leftChild;
} else {
parent.rightChild = current.leftChild;
}
} else if(current.leftChild == null) {
if(current == root) {
root = current.rightChild;
} else if(isLeftChild) {
parent.leftChild = current.rightChild;
} else {
parent.rightChild = current.rightChild;
}
} else {
Node successor = getSuccessor(current);
if(current == root) {
root = successor;
} else if(isLeftChild) {
parent.leftChild = successor;
} else{
parent.rightChild = successor;
}
successor.leftChild = current.leftChild;
}
return true;
}
public Node getSuccessor(Node delNode) {
Node successor = delNode;
Node successorParent = delNode;
Node current = delNode.rightChild;
while(current != null) {
successorParent = successor;
successor = current;
current = current.leftChild;
}
if(successor != delNode.rightChild) {
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
/**
 * 前序遍历
 */
public void frontOrder(Node localNode) {
if(localNode != null) {
//访问根节点
System.out.println(localNode.data + ", " + localNode.sData);
//前序遍历左子树
frontOrder(localNode.leftChild);
//前序遍历右子树
frontOrder(localNode.rightChild);
}
}
/**
 * 中序遍历
 */
public void inOrder(Node localNode) {
if(localNode != null) {
//中序遍历左子树
inOrder(localNode.leftChild);
//访问根节点
System.out.println(localNode.data + ", " + localNode.sData);
//中旬遍历右子树
inOrder(localNode.rightChild);
}
}
/**
 * 后序遍历
 */
public void afterOrder(Node localNode) {
if(localNode != null) {
//后序遍历左子树
afterOrder(localNode.leftChild);
//后序遍历右子树
afterOrder(localNode.rightChild);
//访问根节点
System.out.println(localNode.data + ", " + localNode.sData);
}
}
}
测试：
public class TestTree {
public static void main(String[] args) {
Tree tree = new Tree();
tree.insert(10,"James");
tree.insert(20,"YAO");
tree.insert(15,"Kobi");
tree.insert(3,"Mac");
tree.insert(4, "Zhangsan");
tree.insert(90, "Lisi");
tree.delete(90);
tree.inOrder(tree.root);
}
}


				
转载于:https://blog.51cto.com/8169085/1696870

本次的课程设计要求建立一颗二叉树，并且用中序非递归方法遍历该二叉树，然后判断该二叉树是否为二叉排序树，如果是二叉排序树的话进一步要求对结点进行插入和删除操作，并输出操作后的结果。

树结点

typedef struct node
{
    struct node *lchild;
    struct node *rchild;
    int data;
}BiTreeNode, *BiTree;

首先我们要建立一颗二叉树，这里我们采用二叉树的前序遍历序列和中序遍历序列递归地建立一颗二叉树，代码如下：

//二叉排序树测试用例
int pre[] = { 5, 3, 2, 4, 8, 6 };//前序遍历
int ino[] = { 2, 3, 4, 5, 6, 8 };//中序遍历
void BuildBTree(BiTreeNode **T, int preL, int preR, int inoL, int inoR)//递归建树
{
    if (preL>preR) return;
    int e = pre[preL];
    int root = inoL;
    while (ino[root] != e&&root <= inoR) ++root;
    (*T) = (BiTreeNode *)malloc(sizeof(BiTreeNode));
    (*T)->lchild = NULL;
    (*T)->rchild = NULL;
    (*T)->data = e;
    BuildBTree(&(*T)->lchild, preL + 1, preL + root - inoL, inoL, root - 1);
    BuildBTree(&(*T)->rchild, preL + root - inoL + 1, preR, root + 1, inoR);
}

然后定义中序非递归遍历函数，这里用辅助栈实现中序非递归遍历二叉树算法，代码如下:

void midvisit(BiTreeNode*root)
{
    //中序非递归遍历
    printf("中序遍历结果:");
    if (root)
    {
        BiTreeNode*Stack[100]; int top = -1;
        BiTreeNode*p;
        p = root;
        while (top != -1 || p)
        {
            while (p)
            {
                Stack[++top] = p;
                p = p->lchild;
            }
            if (top != -1)
            {
                p = Stack[top--];
                printf("%d", p->data);
                p = p->rchild;
            }
        }
    }
    putchar('\n');
}


为了便于对输出进行比较，顺便写了一个前序递归遍历函数，代码如下：

void previsit(BiTreeNode* t)
{
    if (t)
    {
        printf("%d", t->data);
        previsit(t->lchild);
        previsit(t->rchild);
    }
}

接下来我们要判断这颗二叉树是不是排序二叉树，算法的思想为：先对二叉树进行一次中序遍历，并且将遍历结果存储到数组中，复制该数组然后用快速排序对其进行升序排序，再比较排序前和排序后的数组是否一致，如果有一处不一致则该二叉树不是排序二叉树，如果全部一致则为二叉排序树，代码如下：

int cmp(const void*a, const void*b)
{
    return *(int*)a - *(int*)b;
}

bool IsSortTree(BiTreeNode* root)
{//判断是否是二叉排序树
    int size = 0;
    int data[MAXSIZE], sortdata[MAXSIZE];

    if (root)
    {
        BiTreeNode*Stack[100]; int top = -1;
        BiTreeNode*p;
        p = root;
        while (top != -1 || p)
        {
            while (p)
            {
                Stack[++top] = p;
                p = p->lchild;
            }
            if (top != -1)
            {
                p = Stack[top--];
                //printf("%d", p->data);
                data[size++] = p->data;
                p = p->rchild;
            }
        }
    }

    for (int i = 0; i < size; ++i)
        sortdata[i] = data[i];
    qsort(sortdata, size, sizeof(int), cmp);

    for (int i = 0; i < size; ++i)
    {
        if (sortdata[i] != data[i])
            return false;
    }
    return true;
}

接来下的两个函数实现对排序二叉树新增结点和删除结点操作。

BiTreeNode* Insert(BiTreeNode*root, int x)
{
    if (!root){
        root = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        root->data = x;
        root->lchild = root->rchild = NULL;
        }
        else{
            if (x < root->data)
                root->lchild = Insert(root->lchild, x);
            else if (x > root->data)
                root->rchild = Insert(root->rchild, x);
        }
        return root;
}
void Del(BiTree&root, int x)
{
        if (root == NULL){
            return;
        }
        if (root->data>x){
            Del(root->lchild, x);
        }
        else if (root->data<x){
            Del(root->rchild, x);
        }
        else{ //查找到了删除节点
            if (root->lchild == NULL){ //左子树为空
                BiTree tempNode = root;
                root = root->rchild;
                free(tempNode);
            }
            else if (root->rchild == NULL){ //右子树为空
                BiTree tempNode = root;
                root = root->lchild;
                free(tempNode);
            }
            else{  //左右子树都不为空
                //一般的删除策略是左子树的最大数据 或 右子树的最小数据 代替该节点(这里采用查找左子树最大数据来代替)
                BiTree tempNode = root->lchild;
                if (tempNode->rchild != NULL){
                    tempNode = tempNode->rchild;
                }
                root->data = tempNode->data;
                Del(root->lchild, tempNode->data);
            }
        }
}

这里我们定义了一个非必须的solve()函数，来实现判断二叉树是否为排序二叉树以及后续操作。

void solve(BiTreeNode*root)
{
    //如果是二叉排序树，进行结点的插入或删除。
    if (IsSortTree(root))
    {
        midvisit(root);
        Insert(root, 11); //如果是排序树，插入值11
        midvisit(root);
        Del(root, 5);//删除值为5的结点
        midvisit(root);
    }
    else
        return;//不是二叉排序树 什么也不做
}

最后就是main()函数了。。。

int main()
{
    //freopen("data.txt", "r", stdin);

    BiTreeNode*root;
    BuildBTree(&root, 0, sizeof(pre) / sizeof(pre[0])-1, 0, sizeof(ino) / sizeof(ino[0])-1);
    printf("前序遍历结果:");
    previsit(root); 
    putchar('\n');
    midvisit(root);

    if (IsSortTree(root))
        printf("YES\n");
    else
        printf("NO\n");
    solve(root);
}

完整代码代码如下：

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE (100)

typedef struct node
{
    struct node *lchild;
    struct node *rchild;
    int data;
}BiTreeNode, *BiTree;

//非二叉排序树测试用例
//int pre[] = { 1, 2, 4, 5, 3, 6, 7 };//前序序列
//int ino[] = { 4, 2, 5, 1, 6, 3, 7 };//中序序列

//二叉排序树测试用例
int pre[] = { 5, 3, 2, 4, 8, 6 };
int ino[] = { 2, 3, 4, 5, 6, 8 };
void BuildBTree(BiTreeNode **T, int preL, int preR, int inoL, int inoR)//递归建树
{
    if (preL>preR) return;
    int e = pre[preL];
    int root = inoL;
    while (ino[root] != e&&root <= inoR) ++root;
    (*T) = (BiTreeNode *)malloc(sizeof(BiTreeNode));
    (*T)->lchild = NULL;
    (*T)->rchild = NULL;
    (*T)->data = e;
    BuildBTree(&(*T)->lchild, preL + 1, preL + root - inoL, inoL, root - 1);
    BuildBTree(&(*T)->rchild, preL + root - inoL + 1, preR, root + 1, inoR);
}

void midvisit(BiTreeNode*root)
{
    //中序非递归遍历
    printf("中序遍历结果:");
    if (root)
    {
        BiTreeNode*Stack[100]; int top = -1;
        BiTreeNode*p;
        p = root;
        while (top != -1 || p)
        {
            while (p)
            {
                Stack[++top] = p;
                p = p->lchild;
            }
            if (top != -1)
            {
                p = Stack[top--];
                printf("%d", p->data);
                p = p->rchild;
            }
        }
    }
    putchar('\n');
}

void previsit(BiTreeNode* t)
{
    if (t)
    {
        printf("%d", t->data);
        previsit(t->lchild);
        previsit(t->rchild);
    }
}
int cmp(const void*a, const void*b)
{
    return *(int*)a - *(int*)b;
}

bool IsSortTree(BiTreeNode* root)
{//判断是否是二叉排序树
    int size = 0;
    int data[MAXSIZE], sortdata[MAXSIZE];

    if (root)
    {
        BiTreeNode*Stack[100]; int top = -1;
        BiTreeNode*p;
        p = root;
        while (top != -1 || p)
        {
            while (p)
            {
                Stack[++top] = p;
                p = p->lchild;
            }
            if (top != -1)
            {
                p = Stack[top--];
                //printf("%d", p->data);
                data[size++] = p->data;
                p = p->rchild;
            }
        }
    }

    for (int i = 0; i < size; ++i)
        sortdata[i] = data[i];
    qsort(sortdata, size, sizeof(int), cmp);

    for (int i = 0; i < size; ++i)
    {
        if (sortdata[i] != data[i])
            return false;
    }
    return true;
}
BiTreeNode* Insert(BiTreeNode*root, int x)
{
    if (!root){
        root = (BiTreeNode*)malloc(sizeof(BiTreeNode));
        root->data = x;
        root->lchild = root->rchild = NULL;
        }
        else{
            if (x < root->data)
                root->lchild = Insert(root->lchild, x);
            else if (x > root->data)
                root->rchild = Insert(root->rchild, x);
        }
        return root;
}
void Del(BiTree&root, int x)
{
        if (root == NULL){
            return;
        }
        if (root->data>x){
            Del(root->lchild, x);
        }
        else if (root->data<x){
            Del(root->rchild, x);
        }
        else{ //查找到了删除节点
            if (root->lchild == NULL){ //左子树为空
                BiTree tempNode = root;
                root = root->rchild;
                free(tempNode);
            }
            else if (root->rchild == NULL){ //右子树为空
                BiTree tempNode = root;
                root = root->lchild;
                free(tempNode);
            }
            else{  //左右子树都不为空
                //一般的删除策略是左子树的最大数据 或 右子树的最小数据 代替该节点(这里采用查找左子树最大数据来代替)
                BiTree tempNode = root->lchild;
                if (tempNode->rchild != NULL){
                    tempNode = tempNode->rchild;
                }
                root->data = tempNode->data;
                Del(root->lchild, tempNode->data);
            }
        }
}

void solve(BiTreeNode*root)
{
    //如果是二叉排序树，进行结点的插入或删除。
    if (IsSortTree(root))
    {
        midvisit(root);
        Insert(root, 11); //如果是排序树，插入值11
        midvisit(root);
        Del(root, 5);//删除值为5的结点
        midvisit(root);
    }
    else
        return;//不是二叉排序树 什么也不做
}
int main()
{
    //freopen("data.txt", "r", stdin);

    BiTreeNode*root;
    BuildBTree(&root, 0, sizeof(pre) / sizeof(pre[0])-1, 0, sizeof(ino) / sizeof(ino[0])-1);
    printf("前序遍历结果:");
    previsit(root); 
    putchar('\n');
    midvisit(root);

    if (IsSortTree(root))
        printf("YES\n");
    else
        printf("NO\n");
    solve(root);
}

 

一、二叉树删除节点的思路图解

二、二叉树删除节点的示例代码
1、代码
package com.rf.springboot01.dataStructure.tree;

/**
 * @description: 二叉树删除节点示例
 * @author: xiaozhi
 * @create: 2020-08-28 21:07
 */
public class BinaryTreeDemoThree {
    public static void main(String[] args) {
        //创建二叉树
        BinaryTree1 binaryTree1 = new BinaryTree1();
        //创建需要的结点
        UsersNode root = new UsersNode(1,"张三");
        UsersNode node2 = new UsersNode(2, "李四");
        UsersNode node3 = new UsersNode(3, "王五");
        UsersNode node4 = new UsersNode(4, "小志");
        UsersNode node5 = new UsersNode(5, "Tom");
        //手动创建该二叉树
        binaryTree1.setRoot(root);//创建根节点
        root.setLeft(node2);//创建根节点左边子节点
        root.setRight(node3);//创建根节点右边子节点
        node3.setRight(node4);//创建根节点右边子节点的右边子节点
        node3.setLeft(node5);//创建根节点右边子节点的左边子节点

        System.out.println("删除前，前序遍历结果如下===============");
        binaryTree1.preOrder();//输出的no的顺序为1,2,3,5,4
        binaryTree1.delNode(3);
        System.out.println("删除后，前序遍历结果如下===============");
        binaryTree1.preOrder();//输出的no的顺序为1,2

    }
}
/**
 * @Description: 创建BinaryTree1 二叉树
 * @Param:
 * @Author: xz
 * @return:
 * @Date: 2020-08-28 21:15
 */
class BinaryTree1{
    private UsersNode root;

    public void setRoot(UsersNode root) {
        this.root = root;
    }

    //前序遍历方法
    public void preOrder(){
        if(root !=null){
            this.root.preOrder();
        }else{
            System.out.println("二叉树为空，无法遍历");
        }
    }
    //删除结点
    public void delNode(int no) {
        if(root != null) {
            //如果只有一个root结点, 这里立即判断root是不是就是要删除结点
            if(root.getNo() == no) {
                root = null;
            } else {
                //递归删除
                root.deleteNode(no);
            }
        }else{
            System.out.println("空树，不能删除~");
        }
    }

}
/**
 * @Description: 先创建UserNode结点类
 * @Author: xz
 * @Date: 2020-08-28 21:10
 */
class UsersNode{

    private int no;
    private String name;
    private UsersNode left;//左节点，默认为null
    private UsersNode right;//左节点，默认为null

    public UsersNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public UsersNode getLeft() {
        return left;
    }

    public void setLeft(UsersNode left) {
        this.left = left;
    }

    public UsersNode getRight() {
        return right;
    }

    public void setRight(UsersNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "UsersNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    //前序遍历方法
    public void preOrder(){
        //先输出父节点
        System.out.println(this);
        //递归向左子树前序遍历
        if(this.left != null){
            this.left.preOrder();
        }
        //递归向右子树前序遍历
        if(this.right != null){
            this.right.preOrder();
        }
    }
    //删除节点方法
    public void deleteNode(int no){
        //如果当前节点的左子节点不为空，并且左子节点就是要删除节点，就将this.left=null; 并且返回(结束递归删除)
        if(this.left != null && this.left.no == no){
            this.left=null;
            return;
        }
        //如果当前节点的右子节点不为空，并且右子节点就是要删除节点，就将this.right=null;并且返回(结束递归删除)
        if(this.right != null && this.right.no == no){
            this.right=null;
            return;
        }
        //要向左子树进行递归删除
        if(this.left !=null){
            this.left.deleteNode(no);
        }
        //向右子树进行递归删除
        if(this.right !=null){
            this.right.deleteNode(no);
        }
    }


}


2、删除节点5的运行结果如下：



3、删除节点3的运行结果如下：

算法第四版习题2.4.24： 用堆有序的二叉树实现一个优先队列，但使用链表结构，每个结点需要三个链接：两个向下，一个向上。要求算法基本操作所需时间为对数级。

二叉树如图：


此算法实现的主要步骤：

1.将新元素插入到最末结点之后，并上浮到合适位置

2. 从二叉树顶端删除最大元素，并将最末结点放到顶端，并下沉顶结点。

此算法的难点在于如何定位最末结点向后一位的结点
一、沈星繁博客中提出的解决办法
维护一个指向最末结点的指针，通过向上回溯来找下一位结点，如图：



具体步骤为：

1.向上回溯一层，判断回溯方向：若为自左路回溯，则右路为后一位结点；若为右路回溯，转为第2步。

2.继续向上回溯，直到回溯方向为左路，然向向右下一层，再沿左路下到底。

3.若向上回溯一直为右路，则会回到顶结点，自顶结点一路向左下到底即可。

此算法逻辑较复杂，而且还要判断回溯方向。具体实现代码可参见下面链接: 沈星繁-算法2.4.
二、我的巧妙算法：
查找某序号结节位置（序号从1开始，自上而下自左到右顺序编号），对于二叉树来说，结点数为N，其下一位就是序号N+1的结点位置。具体查找方法如下：

1.先将序号转为二进制数。

2.此二进制数的位数代表二叉树的层数。自左向右分别为顶结点-2层结点-3层结点-4层结点。除第1位顶结点外，其余每位0代表左结点，1代表右结点。

比如要定位10号结点，先转为二进制为“1010”，定位顺序为：顶结点->左->右->左

此算法遍历的结节数为树的层数，正好为lgN对数级。

代码如下：
public Node seekNode(int x) {
						
		String s = Integer.toBinaryString(x);
		
		Node seek = top;		
		for(int i =1; i<s.length(); i++) {
			
			if(s.charAt(i)=='0') seek = seek.left;
			else seek = seek.right;
		}
		return seek;
		
	}

逻辑清晰，简单高效！