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

public void visit(Node n){ if(null != n){ // 递归访问其左子树 visit(n.lchild); if(null == n.lchild && null == n.rchild){ // 当前节点是叶子，则访问它 System.out.println(n); } // 递归访问其右子树 visit(n.rchild); }}

#include
using namespace std;

typedef struct TNode//二叉树结构
{
char nodeValue;//结点的值
TNode* left;//左子树
TNode* right;//右子树
}*BiTree;
void CreateBiTree(BiTree &T)//中序遍历方式创建二叉树 ,输入#代表该结点为空
{
char nodeValue;
cin>> nodeValue;
if(nodeValue!='#')//结点非空
{
T=new TNode;
T->nodeValue=nodeValue;
CreateBiTree(T->left);
CreateBiTree(T->right);
}
else T=NULL;

}
int CountLeaf(BiTree T)
{
static int LeafNum=0;//叶子初始数目为0，使用静态变量
if(T)//树非空
{
if(T->left==NULL&&T->right==NULL)//为叶子结点
LeafNum++;//叶子数目加1
else//不为叶子结点
{
CountLeaf(T->left);//递归统计左子树叶子数目
CountLeaf(T->right);//递归统计右子树叶子数目
}
}
return LeafNum;
}
//用来测试的main函数，
int main()
{
BiTree T;
int leafNum;
cout<<"请输入中序遍历的二叉树序列(#号代表该结点为空)：如(ABC##DE#G##F###)"<<endl;
CreateBiTree(T);
leafNum=CountLeaf(T);
cout<<"该二叉树中叶子结点数为："<<leafNum<<endl;
return 0;
}

构造的二叉树结构如下：

运行结果如下：

代码如下：

#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;
}