二叉树所有根到叶子节点路径打印

思路:如果二叉树根结点不为空,则将根结点值保存到设定的数组中,再递归遍历根结点的左子树和右子树,如果结点的左右子树都为空,则打印出数组中数据。

代码:

#include <iostream>
using namespace std;

struct TreeNode 
{
	int m_pData;
	TreeNode* m_pLeft;
	TreeNode* m_pRight;
};

void CreateTree(int *p, int len, TreeNode* &pHead)
{
	if(len > 0)
	{
		pHead = new TreeNode;
		int mid = len / 2;
		pHead->m_pData = p[mid];
		pHead->m_pLeft = NULL;
		pHead->m_pRight = NULL;
		CreateTree(p,mid,pHead->m_pLeft);
		CreateTree(p+mid+1,len-mid-1,pHead->m_pRight);
	}
	else
	{
		pHead = NULL;
	}
}

void InOrder(TreeNode *pHead)
{
	if(pHead != NULL)
	{
		InOrder(pHead->m_pLeft);
		cout<<pHead->m_pData<<" ";
		InOrder(pHead->m_pRight);
	}
}

/////////////////////////////////打印二叉树路径
void printArr(int ar[],int len)
{
	for(int i = 0; i < len; ++i)
	{
		cout<<ar[i]<<" ";
	}
	cout<<endl;
}

void PrintTreePaths(TreeNode *pHead,int path[],int pathLen)
{
	if(pHead == NULL)
		return ;
	path[pathLen] = pHead->m_pData;
	pathLen++;

	if(pHead->m_pLeft == NULL && pHead->m_pRight == NULL)
		printArr(path,pathLen);
	else
	{
		PrintTreePaths(pHead->m_pLeft,path,pathLen);
		PrintTreePaths(pHead->m_pRight,path,pathLen);
	}
}

void PrintPaths(TreeNode *pHead)
{
	int path[1000];
	PrintTreePaths(pHead,path,0);
}

int main()
{
	int arr[] = {1,2,3,4,5,6,7,8,9,10};
	TreeNode *pHead = NULL;
	CreateTree(arr,sizeof(arr)/sizeof(arr[0]),pHead);
	
	InOrder(pHead);
	cout<<endl;

	PrintPaths(pHead);
	
	return 0;
}
相关文章
相关标签/搜索
每日一句
    每一个你不满意的现在,都有一个你没有努力的曾经。
公众号推荐
   一个历史类的公众号,欢迎关注
一两拨千金