Question

运用C++如何使用二叉链表存储二叉树，遍历输出叶子节点路径，递归输出叶子节点值，输出树的深度？

求代码 最好有解释 急急急！！！！！

Answer 1

构造的二叉树结构如下：

运行结果如下：

代码如下：

#include <iostream>
#include <vector>
using namespace std;

typedef struct tnode //定义树节点结构
{
	int val;
	tnode* left;
	tnode* right;
	tnode(int x=0):val(x),left(NULL),right(NULL){}//默认构造函数
}TreeNode,*pTreeNode;



void getPath(TreeNode* cur,vector<vector<TreeNode*> >&resAllPath,vector<TreeNode*> path,vector<TreeNode*>& leafNode)//深度优先遍历dfs
{
 
    path.push_back(cur);
    if(cur->left==NULL && cur->right==NULL)
    {
		leafNode.push_back(cur);
        resAllPath.push_back(path);
        return;
    }
    if(cur->left)
    {
        getPath(cur->left,resAllPath,path,leafNode);
    }
    if(cur->right)
    {
        getPath(cur->right,resAllPath,path,leafNode);
    }
        
}

vector<vector<TreeNode*> > getLeafPathAndNode(TreeNode *root,vector<TreeNode*>& leafNode) //获取叶节点及其路径
{
     
    vector<vector<TreeNode*> > resAllPath;
    vector<TreeNode*> path;
	
        
    if(root==NULL)
        return resAllPath;
        
    getPath(root,resAllPath,path,leafNode);
    return resAllPath;
      
}

void printAllPath(vector<vector<TreeNode*> >& leafPath)//打印所有叶子节点路径
{
	vector<vector<TreeNode*> >::iterator it1;
	vector<TreeNode*>::iterator it2;
	cout<<"The leaf node path is as follows:"<<endl;
	for(it1=leafPath.begin();it1!=leafPath.end();it1++)
	{
		for(it2=(*it1).begin();it2!=(*it1).end();it2++)
		{
			cout<<(*it2)->val<<" ";
		}
		cout<<endl;
	}
}
    
void printAllNode(vector<TreeNode*>& leafNode) //打印叶节点
{
	vector<TreeNode*>::iterator it;
	cout<<"The leaf node is as follows:"<<endl;
	for(it=leafNode.begin();it!=leafNode.end();it++)
	{
		cout<<(*it)->val<<" ";
	}
	cout<<endl;
}
    
int getDepth(TreeNode* root) //获取树的深度
{
	if(root==NULL)
		return 0;
	int l=getDepth(root->left);
	int r=getDepth(root->right);
	return l<r?r+1:l+1;
}


int main(void)
{
	TreeNode* node1=new TreeNode(1);  //构造一颗二叉树
	TreeNode* node2=new TreeNode(2);
	TreeNode* node3=new TreeNode(3);
	TreeNode* node4=new TreeNode(4);
	TreeNode* node5=new TreeNode(5);
	TreeNode* node7=new TreeNode(7);
	TreeNode* node8=new TreeNode(8);
	TreeNode* node9=new TreeNode(9);
	TreeNode* node11=new TreeNode(11);

	TreeNode* root=node1;

	node1->left=node2;
	node1->right=node3;
	node2->left=node4;
	node2->right=node5;
	node3->right=node7;
	node4->left=node8;
	node4->right=node9;
	node5->right=node11;

	vector<TreeNode*> leafNode;

	vector<vector<TreeNode*> > leafPath=getLeafPathAndNode(root,leafNode);
	
	printAllNode(leafNode);
	
	printAllPath(leafPath);


	int depth = getDepth(root);
	cout<<"The tree depth is "<<depth<<endl;

	
	system("PAUSE");
	return 0;
}