데이터 구조 (7) - 균형 이 진 트 리
25120 단어 데이터 구조
//BinTree.h
#ifndef BINTREE_H_
#define BINTREE_H_
#define ElemType int
typedef struct _PNode
{
ElemType data;
_PNode *left;
_PNode *right;
int height;
}PNode;
class BinTree
{
private:
PNode *root;
public:
BinTree();
~BinTree();
PNode* GetRoot(); //
void SetRoot(PNode *p) { root = p; } //
PNode* Find(ElemType x , PNode *p); // x
PNode* FindMin(PNode *p); //
PNode* FindMax(PNode *p); //
PNode* Insert(ElemType x, PNode *p); // ，
PNode* Delete(ElemType x, PNode *p); //
//
void PreOrder(PNode *p); //
void CenOrder(PNode *p); //
void Trave(PNode *p); //
int GetHeight(PNode *p);
PNode* AVL_Insertion(ElemType x, PNode *p);
PNode* SingleLeftRotation(PNode *p); //
PNode* DoubleLeftRightRotation(PNode *p); //
PNode* SingleRightRotation(PNode *p); //
PNode* DoubleRightLeftRotation(PNode *p); //
int Max(int a, int b); //
};
#endif
/////////////////////////////////////////////////////////////////////
//BinTree.cpp
#include "BinTree.h"
#include <iostream>
#include <queue>
BinTree::BinTree()
{
root = NULL;
}
BinTree::~BinTree(){}
PNode* BinTree::GetRoot()
{
return root;
}
PNode* BinTree::Find(ElemType x, PNode *p)
{
/*
//
if (p == NULL)
return NULL;
if (x > p->data)
return Find(x, p->right);
else if (x < p->data)
return Find(x, p->left);
else
return p;*/
while (p != NULL)
{
if (x > p->data)
p = p->right;
else if (x < p->data)
p = p->left;
else
return p;
}
return NULL;
}
PNode* BinTree::FindMin(PNode *p)
{
//
if (p == NULL)
return NULL;
else if (p->left == NULL)
return p;
else
return FindMin(p->left);
}
PNode* BinTree::FindMax(PNode *p)
{
if (p != NULL)
while (p->right != NULL)
p = p->right;
return p;
}
//
void BinTree::PreOrder(PNode *p)
{
if (p == NULL)
return;
std::cout << p->data << " ";
PreOrder(p->left);
PreOrder(p->right);
}
void BinTree::CenOrder(PNode *p)
{
if (p == NULL)
return;
CenOrder(p->left);
std::cout << p->data << " ";
CenOrder(p->right);
}
PNode* BinTree::Insert(ElemType x, PNode *p)
{
if (p == NULL)
{
p = new PNode();
p->data = x;
p->left = p->right = NULL;
}
else
{
if (x < p->data)
p->left = Insert(x, p->left);
else if (x > p->data)
p->right = Insert(x, p->right);
}
return p;
}
PNode* BinTree::Delete(ElemType x, PNode *p)
{
PNode *tmp;
if (p == NULL)
std::cout << " " << std::endl;
else if (x < p->data) //
p->left = Delete(x, p->left);
else if (x > p->data)
p->right = Delete(x, p->right);
else
{
// ,
if (p->left != NULL && p->right != NULL)
{
tmp = FindMin(p->right); //
p->data = tmp->data; //
p->right = Delete(p->data, p->right); //
}
else
{// ， ，
tmp = p;
if (p->left == NULL) // ，
p = p->right;
else if(p->right == NULL) // ，
p = p->left;
delete tmp; // ，
}
}
return p;
}
void BinTree::Trave(PNode *p) //
{
std::queue<PNode*> q;
q.push(p);
while (!q.empty())
{
PNode *s = q.front();
std::cout << s->data << " ";
if (s->left != NULL)
q.push(s->left);
if (s->right != NULL)
q.push(s->right);
q.pop();
}
}
int BinTree::GetHeight(PNode *p)
{
int hl;
int hr;
int maxh;
if (p)
{
hl = GetHeight(p->left);
hr = GetHeight(p->right);
maxh = (hl > hr) ? hl : hr;
return (maxh + 1);
}
else
return -1;
}
PNode* BinTree::AVL_Insertion(ElemType x, PNode *p)
{
// x AVL T ， AVL
if (p == NULL) // ，
{
p = new PNode();
p->data = x;
p->height = 0;
p->left = p->right = NULL;
}
else if (x < p->data) // T
{
p->left = AVL_Insertion(x, p->left);
if (GetHeight(p->left) - GetHeight(p->right) == 2)
if (x < p->left->data) //
p = SingleLeftRotation(p); //
else
p = DoubleLeftRightRotation(p); //
} //
else if (x > p->data)
{
p->right = AVL_Insertion(x, p->right);
if (GetHeight(p->right) - GetHeight(p->left) == 2)
if (x > p->right->data) //
p = SingleRightRotation(p); //
else
p = DoubleRightLeftRotation(p); //
}
//x == p->data
p->height = Max(GetHeight(p->left), GetHeight(p->right)) + 1;
return p;
}
int BinTree::Max(int a, int b)
{
return (a > b ? a : b);
}
PNode* BinTree::SingleLeftRotation(PNode *A) //
{
// ，A
PNode *B = A->left;
A->left = B->right;
B->right = A;
A->height = Max(GetHeight(A->left), GetHeight(A->right)) + 1;
B->height = Max(GetHeight(B->left), GetHeight(A->right)) + 1;
return B;
}
PNode* BinTree::DoubleLeftRightRotation(PNode *A) //
{
A->left = SingleRightRotation(A->left);
return SingleLeftRotation(A);
}
PNode* BinTree::SingleRightRotation(PNode *A) //
{
PNode *B = A->right;
A->right = B->left;
B->left = A;
A->height = Max(GetHeight(A->left), GetHeight(A->right)) + 1;
B->height = Max(GetHeight(B->left), GetHeight(A->right)) + 1;
return B;
}
PNode* BinTree::DoubleRightLeftRotation(PNode *A) //
{
A->right = SingleLeftRotation(A->right);
return SingleRightRotation(A);
}
////////////////////////////////////////////////////////
//
#include <iostream>
#include "BinTree.h"
using namespace std;
int main()
{
BinTree bt;
//
bt.SetRoot(bt.AVL_Insertion(2, bt.GetRoot())); //
bt.SetRoot(bt.AVL_Insertion(3, bt.GetRoot()));
bt.SetRoot(bt.AVL_Insertion(4, bt.GetRoot()));
bt.SetRoot(bt.AVL_Insertion(5, bt.GetRoot()));
bt.SetRoot(bt.AVL_Insertion(6, bt.GetRoot()));
bt.SetRoot(bt.AVL_Insertion(8, bt.GetRoot()));
bt.SetRoot(bt.AVL_Insertion(2, bt.GetRoot()));
bt.SetRoot(bt.AVL_Insertion(1, bt.GetRoot()));
cout << bt.GetHeight(bt.GetRoot()) << endl;
cout << " : " << endl;
bt.PreOrder(bt.GetRoot());
cout << endl;
cout << " : " << endl;
bt.CenOrder(bt.GetRoot());
cout << endl;
cout << " ：" << endl;
bt.Trave(bt.GetRoot());
cout << endl;
cout << " :" << bt.FindMin(bt.GetRoot())->data << endl;
cout << " :" << bt.FindMax(bt.GetRoot())->data << endl;
///////////////////////////////////////////////////////////////////
//cout << endl << " 5 " << endl;
//bt.Delete(4, bt.GetRoot());
cout << " : " << endl;
bt.PreOrder(bt.GetRoot());
cout << endl;
cout << " : " << endl;
bt.CenOrder(bt.GetRoot());
cout << endl;
cout << " ：" << endl;
bt.Trave(bt.GetRoot());
cout << endl;
cout << " :" << bt.FindMin(bt.GetRoot())->data << endl;
cout << " :" << bt.FindMax(bt.GetRoot())->data << endl;
system("pause");
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
