이 진 트 리 를 옮 겨 다 니 며 - 재 귀적 실현

이 진 트 리 는 나무의 일종 으로 중요 한 데이터 구조 이자 면접 관 들 이 자주 보 는 것 이다.이 진 트 리 에서 면접 문 제 를 흔히 볼 수 있 는 문제 형 은 다음 과 같은 몇 가지 가 있 습 니 다. 이 진 트 리 (선 서, 중 서, 후 서) 를 만 들 고 이 진 트 리 (선 서, 중 서, 후 서 와 층 차 를 옮 겨 다 니 며) 를 옮 겨 다 니 며 이 진 트 리 의 잎 노드 의 개수, 이 진 트 리 의 높이 등 을 구 합 니 다.
다음은 일부 면접 문제 코드 의 재 귀적 실현 이다.비 귀속 실현 은 다음 블 로그 에 발 표 될 것 이다.
"BinaryTree.h"

<strong><span style="font-size:18px;">#pragma once

template<class T>
class BinaryTreeNode
{
public:
	T _data;
	BinaryTreeNode<T>* _left;
	BinaryTreeNode<T>* _right;

	BinaryTreeNode(const T& data)
		:_data(data)
		,_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)//invalid    
	{
		size_t inder = 0;
		_root = _GreateTree(a,size,invalid,inder);
	}
	void PrevOrder()//    
	{
		_PrevOrder(_root);
		cout<<endl;
	}
	void InOrder()//    
	{
		_InOrder(_root);
		cout<<endl;
	}
	void PostOrder()//    
	{
		_PostOrder(_root);
		cout<<endl;
	}
	size_t Size()//     
	{
		return _Size(_root);
	}
	size_t LeafSize()//       
	{
		return _LeafSize(_root);
	}
	size_t Depth()//      
	{
		return _Depth(_root);
	}
	size_t GetKLevel(size_t k)// k        
	{
		return _GetKLevel(_root,k);
	}
	Node* Find(const T& data)//      
	{
		return _Find(_root,data);
	}
protected:
	Node* _Find(Node* root,const T& data)
	{
		if (root == NULL)
		{
			return NULL;
		}

		if (root->_data == data)
		{
			return root;
		}

		//         
		Node* ret = _Find(root->_left,data);
		if (ret)
		{
			return ret;
		}
		//         
		return _Find(root->_right,data);
	}
	size_t _GetKLevel(Node* root,size_t k)
	{
		if (root == NULL)
		{
			return 0;
		}

		if (k == 1)
		{
			return 1;
		}
		return _GetKLevel(root->_left,k-1) + _GetKLevel(root->_right,k-1);//   k-1   k--，      
	}
	size_t _Depth(Node* root)
	{
		if (root == NULL)
		{
			return 0;
		}

		return _Depth(root->_left) > _Depth(root->_right) ? _Depth(root->_left)+1 : _Depth(root->_right)+1;//     
	}
	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;
	}
	void _PostOrder(Node* root)
	{
		if (root == NULL)
		{
			return;
		}

		_PostOrder(root->_left);
		_PostOrder(root->_right);
		cout<<root->_data<<" ";
	}
	void _InOrder(Node* root)
	{
		if (root == NULL)
		{
			return;
		}

		_InOrder(root->_left);
		cout<<root->_data<<" ";
		_InOrder(root->_right);
	}
	void _PrevOrder(Node* root)
	{
		if (root == NULL)
		{
			return;
		}

		cout<<root->_data<<" ";
		_PrevOrder(root->_left);
		_PrevOrder(root->_right);
	}
	Node* _GreateTree(const T* a,size_t size,const T& invalid,size_t& inder)//     inder  ，      
	{
		Node* root = NULL;
		if (a[inder] != invalid && inder < size)
		{
			root = new Node(a[inder]);
			root->_left = _GreateTree(a,size,invalid,++inder);
			root->_right = _GreateTree(a,size,invalid,++inder);
		}
		return root;//     
	}
private:
	Node* _root;
};
</span></strong>

 
"test.cpp"

<strong><span style="font-size:18px;">#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
using namespace std;
#include "BinaryTree.h"

void TestBinaryTree()
{
	int arr[] = {1, 2, 3, '#', '#', 4, '#' , '#', 5, 6};
	int size = sizeof(arr)/sizeof(arr[0]);
	BinaryTree<int> T(arr,size,'#');

	cout<<"    ： ";
	T.PrevOrder();
	cout<<"    ： ";
	T.InOrder();
	cout<<"    ： ";
	T.PostOrder();

	cout<<"      ？ "<<T.Size()<<endl;
	cout<<"        ？ "<<T.LeafSize()<<endl;
	cout<<"         ？ "<<T.Depth()<<endl;
	cout<<"        k ："<<endl;
	int k = 0;
	cin>>k;
	cout<<" k      ？ "<<T.GetKLevel(k)<<endl;

	typedef BinaryTreeNode<int> Node;
	Node* ret = T.Find(2);
	if (ret == NULL)
	{
		cout<<"   "<<endl;
	} 
	else
	{
		cout<<ret->_data<<" ";
		cout<<"   "<<endl;
	}
}

int main()
{
	TestBinaryTree();
	system("pause");
	return 0;
}</span></strong>