[DS] 데이터 구조 - 이 진 트 리 구현

최근 에 데이터 구 조 를 복습 하기 시 작 했 습 니 다. 머리 가 좋 지 않 은 것 같 습 니 다. 나중에 볼 수 있 도록 기록 해 드 리 겠 습 니 다. 도움 이 되 었 으 면 좋 겠 습 니 다!
클래스 정의 와 일부 함수 인터페이스:

template<class T>
struct BinaryTreeNode
{
	BinaryTreeNode(T data)
		:_data(data),
		_left(NULL),
		_right(NULL)
	{}
	BinaryTreeNode<T>* _left;
	BinaryTreeNode<T>* _right;
	T _data;
};
template<class T>
class BinaryTree
{
	typedef BinaryTreeNode<T> Node;
public:
	BinaryTree();
	BinaryTree(T* arr, size_t size, const T& value);
	//BinaryTree(const BinaryTree<T>& other);
	//BinaryTree<T>& operator=(const BinaryTree<T>& other);
	//~BinaryTree();
	//    
	void PreOrder();
	void InOrder();
	void PostOrder();
	
	//    
	void PreOrder_NoR();
	void InOrder_NoR();
	void PostOrder_NoR();
	void LevelOrder();


	size_t Size();
	size_t Depth();
	size_t LeafSize();

다음 의 완전한 코드:

#include <iostream>
#include <assert.h>
#include <queue>
#include <stack>
using namespace std;


template<class T>
struct BinaryTreeNode
{
	BinaryTreeNode(T data)
		:_data(data),
		_left(NULL),
		_right(NULL)
	{}
	BinaryTreeNode<T>* _left;
	BinaryTreeNode<T>* _right;
	T _data;
};
template<class T>
class BinaryTree
{
	typedef BinaryTreeNode<T> Node;
public:
	BinaryTree();
	BinaryTree(T* arr, size_t size, const T& value);
	BinaryTree(const BinaryTree<T>& other);
	//BinaryTree<T>& operator=(BinaryTree<T>& other);
	BinaryTree<T>& operator=(BinaryTree<T> other);
	~BinaryTree();
	//    
	void PreOrder();
	void InOrder();
	void PostOrder();
	
	//    
	void PreOrder_NoR();
	void InOrder_NoR();
	void PostOrder_NoR();
	void LevelOrder();

	size_t Size();
	size_t Depth();
	size_t LeafSize();
protected:

	void _PreOrder(Node* root)
	{
		if (root== NULL)
		{
			return;
		}
		else
		{
			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 << " ";
	}
	Node* CreateTree(T* arr, size_t size,size_t& index, const T& value)
	{
		Node* root = NULL;
		if (index <size && arr[index] != value)
		{
			root = new Node(arr[index]);
			root->_left = CreateTree(arr, size,++index, value);
			root->_right = CreateTree(arr, size,++index, value);
		}
		return root;
	}
	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;
		}
		size_t left = _Depth(root->_left)+1;
		size_t right = _Depth(root->_right)+1;

		return left > right ? left : right;
	}

	size_t _LeafSize(Node* root)
	{
		if (root == NULL)
			return 0;
		if (root->_left == NULL &&root->_right == NULL)
		{
			return 1;
		}

		return _LeafSize(root->_left) + _LeafSize(root->_right);
	}
	Node* CopyTree(Node* root)
	{
		Node* Croot = NULL;
		if (NULL == root)
			return NULL;
		Croot = new Node(root->_data);
		Croot->_left = CopyTree(root->_left);
		Croot->_right = CopyTree(root->_right);

		return Croot;
	}
	void _destroy(Node* root)
	{
		if (root)
		{
			_destroy(root->_left);
			_destroy(root->_right);

			delete root;
			root = NULL;
		}
	}
protected:
	Node* _root;
};

template<class T>
BinaryTree<T>::BinaryTree()
{
	_root = NULL;
}

template<class T>
BinaryTree<T>::BinaryTree(T* arr, size_t size, const T& value)
{
	size_t index = 0;
	_root = CreateTree(arr, size,index, value);
}
template<class T>
BinaryTree<T>::~BinaryTree()
{
	_destroy(_root);
}
template<class T>
BinaryTree<T>::BinaryTree(const BinaryTree<T>& other)
{
	_root = CopyTree(other._root);
}

//   
//template<class T>
//BinaryTree<T>& BinaryTree<T>::operator=(BinaryTree<T>& other)
//{
//	if (this != &other)
//	{
//		this->~BinaryTree();
//	}
//	_root = CopyTree(other._root);
//	return *this;
//}

//   
template<class T>
BinaryTree<T>& BinaryTree<T>::operator=(BinaryTree<T> other)
{
	swap(_root, other._root);
	return *this;
}
template<class T>
void BinaryTree<T>::PreOrder()
{
	_PreOrder(_root);
	cout << endl;
}
template<class T>
void BinaryTree<T>::PreOrder_NoR()
{
	Node* cur = _root;
	stack<Node*> s;

	while (cur || !s.empty())
	{
		while (cur)
		{
			cout << cur->_data << " ";
			s.push(cur);
			cur = cur->_left;
		}

		if (!s.empty())
		{
			cur = s.top();
			s.pop();
			cur = cur->_right;
		}
	}
	cout << endl;
}
template<class T>
void BinaryTree<T>::InOrder()
{
	_InOrder(_root);
	cout << endl;
}


template<class T>
void BinaryTree<T>::InOrder_NoR()
{
	Node* cur = _root;
	stack<Node*> s;

	while (cur || !s.empty())
	{
		while (cur)
		{
			s.push(cur);
			cur = cur->_left;
		}
		Node* temp = s.top();
		s.pop();
		cout << temp->_data << " ";
		cur = temp->_right;
	}
	cout << endl;
}

template<class T>
void BinaryTree<T>::PostOrder_NoR()
{
//                      ，  
//        P，     。  P          ，        ；  
//  P          ，                 ，            。  
//        ，  P            ，                ，  
//            ，                 。
	
	Node* cur = _root;
	Node* prev = NULL;
	stack<Node*> st;


	if (_root==NULL)
	{
		return;
	}
	st.push(cur);
	while (!st.empty())
	{
		cur = st.top();
		if ((cur->_left == NULL && cur->_right == NULL)\
			|| (prev != NULL) && (prev == cur->_left || prev == cur->_right))
		{//       ，  ，           ，     。
			cout << cur->_data << " ";
			st.pop();
			prev = cur;
		}
		else
		{
			if (cur->_right)
			{
				st.push(cur->_right);
			}
			if (cur->_left)
			{
				st.push(cur->_left);
			}
		}
		
	}
	cout << endl;
}

template<class T>
void BinaryTree<T>::PostOrder()
{
	_PostOrder(_root);
	cout << endl;
}

template<class T>
void BinaryTree<T>::LevelOrder()
{
	queue<Node*> qu;
	if (_root)
	{
		qu.push(_root);
	}
	while (!qu.empty())
	{
		Node* front = qu.front();
		qu.pop();
		cout << front->_data << " ";
		if (front->_left)
		{
			qu.push(front->_left);
		}
		if (front->_right)
		{
			qu.push(front->_right);
		}
	}
	cout << endl;
}


template<class T>
size_t BinaryTree<T>::Size()
{
	return _Size(_root);
}
/*void _size()
{
	gsize = 0;//        0 ，      ；
	_size(root);
	return gsize;
}

//    gsize     ，      ，   ，++gsize  。
//              0，    bug；             bug。

//                      ，                ,   ， int &size。
//size             ；
size_t _Size(Node* root)
{
	if (root == NULL)
	{
		return 0;
	}
	gsize++;
	_Size(root->_left);
	_Size(root->_right);

}*/
template<class T>
size_t BinaryTree<T>::Depth()
{
	return _Depth(_root);
}

template<class T>
size_t BinaryTree<T>::LeafSize()
{
	return _LeafSize(_root);
}

다음은 테스트 코드:

void test()
{
	int arr[10] = {1,2,3,'#','#',4,'#','#',5,6};
	BinaryTree<int> t1(arr, 10, '#');

	cout << "      " << endl;
	t1.PreOrder();

	cout << "      " << endl;
	t1.InOrder();

	cout << "      " << endl;
	t1.PostOrder();

	cout << "       " << endl;
	t1.PreOrder_NoR();

	cout << "       " << endl;
	t1.InOrder_NoR();

	cout << "       " << endl;
	t1.PostOrder_NoR();
	cout << "    " << endl;
	t1.LevelOrder();

	cout<<"Size == "<<t1.Size()<<endl;
	cout << "Depth == " << t1.Depth() << endl;
	cout << "LeafSize == " << t1.LeafSize() << endl;
}
int main()
{
	test();
	return 0;
}

운행 결 과 는 그림 과 같다.

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

[DS] 데이터 구조 - 이 진 트 리 구현

좋은 웹페이지 즐겨찾기