【数据结构】二叉树的实现（如：默认成员函数、（叶子）节点数、深度、四种遍历）(二叉树,实现,数据结构,编程语言)

二叉树：树的每个节点最多有两个子节点。

我们看下它的结构，有二叉链表结构与三叉链表结构，具体结果如我摘自《C++Primer》中的图。

相比之下，三叉链表的优势在于当我们知道父亲节点要找他的子女节点比较方便和便捷，反之当我们知道子女节点找它的父亲节点时也方便。

下面，我实现下二叉链表的结构。

template<classT>structBinaryTreeNode{BinaryTreeNode<T>*_left;//左子树BinaryTreeNode<T>*_right;//右子树T_data;BinaryTreeNode(constT&x):_left(NULL),_right(NULL),_data(x){}};

（1）求二叉树的叶子节点数leafsize:

叶子节点指的是，节点无子女节点。我们有两种思路：

1）设置一下全局变量或者静态变量的size，遍历二叉树，每次遇到一个节点就加加一次size

2)总叶子节点数就等于左子树叶子节点个数+右子树叶子节点个数

//思路1：size_t_LeafSize(Node*root){staticintsize=0;if(root==NULL){returnsize;}if(root->_left==NULL&&root->_right==NULL){size++;returnsize;}_LeafSize(root->_left);_LeafSize(root->_right);}

//思路2：size_t_LeafSize(Node*root){if(root==NULL){return0;}if(root->_left==NULL&&root->_right==NULL){return1;}return_LeafSize(root->_left)+_LeafSize(root->_right);}

（2）求二叉树的深度depth:

深度也称作为高度，就是左子树和右子树深度的较大值。

size_t_Depth(Node*root){if(root==NULL){return0;}intLeftDepth=_Depth(root->_left);intRightDepth=_Depth(root->_right);returnLeftDepth>RightDepth?LeftDepth+1:RightDepth+1;}

（3）求二叉树的节点个数size:

总节点数就等于左子树节点个数+右子树节点个数+根节点个数1

size_t_Size(Node*root){if(root==NULL){return0;}return_Size(root->_left)+_Size(root->_right)+1;}

（4）求第k层节点数：

默认根节点为第一层1。

思路与求叶子节点类似。

size_t_kLevelSize(Node*root,intk)//默认根节点为第1层{assert(k>0);if(root==NULL){return0;}if(k==1){return1;}//不可以传参数k--,不然只能是执行完这一句代码后k才会发生变化，k一直为3//不可以传参数--k,执行root->_left时，k变为2，执行root->_right时为同一层k变为1//传参数k-1return_kLevelSize(root->_left,k-1)+_kLevelSize(root->_right,k-1);}

（5）遍历二叉树：

注意：前中后序遍历要不要漏掉递归出口。

1）前序遍历：访问根节点->左子树->右子树

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

2）中序遍历：访问左子树->根节点->右子树

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

3）后序遍历：访问左子树->右子树->根节点

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

4）层次遍历：

即一层一层地遍历结束，再遍历下一层节点，如int a1[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 }（注意：#表示空。）则层次遍历就应为：1，2，5，3，4，6。

我们用队列解决该问题：首先先给队列无条件入队根节点，下面在出队根节点之前先入队它的子女节点2、5。此时，出队1后队头元素为2，在出队它之前入队它的根节点3，4……

void_LevelOrder(Node*root){queue<Node*>q;if(root==NULL){return;}q.push(root);while(!q.empty()){if(q.front()->_left!=NULL){q.push(q.front()->_left);}if(q.front()->_right!=NULL){q.push(q.front()->_right);}cout<<q.front()->_data<<"";q.pop();}}

我给出完整程序代码（测试用例我就不要在此处多加阐述了，你们可以自己实现）。

#define_CRT_SECURE_NO_WARNINGS1#ifndef__TREE_H__//防止多次包含#define__TREE_H__#include<iostream>usingnamespacestd;#include<assert.h>#include<queue>#include<stack>template<classT>structBinaryTreeNode{BinaryTreeNode<T>*_left;//左子树BinaryTreeNode<T>*_right;//右子树T_data;BinaryTreeNode(constT&x):_left(NULL),_right(NULL),_data(x){}};template<classT>classBinaryTree{typedefBinaryTreeNode<T>Node;//重命名在于想简化代码，避免过长。public:BinaryTree():_root(NULL){}BinaryTree(constT*a,size_tsize,constT&invalid):_root(NULL){size_tindex=0;_root=_CreateTree(a,size,invalid,index);}BinaryTree<T>(constBinaryTree<T>&t):_root(NULL){_root=_Copy(t._root);}BinaryTree<T>&operator=(constBinaryTree<T>&t){if(&t!=this){_Copy(t._root);_Destroy(_root);}return*this;}~BinaryTree(){if(_root){_Destroy(_root);}}//前序遍历voidPreOrder(){_PrevOrder(_root);cout<<endl;}//前序遍历非递归写法voidPreOrderNon_R(){_PreOrderNon_R(_root);cout<<endl;}//中序遍历voidInOrder(){_InOrder(_root);cout<<endl;}//中序遍历非递归写法voidInOrderNon_R(){_InOrderNon_R(_root);cout<<endl;}//后序遍历voidPostOrder(){_PostOrder(_root);cout<<endl;}//后序遍历非递归写法voidPostOrderNon_R(){_PostOrderNon_R(_root);cout<<endl;}//层次遍历voidLevelOrder(){_LevelOrder(_root);cout<<endl;}//节点数size_tSize(){return_Size(_root);}//深度（高度）size_tDepth(){return_Depth(_root);}//叶子节点数size_tLeafSize(){return_LeafSize(_root);}//第k层节点size_tkLevelSize(intk){return_kLevelSize(_root,k);}protected:void_Destroy(Node*root){if(root==NULL){return;}if(root->_left==NULL&&root->_right==NULL){deleteroot;root=NULL;return;}_Destroy(root->_left);_Destroy(root->_right);}Node*_Copy(Node*troot){if(troot==NULL){returnNULL;}Node*root=newNode(troot->_data);root->_left=_Copy(troot->_left);root->_right=_Copy(troot->_right);returnroot;}//方法1：/*size_t_LeafSize(Node*root){staticintsize=0;if(root==NULL){returnsize;}if(root->_left==NULL&&root->_right==NULL){size++;returnsize;}_LeafSize(root->_left);_LeafSize(root->_right);}*///方法2：size_t_LeafSize(Node*root){if(root==NULL){return0;}if(root->_left==NULL&&root->_right==NULL){return1;}return_LeafSize(root->_left)+_LeafSize(root->_right);}size_t_Size(Node*root){if(root==NULL){return0;}return_Size(root->_left)+_Size(root->_right)+1;}size_t_Depth(Node*root){if(root==NULL){return0;}intLeftDepth=_Depth(root->_left);intRightDepth=_Depth(root->_right);returnLeftDepth>RightDepth?LeftDepth+1:RightDepth+1;}size_t_kLevelSize(Node*root,intk)//默认根节点为第1层{assert(k>0);if(root==NULL){return0;}if(k==1){return1;}//不可以传参数k--,不然只能是执行完这一句代码后k才会发生变化，k一直为3//不可以传参数--k,执行root->_left时，k变为2，执行root->_right时为同一层k变为1//传参数k-1return_kLevelSize(root->_left,k-1)+_kLevelSize(root->_right,k-1);}Node*_CreateTree(constT*a,size_tsize,constT&invalid,size_t&index){Node*root=NULL;if(index<size&&a[index]!=invalid){root=newNode(a[index]);root->_left=_CreateTree(a,size,invalid,++index);root->_right=_CreateTree(a,size,invalid,++index);}returnroot;}//前序遍历：访问根节点->左子树->右子树void_PrevOrder(Node*root){if(root==NULL){return;}cout<<root->_data<<"";_PrevOrder(root->_left);_PrevOrder(root->_right);}//前序遍历的非递归void_PrevOrderNon_R(Node*root){stack<Node*>s;if(root==NULL){return;}s.push(root);while(!s.empty()){root=s.top();cout<<root->_data<<"";s.pop();if(root->_right){s.push(root->_right);}if(root->_left){s.push(root->_left);}}}//中序遍历：访问左子树->根节点->右子树void_InOrder(Node*root){if(root==NULL){return;}_InOrder(root->_left);cout<<root->_data<<"";_InOrder(root->_right);}//中序遍历的非递归void_InOrderNon_R(Node*root){if(root==NULL){return;}stack<Node*>s;Node*cur=root;Node*tmp=root;while(cur||!s.empty()){while(cur){tmp=cur;s.push(cur);cur=cur->_left;}cur=s.top();//将栈顶元素保存，以便于后面判断它是否有右孩子cout<<s.top()->_data<<"";s.pop();if(cur->_right==NULL){cur=NULL;}else{cur=cur->_right;}}}//后序遍历：访问左子树->右子树->根节点void_PostOrder(Node*root){if(root==NULL){return;}_PostOrder(root->_left);_PostOrder(root->_right);cout<<root->_data<<"";}//后序遍历非递归void_PostOrderNon_R(Node*root){if(root==NULL){return;}Node*cur=root;Node*prev=NULL;stack<Node*>s;while(cur||!s.empty()){while(cur){s.push(cur);cur=cur->_left;}cur=s.top();if(cur->_right==NULL||cur->_right==prev){cout<<cur->_data<<"";s.pop();prev=cur;cur=NULL;}else{cur=cur->_right;}}}//层次遍历void_LevelOrder(Node*root){queue<Node*>q;if(root==NULL){return;}q.push(root);while(!q.empty()){if(q.front()->_left!=NULL){q.push(q.front()->_left);}if(q.front()->_right!=NULL){q.push(q.front()->_right);}cout<<q.front()->_data<<"";q.pop();}}protected:Node*_root;};#endif//__TREE_H__