[꼭대기] [데이터 구조] 이 진 트 리
컴퓨터 과학 에서 이 진 트 리 는 각 노드 에 최대 두 개의 나무 가 있 는 나무 구조 이다.보통 하위 나 무 는 '왼쪽 subtree' (left subtree) 와 '오른쪽 subtree' (right subtree) 라 고 불 린 다.이 진 트 리 는 이 진 트 리 와 이 진 트 리 를 찾 는 데 자주 사용 된다.
이 진 트 리 의 모든 결점 은 기껏해야 두 그루 의 나무 (존재 도가 2 보다 큰 결점 은 없다) 만 있 고 이 진 트 리 의 자 나 무 는 좌우 의 구분 이 있 으 며 순 서 는 뒤 바 뀌 어 서 는 안 된다.두 갈래 나무의 i 층 은 많아야 2 ^ {i - 1} 개의 결점 이 있다.깊이 가 k 인 이 진 트 리 는 많아야 2 ^ k - 1 개의 결점 이 있다.모든 이 진 트 리 T 에 대해 터미널 노드 가 n 이면0, 도 2 의 결 점 수 는 n2, n0=n_2+1。
(1) 완전 이 진 트 리 - 이 진 트 리 의 높이 가 h 이면 h 층 을 제외 하고 다른 각 층 (1 ～ h - 1) 의 결 점 수 는 모두 최대 개수 에 달 하고 h 층 에 잎 결점 이 있 으 며 잎 결점 은 모두 왼쪽 에서 오른쪽으로 순서대로 배열 되 는데 이것 이 바로 완전 이 진 트 리 이다.
(2) 만 이 진 트 리 - 잎의 결점 을 제외 하고 모든 결점 은 좌우 자엽 이 있 고 잎의 결점 은 모두 최 하층 에 있 는 이 진 트 리 이다.
이 진 트 리 성질
(1) 비 공 이 진 트 리 에서 i 층 의 결점 총 수 는 2 ^ (i - 1), i > = 1 을 초과 하지 않 는 다.
(2) 깊이 가 h 인 이 진 트 리 는 최대 2 ^ h - 1 개의 결점 (h > = 1) 이 있 고 최소 h 개의 결점 이 있다.
(3) 임의의 이 진 트 리 에 대해 잎 결 점 수 는 N0 이 고 도수 가 2 인 결 점 수 는 N2 이면 N0 = N2 + 1 이다.
(4) n 개의 결점 을 가 진 완전 이 진 트 리 의 깊이 는 log 2 (n + 1) 이다. [로그 가 2 를 밑 으로 하 는 n + 1]
저장 구조: 순차 저장, 체인 저장
옮 겨 다 니 기 방식: 앞 순서 옮 겨 다 니 기, 중간 순서 옮 겨 다 니 기, 뒤 순서 옮 겨 다 니 기
이전 순서 옮 겨 다 니 기:
void _PreOrder(Node* root)
{
if (root == NULL)
return;
cout << root->_data << " ";
_PreOrder(root->_left);
_PreOrder(root->_right);
}중간 순서 옮 겨 다 니 기:
void _InOrder(Node* root)
{
if (root == NULL)
return;
_InOrder(root->_left);
cout << root->_data << " ";
_InOrder(root->_right);
}다음 순서 옮 겨 다 니 기:
void _PostOrder(Node* root)
{
if (root == NULL)
return;
_PostOrder(root->_left);
_PostOrder(root->_right);
cout << root->_data << " ";
}그 밖 에 이 진 트 리 에 대한 조작 은 다음 과 같다.
나무의 깊이 Depth ()
나무의 크기 Size ()
잎 결점 의 개수 Leaf Size ()
K 층 에 도 개수 추가 GetKLevel ()
다음 과 같이 구현:
Depth()：
size_t _Depth(Node* root)
{
if (root == NULL)
return 0;
int leftDepth = _Depth(root->_left);
int rightDepth = _Depth(root->_right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}Size()：
size_t _Size(Node* root)
{
if (root == NULL)
return 0;
return _Size(root->_left) + _Size(root->_right) + 1;
}LeafSize()：
void _LeafSize(Node* root, size_t& size) // size ， ， size 0
{
if (root == NULL)
return;
if (root->_left == NULL && root->_right == NULL)
{
++size;
return;
}
_LeafSize(root->_left,size);
_LeafSize(root->_right, size);
}GetKLevel()：
void _GetKLevel(Node* root, int k,
size_t level, size_t& kSize)
{
if (root == NULL)
{
return;
}
if (level == k)
{
++kSize;
return;
}
_GetKLevel(root->_left, k, level + 1, kSize);
_GetKLevel(root->_right, k, level + 1, kSize);
}이로써 이 진 트 리 의 기본 작업 이 완료 되 었 다.
우 리 는 이 진 트 리 의 앞 순서, 중간 순서, 뒤 순 서 는 모두 재 귀 체 제 를 이용 하 는 것 을 발견 했다. 그러면 재 귀 하지 않 으 면 어떻게 실현 되 는 것 일 까?
여기에 세 가지 서로 다른 스 트 리밍 방식 의 비 재 귀적 방식 을 써 서 실현 합 니 다.
이전 순서 옮 겨 다 니 기 (비 재 귀적):
void _PreOrder_NoR()
{
stack<Node*> s;
if (_root)
{
s.push(_root);
}
while (!s.empty())
{
Node* top = s.top();
cout << top->_data << " ";
s.pop();
if (top->_right) // ，
{
s.push(top->_right);
}
if (top->_left)
{
s.push(top->_left);
}
}
}중간 순서 로 옮 겨 다 니 기 (비 재 귀적):
void _InOrder_NoR()
{
Node* cur = _root;
stack<Node*> s;
while (cur || !s.empty())
{
while (cur)
{
// 1. ，
s.push(cur);
cur = cur->_left;
}
// 2. ， ， ， ， ，
if (!s.empty())
{
Node* top = s.top();
s.pop();
cout << top->_data << " ";
cur = top->_right;
}
}
}다음 순서 로 옮 겨 다 니 기 (비 재 귀적):
void _PostOrder_NoR()
{
Node* pre = NULL;
Node* cur = _root;
stack<Node*> s;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
Node* top = s.top();
if (top->_right == NULL || top->_right == pre)
{
cout << top->_data << " ";
s.pop();
pre = top;
}
else
{
cur = top->_right;
}
}
}재 귀적 이지 않 은 실현 은 스 택 구 조 를 이용 하여 이 진 트 리 를 저장 하고 관리 하 는 것 임 을 발견 했다.
소스 코드 및 테스트 코드 첨부:
BinaryTree. h 파일:
#pragma once
#include <stack>
template <class T>
struct BinaryTreeNode
{
T _data;
BinaryTreeNode<T>* _left;
BinaryTreeNode<T>* _right;
BinaryTreeNode(const T& x)
: _data(x)
, _left(NULL)
, _right(NULL)
{}
};
template <class T>
class BinaryTree
{
typedef BinaryTreeNode<T> Node;
public:
BinaryTree()
:_root(NULL)
{}
BinaryTree(const T* a, size_t size, const T& invalid)
{
size_t index = 0;
_root = _CreatBinaryTree( a, size, index, invalid);
}
BinaryTree(const BinaryTree<T>& t)
{
_root = _Copy(t._root);
}
//BinaryTree<T>& operator=(const BinaryTree<T>& t)
//{
// if (this != &t)
// {
// Node* tmp = _Copy(t._root);
// _Destory(_root);
// _root = tmp;
// }
// return *this;
//}
BinaryTree<T>& operator=(BinaryTree<T> t)
{
swap(this->_root, t._root);
return *this;
}
~BinaryTree()
{
_Destory(_root);
_root = NULL;
}
void PreOrder()
{
_PreOrder(_root);
cout << endl;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
void PostOrder()
{
_PostOrder(_root);
cout << endl;
}
size_t Size()
{
return _Size(_root);
}
size_t Depth()
{
return _Depth(_root);
}
size_t LeafSize()
{
size_t size = 0;
_LeafSize(_root,size);
return size;
}
size_t GetKLevel(int k)
{
size_t kSize = 0;
size_t level = 1;
_GetKLevel(_root,k,level,kSize);
return kSize;
}
void PreOrder_NoR()
{
_PreOrder_NoR();
cout << endl;
}
void InOrder_NoR()
{
_InOrder_NoR();
cout << endl;
}
void PostOrder_NoR()
{
_PostOrder_NoR();
cout << endl;
}
protected:
void _Destory(Node* root)
{
if (root == NULL)
{
return;
}
_Destory(root->_left);
_Destory(root->_right);
delete root;
}
Node* _Copy(Node* root)
{
if (root == NULL)
{
return NULL;
}
Node* newRoot = new Node(root->_data);
newRoot->_left = _Copy(root->_left);
newRoot->_right = _Copy(root->_right);
return newRoot;
}
Node* _CreatBinaryTree(const T* a, size_t size,
size_t& index, const T& invalid)
{
Node* root = NULL;
while (index < size && a[index] != invalid)
{
root = new Node(a[index]); // new
root->_left = _CreatBinaryTree( a, size, ++index, invalid);
root->_right = _CreatBinaryTree( a, size, ++index, invalid);
}
return root;
}
void _PreOrder(Node* root)
{
if (root == NULL)
return;
cout << root->_data << " ";
_PreOrder(root->_left);
_PreOrder(root->_right);
}
void _InOrder(Node* root)
{
if (root == NULL)
return;
_InOrder(root->_left);
cout << root->_data << " ";
_InOrder(root->_right);
}
void _PostOrder(Node* root)
{
if (root == NULL)
return;
_PostOrder(root->_left);
_PostOrder(root->_right);
cout << root->_data << " ";
}
size_t _Size(Node* root)
{
if (root == NULL)
return 0;
return _Size(root->_left) + _Size(root->_right) + 1;
}
size_t _Depth(Node* root)
{
if (root == NULL)
return 0;
int leftDepth = _Depth(root->_left);
int rightDepth = _Depth(root->_right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
void _LeafSize(Node* root, size_t& size) // size ， ， size 0
{
if (root == NULL)
return;
if (root->_left == NULL && root->_right == NULL)
{
++size;
return;
}
_LeafSize(root->_left,size);
_LeafSize(root->_right, size);
}
void _GetKLevel(Node* root, int k,
size_t level, size_t& kSize)
{
if (root == NULL)
{
return;
}
if (level == k)
{
++kSize;
return;
}
_GetKLevel(root->_left, k, level + 1, kSize);
_GetKLevel(root->_right, k, level + 1, kSize);
}
void _PreOrder_NoR() // ->
{
stack<Node*> s;
if (_root)
{
s.push(_root);
}
while (!s.empty())
{
Node* top = s.top();
cout << top->_data << " ";
s.pop();
if (top->_right) // ，
{
s.push(top->_right);
}
if (top->_left)
{
s.push(top->_left);
}
}
}
void _InOrder_NoR()
{
Node* cur = _root;
stack<Node*> s;
while (cur || !s.empty())
{
while (cur)
{
// 1. ，
s.push(cur);
cur = cur->_left;
}
// 2. ， ， ， ， ，
if (!s.empty())
{
Node* top = s.top();
s.pop();
cout << top->_data << " ";
cur = top->_right;
}
}
}
void _PostOrder_NoR()
{
Node* pre = NULL;
Node* cur = _root;
stack<Node*> s;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
Node* top = s.top();
if (top->_right == NULL || top->_right == pre)
{
cout << top->_data << " ";
s.pop();
pre = top;
}
else
{
cur = top->_right;
}
}
}
protected:
Node* _root;
};Test. cpp 파일:
#include <iostream>
using namespace std;
#include "BinaryTree.h"
int main()
{
int a[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };
BinaryTree<int> t( a, 10, '#');
cout << t.Depth() << endl;
cout << t.Size() << endl;
t.PreOrder();
t.InOrder();
t.PostOrder();
cout<< t.GetKLevel(1) << endl;
cout << t.GetKLevel(3) << endl;
cout << t.LeafSize() << endl;
t.PreOrder_NoR();
t.InOrder_NoR();
t.PostOrder_NoR();
system("pause");
return 0;
}잘못 이 있 으 면 지적 해 주시 기 바 랍 니 다.
본문 은 "Vs 여 소포" 블 로그 에서 나 온 것 이 니, 반드시 이 출처 를 보존 해 주 십시오.http://survive.blog.51cto.com/10728490/1769564
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
