[꼭대기] 이 진 트 리 의 생 성 및 기본 작업

질문 설명:
   이 진 트 리 라 는 부분의 지식 은 데이터 구조의 중요 한 부분 이 라 고 할 수 있 습 니 다. 관련 분야 의 지식 포 인 트 는 꽤 많 습 니 다. 비록 일부 지식 포 인 트 는 난이도 가 높 지만 대부분의 지식 포 인 트 는 간단 할 수 있 습 니 다. 그래서 필기시험 면접 에서 우 리 는 이 진 트 리 와 관련 된 문제 형 을 거의 만 나 지 못 했 습 니 다.이 진 트 리 와 그 확장 에 관 한 지식 포 인 트 는 6 가지 놀 았 고 데이터 구조의 적어도 절반 은 지식 이 주머니 에 들 어 갔다 고 할 수 있다.
필기시험 면접 에서 특정한 두 갈래 나무 에 있 는 구성원 함 수 를 쓰 게 하 는 경우 가 많 습 니 다. 예 를 들 어 노드 의 옮 겨 다 니 는 순서 (앞 순서, 중간 순서, 뒤 순서, 층 차), K 층 의 노드 수 를 어떻게 구 하 는 지, 두 갈래 나무의 높이 를 구 하 는 지 등 입 니 다. 그래서 여기 서 두 갈래 나무의 기초 구축 부터 시작 하여 벽돌 과 기 와 를 추가 하고 두 갈래 나무의 관련 작업 을 한 걸음 한 걸음 보완 합 니 다.많 든 적 든 너 와 함께 격려 할 수 있 기 를 바란다.

#include<iostream>
using namespace std;

template<class T>
typedef struct BinaryNode 
//      
{
	T _data;//  
	BinaryNode<T>* _left;//     
	BinaryNode<T>* _right;//     

	BinaryNode(const T&x)
		:_left(NULL)
		, _right(NULL)
		, _data(x)
	{}
};

template<class T>
class BinaryTree  //    
{
	typedef BinaryNode<T> Node;//    ， Node  

public:
	BinaryTree()
		:_root(NULL)
	{}

	BinaryTree(const T*a, size_t size, const T&invalid)
		:_root(NULL)//a               ，size   ，invalid    ，    ，     
	{
		size_t index = 0;
		_root = CreateTree(a, size, invalid, index);
	}

	BinaryTree<T>(const BinaryTree<T>&obj)//      
		: _root(NULL)
	{
		_root = _Copy(obj._root);
	}

	BinaryTree<T>& operator=(const BinaryTree<T>&obj)//         
	{
		if (this != &obj)
		{
			_Copy(obj._root);
			_Destroy(_root);
		}
		return *this;
	}

	~BinaryTree()//    
	{
		if (_root)
		{
			_Destroy(_root);
		}
	}


public:
	size_t Size()//    :     +     +   
	{
		return _Size(_root);
	}

	size_t Depth()//    (  ):                
	{
		return _Depth(_root);
	}

	size_t LeafSize()//     :       +       
	{
		return _LeafSize(_root);
	}

	size_t KLevelSize(int k)// K   
	{
		return _KLevelSize(_root, k);
	}

protected:
	void _Destroy(Node* root)//    
	{
		if (root == NULL)
		{
			return;
		}
		if (root->_left == NULL && root->_right == NULL)
		{
			delete root;
			root = NULL;
			return;
		}
		_Destroy(root->_left);
		_Destroy(root->_right);
	}

	Node* _Copy(Node* root)//    
	{
		if (root == NULL)
		{
			return NULL;
		}
		Node* root = new Node(root->_data);

		root->_left = _Copy(root->_left);
		root->_right = _Copy(root->_right);
		return root;
	}

	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);
	}

	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);//          ，             
	}

	size_ t _KLevelSize(Node* root, int k)
	{
		assert(k > 0);
		if (root == NULL)
		{
			return 0;
		}
		if (k == 1)
		{
			return 1;
		}
		return _KLevelSize(root->_left, k - 1) + _KLevelSize(root->_right, k - 1);
	}

	Node* _CreateTree(const T*a, size_t size, const T&invalid, size_t &index)//    
	{
		Node* root = NULL;
		if (index < size && a[index] != invalid)
		{
			root = new Node(a[index]);
			root->_left = _CreateTree(a, size, invalid, ++index);
			root->_right = _CreateTree(a, size, invalid, ++index);
		}
		return root;
	}


private:
	Node* _root;
};

주: 이 진 트 리 의 옮 겨 다 니 는 문제 에 대해 다음 글 에서 자세히 정리 하 겠 습 니 다. 각 신의 지 도 를 환영 합 니 다.