[数据结构与算法]二叉树遍历及基本操作

一、二叉树遍历

1、前序遍历（根左右----DLR）

/* 递归 */
void PreOrder(BiTNode *root)
{
	if(root == nullptr)
		return;
	cout<<root->data<<" ";   //先输出当前结点
	PreOrder(root->lchild);        //输出左孩子
	PreOrder(root->rchild);        //输出右孩子
}

/* 非递归 */
void PreOrder(BiTNode *root)
{
	if(root == nullptr)
		return;
	stack<BiTNode*> st;
	cout<<root->data<<" "<<endl;   //先输出当前结点
	st.push(root);                  //入栈
	root = root->lchild;
	while(!st.empty() || root)
	{
		while(root)
		{
			cout<<root->data<<" ";  //先输出当前结点
			st.push(root);        
			root = root->lchild;    //再输出左孩子
		}
		// while 结束意味着左孩子已经全部输出,开始输出右孩子
		root = st.top()->rchild;
		st.pop();
	}
}

2、中序遍历（左根右----LDR）

/* 递归 */
void InOrder(BiTNode *root)
{
	if(root == nullptr)
		return;
	InOrder(root->lchild);        //输出左孩子
	cout<<root->data<<" ";         //输出当前结点
	InOrder(root->rchild);        //输出右孩子
}

/* 非递归 */
void InOrder(BiTNode *root)
{
	if(root == nullptr)
		return;
	stack<BiTNode*> st;
	st.push(root);                 
	root = root->lchild;      //访问左孩子
	while(!st.empty() || root)
	{
		while(root)
		{
			st.push(root);
			root = root->lchild;
		}
		//左孩子已遍历完，进行输出
		cout<<st.top()->data<<" ";   
		root = st.top()->rchild;     //遍历右孩子
		st.pop();
	}
}

3、后序遍历（左右根----LRD）

/* 递归 */
void PostOrder(BiTNode *root)
{
	if(root == nullptr)
		return;
	PostOrder(root->lchild);
	PostOrder(root->rchild);
	cout<<root->data<<" ";
}

/* 非递归 */
/*
对于一个结点，如果要输出它，只有它既没有左孩子也没有右孩子或者它有孩子但是它的孩子已经被输出（由此设置 pre 变量）。若非上述两种情况，则将该结点的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候,先依次遍历左子树和右子树
*/
void PostOrder(BiTNode *root)
{
	if(root == nullptr)
		return;
	stack<BiTNode*> st;
	BiTNode *pre = nullptr;
	st.push(root);                 
	while(!st.empty() || root)
	{
		root = st.top();            //取栈顶元素判断
		if((root->lchild==nullptr && root->rchild==nullptr)||
		(pre && (pre == root->lchild || pre == root->rchild)))
		{
			//首先输出的是无左右孩子结点或者它有孩子但是它的孩子已经被输出
			cout<<root->data<<" ";
			pre = root;
			st.pop();
		}
		else
		{
			if(root->rchild)
				st.push(root->rchild);   //先右后左进栈，出来就是先左后右
			if(root->lchild)
				st.push(root->lchild);
		}
	}
}

4、层次遍历

基于广度优先搜搜思想的二叉树遍历算法，依次对于每一层进行遍历，直到遍历到二叉树最下面一层的结点为止，需要用一个队列结构辅助实现（先进先出）。

void LayerOrder(BiTNode *root)
{
	queue<BitNode*> Q;
	BiTNode *p = root;
	if(p == nullptr)
		return;
	Q.push(p);               //入队
	while(!Q.empty())
	{
		p = Q.front();      //取出队头元素并输出
		cout<<p->data<<" ";
		Q.pop();
		//从左到右依次入队
		if(p->lchild)
			Q.push(p->lchild);
		if(p->rchild)
			Q.push(p->rchild);
	}
}

二、二叉树的深度和叶子结点个数

1、二叉树深度

深度优先遍历，比较左右深度

int maxDepth(BiTNode* root)
{
    if(root == nullptr)
        return 0;
    int left_len = maxDepth(root->left) + 1;
    int right_len = maxDepth(root->right) + 1;
    return left_len>right_len?left_len:right_len;
}

2、二叉树叶子节点数

所谓叶子结点就是其左孩子和右孩子均为NULL的结点。遍历整棵二叉树，统计叶子结点个数。

int getLeavesCount(BiTNode *root)
{
	if(root == nullptr)
		return 0;
	if(root->left==nullptr && root->right==nullptr)
		return 1;
	return getLeavesCount(root->left) + getLeavesCount(root->left);
}
//如果是求树的结点数,直接就是遍历左右子树加上根结点
int getCount(BiTNode *root)
{
	if(root == nullptr)
		return 0;
	return getCount(root->left) + getCount(root->left) + 1;
}