두 갈래 정렬 트 리 의 결점 삭제
13323 단어 데이터 구조
8
3 9
2 6 10
1 4 7
5
위 에는 1 부터 10 까지 의 이 진 트 리 가 있다.어떻게 이 진 트 리 의 노드 삭 제 를 실현 합 니까?만약 에 우리 가 결점 6 을 삭제 하면 먼저 전구 결점 이나 후계 노드 를 찾 습 니 다. 6 의 전구 결점 은 5 이 고 후계 가 7 입 니 다. 결점 6 을 삭제 한 후에 나 무 는 어떻게 변화 해 야 하 는 지 상상 해 보 세 요.사실 6 을 5 로 바 꾸 고 5 의 노드 를 삭제 하면 된다.
전구 나 후계 의 도 는 1 또는 0 이 므 로 주의 하 세 요.
(PS: 이 건 마늘 손님 에 게 서 배 운 것 이지 광 고 를 하 는 것 이 아니 라 권리 침해 하면 삭제 합 니 다)
#include <iostream>
#include <cstdlib>
using namespace std;
class Node
{
public:
int data;
Node *lchild, *rchild, *father;
Node(int _data, Node*_father=NULL){
data = _data;
lchild = NULL;
rchild = NULL;
father = _father;
}
~Node(){
if(lchild != NULL)
delete lchild;
if(rchild != NULL)
delete rchild;
}
void myInsert(int value){
if(data == value)
return;
else if(value < data){
if(lchild == NULL)
lchild = new Node(value, this);
else
lchild->myInsert(value);
}
else{
if(rchild == NULL)
rchild = new Node(value, this);
else
rchild->myInsert(value);
}
}
Node *mySearch(int value){
if(data == value)
return this;
else if(value < data){
if(lchild == NULL)
return NULL;
else
lchild->mySearch(value);
}
else{
if(rchild == NULL)
return NULL;
else
rchild->mySearch(value);
}
}
/* */
Node *predecessor(){
Node *temp = lchild;
while(temp!=NULL && temp->rchild!=NULL){
temp = temp->rchild;
}
return temp;
}
/* */
Node *successor(){
Node *temp = rchild;
while(temp!=NULL && temp->lchild!=NULL){
temp = temp->lchild;
}
return temp;
}
/* 1 0 */
void removeNode(Node *nodeOfdelete){
/* temp NULL*/
Node *temp = NULL;
if(nodeOfdelete->lchild != NULL){
temp = nodeOfdelete->lchild;
/* */
temp->father = nodeOfdelete->father;
/* lchild rchild NULL, Node */
nodeOfdelete->lchild = NULL;
}
if(nodeOfdelete->rchild != NULL){
temp = nodeOfdelete->rchild;
temp->father = nodeOfdelete->father;
nodeOfdelete->rchild = NULL;
}
/* if , if */
if(nodeOfdelete->father->lchild == nodeOfdelete)
nodeOfdelete->father->lchild = temp;
if(nodeOfdelete->father->rchild == nodeOfdelete)
nodeOfdelete->father->rchild = temp;
delete nodeOfdelete;
}
bool deleteNode(int value){
Node *currentNode, *nodeOfdelete;
currentNode = mySearch(value);
if(currentNode == NULL)
return false;
/* */
if(currentNode->lchild != NULL)
nodeOfdelete = currentNode->predecessor();
/* */
else if(currentNode->rchild != NULL)
nodeOfdelete = currentNode->successor();
/* */
else
nodeOfdelete = currentNode;
/* data */
currentNode->data = nodeOfdelete->data;
/* 1 , , remove */
removeNode(nodeOfdelete);
return true;
}
void inOrder(){
if(lchild != NULL)
lchild->inOrder();
cout<<data<<" ";
if(rchild != NULL)
rchild->inOrder();
}
};
class BinaryTree
{
private:
Node *root;
public:
BinaryTree(){
root = NULL;
}
~BinaryTree(){
if(root != NULL)
delete root;
}
void myInsert(int value){
if(root == NULL)
root = new Node(value);
else
root->myInsert(value);
}
void mySearch(int value){
if(root->mySearch(value) != NULL)
cout << " " <<endl;
else
cout << " " << endl;
}
void deleteNode(int value){
if(root->deleteNode(value))
cout << " " <<endl;
else
cout << " " <<endl;
}
void inOrder(){
if(root != NULL)
root->inOrder();
}
};
int main(){
BinaryTree binarytree;
int arr[] = {-111, 0, 22, 4, 3, 8, -2, -11, 123, 2333, 44, 9, 100};
for(int i=0; i<13; i++)
binarytree.myInsert(arr[i]);
binarytree.inOrder();
cout<
질문 이나 오류 가 있 으 시 면 환영 합 니 다. 감사합니다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.