Fulongのblog

二叉排序树

2018/03/30 Algorithms 共 9173 字，约 27 分钟

参考文章

定义一个二叉排序树结构：

typedef int DataType;
typedef struct BST_Node {
    DataType data;
    struct BST_Node *lchild, *rchild;
}BST_T, *BST_P;

建立二叉排序树，用到Insert_BST方法，在后面：

void CreateBST(BST_P *T, int a[], int n)
{
    int i;
    for (i = 0; i < n; i++)
    {
        Insert_BST(T, a[i]);
    }
}

二叉排序树查找

要在二叉树中找出查找最大最小元素是极简单的事情，从根节点一直往左走，直到无路可走就可得到最小值；从根节点一直往右走，直到无路可走，就可以得到最大值。

查找最小关键字：

BST_P SearchMin(BST_P root)
{
    if (root == NULL)
        return NULL;
    if (root->lchild == NULL)
        return root;
    else  //一直往左孩子找，直到没有左孩子的结点  
        return SearchMin(root->lchild);
}

查找最大关键字：

BST_P SearchMax(BST_P root)
{
    if (root == NULL)
        return NULL;
    if (root->rchild == NULL)
        return root;
    else  //一直往右孩子找，直到没有右孩子的结点  
        return SearchMax(root->rchild);
}

递归版查找（找到返回关键字的结点指针，没找到返回NULL）：

BST_P Search_BST(BST_P root, DataType key)
{
    if (root == NULL)
        return NULL;
    if (key > root->data) //查找右子树  
        return Search_BST(root->rchild, key);
    else if (key < root->data) //查找左子树  
        return Search_BST(root->lchild, key);
    else
        return root;
}

非递归版查找：

BST_P Search_BST(BST_P root, DataType key)
{
    BST_P p = root;
    while (p) 
    {       
        if (p->data == key)  return p;
        p = (key < p->data) ? p->lchild : p->rchild;
    }
    return NULL;
}

二叉排序树插入

插入新元素时，可以从根节点开始，遇键值较大者就向左，遇键值较小者就向右，一直到末端，就是插入点。

void Insert_BST(BST_P *root, DataType data)
{
    //初始化插入节点
    BST_P p = (BST_P)malloc(sizeof(struct BST_Node));
    if (!p) return;
    p->data = data;
    p->lchild = p->rchild = NULL;

    //空树时，直接作为根节点
    if (*root == NULL)
    {
        *root = p;
        return;
    }

    //是否存在，已存在则返回，不插入
    if (Search_BST(root, data) != NULL) return; 

    //进行插入，首先找到要插入的位置的父节点
    BST_P tnode = NULL, troot = *root;
    while (troot)
    {       
        tnode = troot;
        troot = (data < troot->data) ? troot->lchild : troot->rchild;
    }
    if (data < tnode->data)
        tnode->lchild = p;
    else
        tnode->rchild = p;
}

# 递归插入
def insertTreeNode(root, val) -> TreeNode:
    if root is None:
        root = TreeNode()
        root.val = val
        return root
    elif root.val == val:
        return root
    elif root.val < val:
        root.right = insertTreeNode(root.right, val)
        return root
    else:
        root.left = insertTreeNode(root.left, val)
        return root
    return root
if __name__ == '__main__':
    root = None
    root = insertTreeNode(root, 2)
    root = insertTreeNode(root, 1)
    root = insertTreeNode(root, 1)
    root = insertTreeNode(root, 4)
    root = insertTreeNode(root, 5)
    root = insertTreeNode(root, 3)

二叉排序树删除

简单方法

二叉树的删除操作有一个技巧, 即在查找到需要删除的节点 X; 接着我们找到要么在它的左子树中的最大元素节点 M、要么在它的右子树中的最小元素节点 M, 并交换(M,X). 此时, M 节点必然至多只有一个孩子; 最后一个步骤就是用 M 的子节点代替 M 节点就完成了. 所以, 所有的删除操作最后都会归结为删除一个至多只有一个孩子的节点, 而我们删除这个节点后, 用它的孩子替换就好了

    public Node deleteNode(Node root,int a){
        if(root==null)
            return null;
        if(root.data==a){
            if(root.left==null){
                return root.right;
            }else if(root.right==null){
                return root.left;
            }else{
                Node t=root.right;
                while (t.left!=null){
                    t=t.left;
                }
                int b=root.data;
                root.data=t.data;
                t.data=b;
                root.right=deleteNode(root.right,a);
            }
        }else if(root.data<a){
            root.right=deleteNode(root.right,a);
        }else{
            root.left=deleteNode(root.left,a);
        }
        return root;
    }


def deleteTreeNode(root: TreeNode, val):
    if root is None:
        return
    if root.val == val:
        if root.left is None and root.right is None:
            return None
        elif root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        else:
            replaceNode = root.right
            while replaceNode.left is not None:
                replaceNode = replaceNode.left
            root.val, replaceNode.val = replaceNode.val, root.val
            root.right = deleteTreeNode(root.right, val)
    elif root.val < val:
        root.right = deleteTreeNode(root.right, val)
    elif root.val > val:
        root.left = deleteTreeNode(root.left, val)
    return root

一般方法

对于二叉排序树中的节点A，对它的删除分为两种情况：

  1. 如果A只有一个子节点，就直接将A的子节点连至A的父节点上，并将A删除；
  2. 如果A有两个子节点，我们就以右子树内的最小节点取代A，怎么得最小节点，前有有说。这个最小节点肯定没有左孩子，将右孩子赋值给它的父母
  3. 如果是叶子节点，直接赋值为NULL就好了
void DeleteBSTNode(BST_P *root, DataType data)
{
    BST_P p = *root, parent = NULL, s = NULL;

    if (!p) return;

    if (p->data == data) //找到要删除的节点了
    {
        /* It's a leaf node */
        if (!p->rchild && !p->lchild) 
            *root = NULL;

        // 只有一个左节点
        else if (!p->rchild&&p->lchild) 
            *root = p->lchild;

        // 只有一个右节点
        else if (!p->lchild&&p->rchild) 
            *root = p->rchild;

        //左右节点都不空
        else 
        {
            s = p->rchild;
            /* the s without left child */
            if (!s->lchild)
                s->lchild = p->lchild;
            /* the s have left child */
            else 
            {
                /* find the smallest node in the left subtree of s */
                while (s->lchild) 
                {
                    /* record the parent node of s */
                    parent = s;
                    s = s->lchild;
                }
                parent->lchild = s->rchild;
                s->lchild = p->lchild;
                s->rchild = p->rchild;
            }
            *root = s;
        }
        free(p);
    }
    else if (data > p->data) //向右找
        DeleteBSTNode(&(p->rchild), data);
    else if (data < p->data) //向左找
        DeleteBSTNode(&(p->lchild), data);
}

二叉树遍历

void MidOrderTraverse(BST_P T)
{
    if (T)
    {
        MidOrderTraverse(T->lchild);
        cout << T->data << " ";
        MidOrderTraverse(T->rchild);
    }
}

void PreOrderTraverse(BST_P T)
{
    if (T)
    {
        cout << T->data << " ";
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}

void PostOrderTraverse(BST_P T)
{
    if (T)
    {
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        cout << T->data << " ";
    }
}

测试

int main()
{
    int arr[] = { 17,12,19,10,15,18,25,8,11,13,16,22};  

    BST_P root = NULL;

    //创建二叉排序树
    CreateBST(&root, arr, 12);
    printf("\nCreate BST: ");
    printf("\npre order traverse: ");
    PreOrderTraverse(root);
    printf("\npost order traverse: ");
    PostOrderTraverse(root);
    cout << endl;

    //在二叉排序树中查找节点12.
    BST_P result = Search_BST(root, 12);
    printf("\nSearch Data: ");
    cout << "查找结果：\n" << "指针：" << result << endl << "指针的值：" << result->data << endl;

    //在二叉排序树中插入9
    Insert_BST(&root, 9);
    printf("\nInsert Data: ");
    printf("\npre order traverse: ");
    PreOrderTraverse(root);
    printf("\npost order traverse: ");
    PostOrderTraverse(root);
    cout << endl;

    //删除二叉排序树中的节点12
    DeleteBSTNode(&root, 12);
    printf("\nDelete Data: ");
    printf("\npre order traverse: ");
    PreOrderTraverse(root);
    printf("\npost order traverse: ");
    PostOrderTraverse(root);
    printf("\n");
}

自己复习又写一遍的全部代码

#include<algorithm>
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<queue>
using namespace std;


struct t
{
	int data;
	t *left, *right;
	t():left(NULL),right(NULL){
		
	}
	t(int d) :data(d),left(NULL), right(NULL){

	}
};

t* searchMin(t *root) {
	if (root == NULL) {
		return NULL;
	}
	if (root->left == NULL) {
		return root;
	}
	else {
		return searchMin(root->left);
	}
}
t* searchMax(t *root) {
	if (root == NULL) {
		return NULL;
	}
	if (root->right == NULL) {
		return root;
	}
	else {
		return searchMax(root->right);
	}
}

t* searchKey(t *root, int key) {
	if (root == NULL) {
		return NULL;
	}
	if (root->data == key) {
		return root;
	}
	if (key>root->data) {
		searchKey(root->right, key);
	}
	else {
		searchKey(root->left, key);
	}
}
t* searchKey1(t *root, int key) {
	if (root == NULL) {
		return NULL;
	}
	t *p = root;
	while (p) {
		if (p->data == key) {
			return p;
		}
		if (key > p->data) {
			p = p->right;
		}
		else {
			p = p->left;
		}
	}
	return NULL;
}
void insertNode(t *&root, int data);
t* createTree(vector<int> v) {
	t *root =NULL;
	for (int i = 0; i < v.size(); i++) {
		insertNode(root, v[i]);
	}
	return root;
}

void insertNode(t *&root, int data) {
	t *p = new t(data);
	if (root == NULL) {
		root = p;
		return;
	}
	//找它的父节点
	if (searchKey(root, data)) {
		//里面有这个节点就别插了
		return;
	}
	t *father = NULL;
	t *t1 = root;
	while (t1) {
		father = t1;
		t1 = data > t1->data ? t1->right : t1->left;
	}
	if (data > father->data)
		father->right = p;
	else
		father->left = p;

	//while
}


void deleteNode(t *&root, int data) {
	if (root == NULL) {
		return;
	}
	if (root->data == data) {
		if (root->left == NULL && root->right == NULL) {
			root = NULL;
		}else if (root->left == NULL &&root->right!=NULL) {
			root = root->right;
		}else if (root->right == NULL && root->left != NULL) {
			root = root->left;
		}
		else {
			if (!root->right->left) {
				t *p = root;
				root->right->left = root->left;	
				root = root->right;
				delete p;
			}
			else {
				t *t2, *t3=NULL;
				t2 = root->right;
				while (t2->left) {
					t3 = t2;
					t2 = t2->left;
				}
				t3->left = t2->right;
				t2->left = root->left;
				t2->right = root->right;
				t *p = root;
				root = t2;
				delete p;

			}
		}
	}
	else if (data > root->data) {
		deleteNode(root->right, data);
	}
	else if (data < root->data) {
		deleteNode(root->left, data);
	}

}

void visitlvr(t *root) {
	if (root != NULL) {
		visitlvr(root->left);
		cout << root->data << " ";
		visitlvr(root->right);
	}
}
void visitvlr(t *root) {
	if (root != NULL) {
		cout << root->data << " ";
		visitvlr(root->left);
		visitvlr(root->right);
	}
}
void visitlrv(t *root) {
	if (root != NULL) {
		visitlrv(root->left);
		visitlrv(root->right);
		cout << root->data << " ";
	}
}
void visitTree(t *tree) {
	visitlvr(tree);
	cout << endl;
	visitvlr(tree);
	cout << endl;
	visitlrv(tree);
	cout << endl;
}
int main() {
	freopen("D:/in.txt", "r", stdin);

	vector<int> v;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		v.push_back(a);
	}
	t* tree=createTree(v);
	visitTree(tree);

	deleteNode(tree, 7);
	visitTree(tree);
	return 0;
}

floor()

floor(key)：小于等于键的最大键

如果键小于根节点的键，那么 floor(key) 一定在左子树中；

如果键大于根节点的键，需要先判断右子树中是否存在 floor(key)，如果存在就找到，否则根节点就是 floor(key)。

public Key floor(Key key) {
    Node x = floor(root, key);
    if (x == null)
        return null;
    return x.key;
}

private Node floor(Node x, Key key) {
    if (x == null)
        return null;
    int cmp = key.compareTo(x.key);
    if (cmp == 0)
        return x;
    if (cmp < 0)
        return floor(x.left, key);
    Node t = floor(x.right, key);
    return t != null ? t : x;
}

rank()

rank(key) 返回 key 的排名。

如果键和根节点的键相等，返回左子树的节点数；
如果小于，递归计算在左子树中的排名；
如果大于，递归计算在右子树中的排名，并加上左子树的节点数，再加上 1（根节点）。

@Override
public int rank(Key key) {
    return rank(key, root);
}

private int rank(Key key, Node x) {
    if (x == null)
        return 0;
    int cmp = key.compareTo(x.key);
    if (cmp == 0)
        return size(x.left);
    else if (cmp < 0)
        return rank(key, x.left);
    else
        return 1 + size(x.left) + rank(key, x.right);
}

deleteMin()

令指向最小节点的链接指向最小节点的右子树。

public void deleteMin() {
    root = deleteMin(root);
}

public Node deleteMin(Node x) {
    if (x.left == null)
        return x.right;
    x.left = deleteMin(x.left);
    recalculateSize(x);
    return x;
}

Search

    Table of Contents

    Popular Posts