本文共 7315 字，大约阅读时间需要 24 分钟。

二叉树的遍历方式：

前序，中序，后序，层序

二叉树的储存方式：

链式：动态

数组：静态

二叉树的基本操作：构造，拷贝构造，析构，求深度，叶子节点数，第k层节点，前、中、后序，层序

树的节点结构：

template
   
    struct BinaryTreeNode{	BinaryTreeNode
    
     * _left;	BinaryTreeNode
     
      * _right;	T _data; 	BinaryTreeNode(const T& x)		:_left(NULL)		, _right(NULL)		, _data(x)	{}};
     
    
   

BinaryTree( T* a, size_t n, const T& invalid)	{		size_t index = 0;		_root = CreatTree(a, n, invalid, index);	}	Node* CreatTree( T* a, size_t n, const T& invalid, size_t& index)	{		Node* root = NULL;		if (index >= n || a[index] == invalid)		{			return NULL;		}			root = new Node(a[index]);			root->_left = CreatTree(a, n, invalid, ++index);			root->_right = CreatTree(a, n, invalid, ++index);		return root;	}

拷贝构造函数：

BinaryTree(const BinaryTree& t)	{		_root = _Copy(t._root);	}	Node* _Copy(Node* root)	{		if (NULL == root);		{			return NULL;		}		Node* newroot = new Node(root->_data);		newroot->_left = _Copy(root->_left);		newroot->_right = _Copy(root->_right);		return newroot;	}

BinaryTree& operator=(const BinaryTree& t)	{		if (this != &t)		{			BinaryTree tmp(t);			swap(tmp._root, _root);		}		return *this;	}

析构函数：

析构掉整棵树的时候需要析构他的每个节点，这就要考虑析构节点的先后顺序

前序，中序都不能实现，所以我们选择后序

~BinaryTree()	{		Destroy(_root);		_root = NULL;	}	void Destroy(Node* root)	{		if (NULL == root)		{			return;		}		Destroy(root->_left);		Destroy(root->_right);		delete root;	}

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

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

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

层序

层序不能使用递归的写法，但我们可以利用队列。先将根节点插入队列，看队列是否为空，不为空的话就取队列的头，然后将头节点的左右节点插入队列，

最后pop掉这个头节点。这样就可以实现层序了。

void LevelOrder()	{		queue
   
     q;		if (_root != NULL)		{			q.push(_root);			while (!q.empty())			{				Node* Front = q.front();				cout << Front->_data << " ";				if (Front->_left != NULL)				{					q.push(Front->_left);				}				if (Front->_right != NULL)				{					q.push(Front->_right);				}				q.pop();			}		}	}
   

size_t Depth()	{		return _Depth(_root);	}	size_t _Depth(Node* root)	{		if (NULL==root)		{			return 0;		}		size_t LD = _Depth(root->_left);		size_t LR = _Depth(root->_right);		return LD > LR ? LD + 1 : LR + 1;	}

size_t LeafSize()//叶子节点	{		return _LeafSize(_root);	}	size_t _LeafSize(Node* root)	{		if (NULL==root)		{			return 0;		}		if (root->_left == NULL && root->_right == NULL)		{			return 1;		}		size_t i = _LeafSize(root->_left);		size_t j = _LeafSize(root->_right);		return i + j;	}

size_t GetKLevel(size_t k)	{		size_t count = 0;		_GetKLevel(_root, k, count);		return count;	}	void _GetKLevel(Node* root, size_t k, size_t& count)	{		if (root == NULL)		{			return ;		}		if (k == 1)		{			++count;		}		_GetKLevel(root->_left, k - 1, count);		_GetKLevel(root->_right, k - 1, count);	}

求节点数：

将整棵树遍历一遍，用一个变量计数即可

size_t Size()	{		size_t ret = 0;		_Size(_root,ret);		return ret;	}	void _Size(Node* root,size_t &ret)	{		if (root == NULL)		{			return ;		}		ret++;		_Size(root->_left);		_Size(root->_right);	}

全部实现：

#include
   
    #include
    
     using namespace std;template
     
      struct BinaryTreeNode{	BinaryTreeNode
      
       * _left;	BinaryTreeNode
       
        * _right;	T _data; 	BinaryTreeNode(const T& x)		:_left(NULL)		, _right(NULL)		, _data(x)	{}};template
        
         class BinaryTree{ typedef BinaryTreeNode
         
           Node;public: BinaryTree()//构造函数 :_root(NULL) {} BinaryTree( T* a, size_t n, const T& invalid)//构造树 { size_t index = 0;//数组下标 _root = CreatTree(a, n, invalid, index); } Node* CreatTree( T* a, size_t n, const T& invalid, size_t& index)//构造二叉树 ，这里的index要用引用，否则上一层递归到里面的++对index没有影响 { Node* root = NULL; if (index >= n || a[index] == invalid) { return NULL; } root = new Node(a[index]); root->_left = CreatTree(a, n, invalid, ++index); root->_right = CreatTree(a, n, invalid, ++index); return root; } BinaryTree(const BinaryTree& t)//拷贝构造 { _root = _Copy(t._root); } Node* _Copy(Node* root) { if (NULL == root) { return NULL; } Node* newroot = new Node(root->_data); newroot->_left = _Copy(root->_left); newroot->_right = _Copy(root->_right); return newroot; } BinaryTree& operator=(const BinaryTree& t) { if (this != &t) { BinaryTree tmp(t); swap(tmp._root, _root); } return *this; } void PrevOrder() { _PrevOrder(_root); cout << endl; } void _PrevOrder(Node* root) { if (NULL==root) { return; } cout << root->_data << " "; _PrevOrder(root->_left); _PrevOrder(root->_right); } void InOrder() { _InOrder(_root); cout << endl; } void _InOrder(Node* root) { if (root == NULL) { return; } _InOrder(root->_left); cout << root->_data << " "; _InOrder(root->_right); } void PostOrder() { _PostOrder(_root); cout << endl; } void _PostOrder(Node* root) { if (root == NULL) { return; } _PostOrder(root->_left); _PostOrder(root->_right); cout << root->_data << " "; } void LevelOrder() { queue
          
            q; if (_root != NULL) { q.push(_root); while (!q.empty()) { Node* Front = q.front(); cout << Front->_data << " "; if (Front->_left != NULL) { q.push(Front->_left); } if (Front->_right != NULL) { q.push(Front->_right); } q.pop(); } } cout << endl; } size_t Size() { size_t ret = 0; _Size(_root,ret); return ret; } void _Size(Node* root,size_t &ret) { if (root == NULL) { return ; } ret++; _Size(root->_left); _Size(root->_right); } size_t Depth() { return _Depth(_root); } size_t _Depth(Node* root) { if (NULL==root) { return 0; } size_t LD = _Depth(root->_left); size_t LR = _Depth(root->_right); return LD > LR ? LD + 1 : LR + 1; } size_t LeafSize()//叶子节点 { return _LeafSize(_root); } size_t _LeafSize(Node* root) { if (NULL==root) { return 0; } if (root->_left == NULL && root->_right == NULL) { return 1; } size_t i = _LeafSize(root->_left); size_t j = _LeafSize(root->_right); return i + j; } /*size_t GetKLevel(size_t k) { size_t count = 0; _GetKLevel(_root, 1, k, count); return count; } void _GetKLevel(Node* root, size_t cur, size_t k, size_t& count) { if (root == NULL) { return; } if (cur == k) { count++; } _GetKLevel(root->_left, cur + 1, k, count); _GetKLevel(root->_right, cur + 1, k, count); }*/ size_t GetKLevel(size_t k) { size_t count = 0; _GetKLevel(_root, k, count); return count; } void _GetKLevel(Node* root, size_t k, size_t& count) { if (root == NULL) { return ; } if (k == 1) { ++count; } _GetKLevel(root->_left, k - 1, count); _GetKLevel(root->_right, k - 1, count); } //析构函数即销毁这棵树，几种遍历只有后序可以实现 ~BinaryTree() { Destroy(_root); _root = NULL; } void Destroy(Node* root) { if (NULL == root) { return; } Destroy(root->_left); Destroy(root->_right); delete root; }private: Node* _root;};int main(){ int arr[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 }; int arr2[5] = { 1, 2, 3, 4 }; BinaryTree
           
             t1(arr, sizeof(arr) / sizeof(arr[0]), '#'); BinaryTree
            
              t2(arr2, sizeof(arr2) / sizeof(arr2[0]), '#'); //t1 = t2; t1.PostOrder(); t1.InOrder(); t1.PrevOrder(); t1.LevelOrder(); size_t i = t1.Depth(); cout << i << endl; size_t k=t1.GetKLevel(2); cout << k << endl; size_t j = t1.LeafSize(); cout << j << endl; system("pause"); return 0;}
            
           
          
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/audience_fzn/article/details/78495163 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！