post 相等 大于 truct art parent node -m
二叉排序树的插入与删除可能会破坏二叉排序树的性质,如今要求插入和删除操作保持其性质
二叉排序树或者是一棵空树,或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上全部结点的值均小于它的根结点的值; (2)若右子树不空。则右子树上全部结点的值均大于或等于它的根结点的值; (3)左、右子树也分别为二叉排序树; (4)没有键值相等的节点。
欢迎大家指错或提出改进意见
- #include "stdafx.h"
- #include<iostream>
- using namespace std;
- struct BiNOde
- {
- int ele;
- BiNOde* lnode;
- BiNOde* rnode;
- };
- BiNOde* nearnode = NULL;
- int min = 100000;
- BiNOde*tobedeleted = NULL;
- BiNOde*parentoftobedeleted = NULL;
- BiNOde*create_tree()
- {
- BiNOde * root = new BiNOde;
- BiNOde*node1 = new BiNOde;
- BiNOde*node2 = new BiNOde;
- BiNOde*node3 = new BiNOde;
- BiNOde*node4 = new BiNOde;
- BiNOde*node5 = new BiNOde;
- BiNOde*node6 = new BiNOde;
- BiNOde*node7 = new BiNOde;
- BiNOde*node8 = new BiNOde;
- BiNOde*node9 = new BiNOde;
- BiNOde*node10 = new BiNOde;
- BiNOde*node11 = new BiNOde;
- BiNOde*node12 = new BiNOde;
- root->ele = 45;
- node1->ele = 38;
- node2->ele = 55;
- node3->ele = 33;
- node4->ele = 41;
- node5->ele = 19;
- node6->ele = 16;
- node7->ele = 52;
- node8->ele = 58;
- node9->ele = 50;
- node10->ele = 44;
- node11->ele = 35;
- node12->ele = 42;
- root->lnode = node1;
- root->rnode = node2;
- node1->lnode = node3;
- node1->rnode = node4;
- node2->lnode = node7;
- node2->rnode = node8;
- node3->lnode = node5;
- node3->rnode = NULL;//node11;
- node4->rnode = node10;
- node4->lnode = NULL;
- node5->lnode = node6;
- node5->rnode = NULL;
- node6->lnode = NULL;
- node6->rnode = NULL;
- node7->lnode = node9;
- node7->rnode = NULL;
- node8->lnode = NULL;
- node8->rnode = NULL;
- node9->lnode = NULL;
- node9->rnode = NULL;
- node10->lnode = node12;
- node10->rnode = NULL;
- node11->lnode = NULL;
- node11->rnode = NULL;
- //BiNOde*node12 = new BiNOde;
- //node12->ele = 12;
- node12->lnode = NULL;
- node12->rnode = NULL;
- //node6->lnode = node11;
- return root;
- }
- void find(BiNOde*node, int value)
- {
- if (node == NULL)
- return;
- int k = node->ele - value;
- if (k > 0)
- if (k < min)
- {
- min = k;
- nearnode = node;
- }
- find(node->lnode, value);
- find(node->rnode, value);
- }
- BiNOde*insert(BiNOde*root, int value)
- {
- BiNOde* p = new BiNOde;
- p->ele = value;
- BiNOde*n;
- find(root, value);
- n = nearnode->lnode;
- nearnode->lnode = p;
- p->lnode = n;
- p->rnode = NULL;
- return root;
- }
- void searchnode(BiNOde*root, int value)
- {
- tobedeleted = root;
- while (tobedeleted->ele != value)
- {
- parentoftobedeleted = tobedeleted;
- if (tobedeleted->ele > value)
- tobedeleted = tobedeleted->lnode;
- else
- tobedeleted = tobedeleted->rnode;
- }
- }
- BiNOde*delete_node(BiNOde*root, int value)
- {
- BiNOde*minnode, *maxnode, *nn = NULL;
- searchnode(root, value);
- if (tobedeleted == root)
- {
- if (root->lnode == NULL)
- {
- root = root->rnode;
- delete tobedeleted;
- return root;
- }
- maxnode = root->lnode;
- if (maxnode->rnode == NULL)
- {
- maxnode->rnode = root->rnode;
- root = maxnode;
- delete tobedeleted;
- return root;
- }
- while (maxnode->rnode != NULL)
- {
- nn = maxnode;
- maxnode = maxnode->rnode;
- }
- nn->rnode = maxnode->lnode;
- maxnode->lnode = root->lnode;
- maxnode->rnode = root->rnode;
- root = maxnode;
- delete tobedeleted;
- return root;
- }
- if (tobedeleted->lnode == NULL&&tobedeleted->rnode == NULL)
- {
- if (parentoftobedeleted->lnode == tobedeleted)
- {
- parentoftobedeleted->lnode = NULL;
- delete tobedeleted;
- return root;
- }
- else
- {
- parentoftobedeleted->rnode = NULL;
- delete tobedeleted;
- return root;
- }
- }
- if (tobedeleted->lnode == NULL)
- {
- minnode = tobedeleted->rnode;
- if (minnode->lnode != NULL)
- {
- while (minnode->lnode != NULL)
- {
- nn = minnode;
- minnode = minnode->lnode;
- }
- nn->lnode = minnode->rnode;
- }
- if (parentoftobedeleted->lnode == tobedeleted)
- {
- parentoftobedeleted->lnode = minnode;
- }
- else
- {
- parentoftobedeleted->rnode = minnode;
- }
- if (minnode != tobedeleted->rnode)
- minnode->rnode = tobedeleted->rnode;
- delete tobedeleted;
- return root;
- }
- maxnode = tobedeleted->lnode;
- if (maxnode->rnode != NULL)
- {
- while (maxnode->rnode != NULL)
- {
- nn = maxnode;
- maxnode = maxnode->rnode;
- }
- nn->rnode = maxnode->lnode;
- }
- if (parentoftobedeleted->lnode == tobedeleted)
- {
- parentoftobedeleted->lnode = maxnode;
- }
- else
- {
- parentoftobedeleted->rnode = maxnode;
- }
- if (maxnode != tobedeleted->lnode)
- {
- maxnode->lnode = tobedeleted->lnode;
- maxnode->rnode = tobedeleted->rnode;
- }
- else
- {
- maxnode->rnode = tobedeleted->rnode;
- }
- delete tobedeleted;
- return root;
- }
- int _tmain(int argc, _TCHAR* argv[])
- {
- BiNOde*root = create_tree();
- //insert(root, 37);
- root = delete_node(root, 38);
- cout << root->ele << endl;
- system("pause");
- return 0;
- }
二叉排序树的插入与删除
来源: http://www.bubuko.com/infodetail-2129374.html