[데이터 구조] 이 진 트 리 기본 코드 요약
77479 단어 데이터 구조
1. 기본 성
2. 저장 방식 및 기본 구조
1. 순차 저장
배열 의 형식 으로 저장 하고 배열 의 아래 표 시 는 이 진 트 리 아래 표 시 됩 니 다. 배열 의 내용 은 이 진 트 리 의 내용 입 니 다.
2. 체인 메모리
// ( )
template <class T>
struct BTnode {
T data;
BTnode* left, * right;
BTnode(const T& item = T(), BTnode* lptr = NULL, BTnode* rptr = NULL) :data(item), left(lptr), right(rptr) {}
};
//
template <class T>
BTnode<T>* GetBtnode(const T& item, BTnode<T>* lp = NULL, BTnode<T>* rp = NULL)
{
BTnode<T>* p;
p = new BTnode<T>(item, lp, rp);
if (p == NULL)
{
cerr << "Memory allocation failure!" << endl;
exit(1);
}
cout << "GetBtnode called!" << endl;
return p;
}
메모: 이 진 트 리 함수 만 들 기
//
// ：
BTnode<char>* nullp = NULL;
BTnode<char>* c = GetBtnode('C', f, nullp); //
// ：
BTnode<char>* b = GetBtnode('B', NULL, NULL); //
//
// ：
BTnode<char>* nullp = NULL;
BTnode<char>* c = GetBtnode('C', f, nullp); //
// ：
BTnode<char>* b = GetBtnode('B', NULL, NULL); //
3. 차원 이동, 순서 회전 체인 식 비 귀속 및 수직 출력
1. 층 차 역법 1
대기 열 에 먼저 들 어가 서 삭제 와 접근 을 순환 으로 합 니 다.
//
template <class T>
void Level(const BTnode<T>* t)
{
if (t == NULL)
return;
queue <const BTnode<T>*> Q;
Q.push(t);
while (!Q.empty())
{
t = Q.front();
Q.pop();
cout << t->data;
if (t->left)
Q.push(t->left);
if (t->right)
Q.push(t->right);
}
cout<<endl;
2. 차원 차 역법 2
대기 열 우선 접근 과 입 대 를 순환 으로 합 니 다.
//
template <class T>
void Level(const BTnode<T>* t)
{
if (t == NULL)
return;
queue <const BTnode<T>*> Q;
cout << t->data;
Q.push(t);
while (!Q.empty())
{
t = Q.front();
Q.pop();
if (t->left)
{
cout << t->left->data;
Q.push(t->left);
}
if (t->right)
{
cout << t->right->data;
Q.push(t->right);
}
}
cout << endl;
}
3. 순서 체인 식 비 귀속
대비 차원 차 역법 2 대열 선 방 건 과 입 대 출 대 와 + 1 / 2 를 순환 으로 한다.
//
template <class T>
BTnode<T>* MakeLinked(const vector<T>& L)
{
if (L.size() == 0)
return NULL;
queue<BTnode<T>*> Q;
BTnode<T>* parent, * child;
int n = L.size(),i = 0;
BTnode<T>* t = GetBtnode(L[0]);
Q.push(t);
while (!Q.empty())
{
parent = Q.front();
Q.pop();
if (2 * i + 1 < n && L[2 * i + 1] != T())
{
child = GetBtnode(L[2 * i + 1]);
parent->left = child;
Q.push(child);
}
if (2 * i + 2 < n && L[2 * i + 2] != T())
{
child = GetBtnode(L[2 * i + 2]);
parent->right = child;
Q.push(child);
}
i++;
while (i < n && L[i] == T())
i++;
}
cout << "MakeLinked(1) called!" << endl;
return (t);
}
4. 수직 출력
대비 차원 역법 1 대기 열 노드 와 위치 동기 화 선 입 대 방문 과 판단 을 순환 으로 한다.
//
struct Loction {
int xindent, ylevel;
};
void Gotoxy(int x, int y)
{
static int level = 0, indent = 0;
if (y == 0)
{
indent = 0;
level = 0;
}
if (level != y)
{
cout << endl;
indent = 0;
level++;
}
cout.width(x - indent);
indent = x;
}
template <class T>
void PrintTree(const BTnode<T>* t, int screenwidth)
{
if (t == NULL)
return;
int level = 0, offset = screenwidth / 2;
Loction fLoc, cLoc;
queue<const BTnode<T>*> Q;
queue<Loction> LQ;
fLoc.xindent = offset;
fLoc.ylevel = level;
Q.push(t);
LQ.push(fLoc);
while (!Q.empty())
{
t = Q.front();
Q.pop();
fLoc = LQ.front();
LQ.pop();
Gotoxy(fLoc.xindent, fLoc.ylevel);
cout << t->data;
if (fLoc.ylevel != level)
{
level++;
offset = offset / 2;
}
if (t->left)
{
Q.push(t->left);
cLoc.ylevel = fLoc.ylevel + 1;
cLoc.xindent = fLoc.xindent - offset / 2;
LQ.push(cLoc);
}
if (t->right)
{
Q.push(t->right);
cLoc.ylevel = fLoc.ylevel + 1;
cLoc.xindent = fLoc.xindent + offset / 2;
LQ.push(cLoc);
}
}
cout << endl;
}
4. 앞 순 서 를 옮 겨 다 니 는 재 귀적 비 재 귀적 및 빠 른 정렬
1. 앞 순 서 를 옮 겨 다 니 는 재 귀적
//
template <class T>
void Preorder(const BTnode<T>* t)
{
if (t == NULL)
return;
cout << t->data;
if (t->left)
Preorder(t->left);
if (t->right)
Preorder(t->right);
}
2. 앞 순 서 를 옮 겨 다 니 는 비 재 귀적
스 택 while (t | |! S. empty () {t: 오른쪽 스 택 에 접근 하면 왼쪽 을 가리 키 며, 그렇지 않 으 면 스 택 에서 나 옵 니 다 (스 택 에서 꺼 냅 니 다)}
//
template <class T>
void SimPreorder(const BTnode<T>* t)
{
if (!t)
return;
stack<const BTnode<T>*> S;
while (t || !S.empty())
{
if (t)
{
cout << t->data;
if (t->right)
S.push(t->right);
t = t->left;
}
else
{
t = S.top();
S.pop();
}
}
}
3. 빠 른 정렬
좌우 로 바 꾸 어 아래 표 시 를 취하 다.
//
template <class T>
int Particition(T* pa, int low, int high)
{
int i = low, j = high;
T temp = pa[i];
while (i != j)
{
while (i<j && pa[j]>temp)
j--;
if (i < j)
pa[i++] = pa[j];
while (i < j && pa[i] < temp)
i++;
if (i < j)
pa[j--] = pa[i];
}
pa[i] = temp;
return i;
}
template<class T>
void QuickSoret(T* pa, int low, int high)
{
if (low > high)
return;
int m = Particition(pa, low, high);
QuickSoret(pa, low, m - 1);
QuickSoret(pa, m + 1, high);
}
//
template<class T>
void PrintQuickSoretResout(T* pa, int low, int high)
{
QuickSoret(pa, low, high);
for (int k = low; k <= high; k++)
cout << pa[k] << " ";
cout << endl;
}
5. 중간 순서 로 옮 겨 다 니 는 재 귀 비 재 귀 및 한 노 타 재 귀 알고리즘
1. 중간 순서 로 반복 되 는 재 귀적
//
template <class T>
void Inorder(const BTnode<T>* t)
{
if (!t)
return;
if (t->left)
Inorder(t->left);
cout << t->data;
if (t->right)
Inorder(t->right);
}
2. 중간 순서 로 옮 겨 다 니 는 비 재 귀적
창고 while (t | |! S. empty () {만약 t: 창고 에 들 어 가 는 것 이 왼쪽 을 가리 키 는 지 여부: 창고 에 나 가 는 것 이 오른쪽 을 가리 키 는 지}
//
template <class T>
void SimInorder(const BTnode<T>* t)
{
if (!t)
return;
stack<const BTnode<T>*> S;
while (t || !S.empty())
{
if (t)
{
S.push(t);
t = t->left;
}
else
{
t = S.top();
S.pop();
cout << t->data;
t = t->right;
}
}
}
3. 한 노 타 재 귀 알고리즘
대비 중 순차 적 재 귀
//
void Hanoi(int n, char A, char B, char C)
{
if (n <= 0)
return;
if (n > 1)
Hanoi(n - 1, A, C, B);
cout << '(' << n << ")," << A << ',' << C << endl;
if (n > 1)
Hanoi(n - 1, B, A, C);
}
6. 후 순 으로 옮 겨 다 니 는 재 귀적 비 재 귀적 및 깊이 있 는 해석, 복사 삭제 와 순 전 된 체인 재 귀적
1. 뒤 순 서 를 옮 겨 다 니 는 재 귀적
//
template <class T>
void Postorder(const BTnode<T>* t)
{
if (!t)
return;
if (t->left)
Postorder(t->left);
if (t->right)
Postorder(t->right);
cout << t->data;
}
2. 뒤 순 으로 옮 겨 다 니 는 비 재 귀적
스 택 노드 와 tag 동기 화 while (t |! S. empty () {만약 t: 스 택 에 들 어가 면 왼쪽 을 가리 키 지 않 습 니 다. 그렇지 않 으 면: {스 택 에 나 가면 tag 가 1: 스 택 에 들 어가 면 1 을 2 손가락 오른쪽 으로 바 꿉 니 다. 그렇지 않 으 면: 방문}
//
template <class T>
void SimPostorder(const BTnode<T>* t)
{
if (!t)
return;
int tag;
const BTnode<T>* temp;
stack<const BTnode<T>*> S;
stack<int> tagS;
while (t || !S.empty())
{
if (t)
{
S.push(t); tagS.push(1);
t = t->left;
}
else
{
temp = S.top(); tag = tagS.top();
S.pop(); tagS.pop();
if (tag == 1)
{
S.push(temp); tagS.push(2);
t = temp->right;
}
else
cout << temp->data;
}
}
}
3. 이 진 트 리 깊이 구하 기
//
template<class T>
int Depth(const BTnode<T>* t)
{
if (!t)
return -1;
int l = Depth(t->left);
int r = Depth(t->right);
return (1 + (l > r ? l : r));
}
4. 이 진 트 리 링크 복사
//
template<class T>
BTnode<T>* CopyTree(const BTnode<T>* t)
{
if (!t)
return(NULL);
BTnode<T>* l = CopyTree(t->left);
BTnode<T>* r = CopyTree(t->right);
return (GetBtnode(t->data, l, r));
}
5. 이 진 트 리 링크 삭제
//
template<class T>
void DeleteTree(const BTnode<T>* t)
{
if (!t)
return;
DeleteTree(t->left);
DeleteTree(t->right);
delete t;
t = NULL;
}
6. 순차 체인 재 귀
//
template<class T>
BTnode<T>* MakeLinked(const vector<T>& L, int size, int pos)
{
if (pos >= size || L[pos] ==T())
return NULL;
BTnode<T>* left = MakeLinked(L, size, 2 * pos + 1);
BTnode<T>* right = MakeLinked(L, size, 2 * pos + 2);
BTnode<T>* t = GetBtnode(L[pos], left, right);
return t;
}
7. 중 서 는 그 밖의 두 가지 중 하나 와 결합 하여 진실 한 이 진 트 리 를 구한다.
이전 순서 와 중 서 를 예 로 들 어 차이 노드 수 좌우 재 귀 건축 첫 번 째 를 계산 했다.
//
template<class T>
BTnode<T>* MakeLinked(const T* pL, const T* iL, int size)
{
if (size <= 0)
return NULL;
BTnode<T>* t, * left, * right;
const T* rL;
int k;
for (rL = iL; rL < iL + size; rL++)
if (*rL == *pL)
break;
k = rL - iL;
left = MakeLinked(pL + 1,iL, k);
right = MakeLinked(pL + k + 1,iL + k + 1 , size - k - 1);
t = GetBtnode(*pL, left, right);
return(t);
}
위 에는 이 진 트 리 의 지식 포인트 가 있 으 니 어디 가 틀 렸 는 지 지적 해 주시 기 바 랍 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
