运用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;
}
...采用二叉链表存储,然后分别实现前序,中序,后序遍历该二叉树_百度...
答：int creat(list*root){ //创建一棵二叉树，root使用的是二维指针 char n;scanf(" %c",&n); //注%C前面加空格是为了起间隔作用 scanf不读入空格 if (n=='0') //0为间隔 { root=NULL; return 0; //输入结束 } root=(list)malloc(sizeof(bt));if (!*root) return 0;(*root...
...建立一棵含有n个结点的二叉树,采用二叉链表存储;
答：printf("%c",ptr->ch);} } void main(){ printf("构建一个二叉树（结点数为n)：\n");root=create(root);printf("前序遍历二叉树：\n");preorder(root);printf("\n");printf("中序遍历二叉树：\n");inorder(root);printf("\n");printf("后序遍历二叉树：\n");postorder(root);...
用C语言定义二叉树的二叉链表存储结构,完成二叉树的建立,先序中序后...
答：typedef int ElemType;typedef struct LNode{ ElemType data;struct LNode *lchild,*rchild;}LNode,*TLNode;void create(TLNode * Tree){ //创建 ElemType e;scanf("%d",&e);if(e==0)Tree=NULL;else{ (*Tree)=(TLNode)malloc(sizeof(LNode));(*Tree)->data=e;printf("input %d lch...
用C语言建立一棵二叉树,使用二杈链表存储,对其进行后续遍历,输出后序...
答：printf("%c",b->data);if(b->lchild!=NULL||b->rchild!=NULL){ printf("(");DispBTNode(b->lchild);if(b->rchild!=NULL)printf(",");DispBTNode(b->rchild);printf(")");} } } BTNode *FindNode(BTNode *b,char x){ BTNode *p=NULL;if(b==NULL){ return NULL;} else if...
二叉链表表示二叉树,复制一颗二叉树,如何用C语言算法设计,希望答案正确...
答：2007-12-11 用C语言编写:建立一棵以二叉链表结构存储的二叉树,并对其进行... 5 2012-10-12 给二叉链表的每个节点增加一个域,求二叉树的每个节点的子孙数且... 2013-09-11 数据结构:写一个算法求一颗二叉树的深度,二叉树以二叉链表为存... 5 更多...
C语言编写的数据结构
答：实验一:用二叉链表作为存储结构,建立二叉树,对二叉树进行前序、后序遍历,并对建立的二叉树进行中序线索,再中序线索遍历。实验二:根据给定的权值建立哈夫曼树,进行前序遍历。/*建... 实验一:用二叉链表作为存储结构,建立二叉树,对二叉树进行前序、后序遍历,并对建立的二叉树进行中序线索,再中序线索遍历。实验...
以二叉链表作存储结构,编写二叉树深度的递归算法(c++语言)
答：typedef int Status;//二叉树的二叉链表存储结构 typedef struct BiTNode{ TElemType data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;//先序遍历生成二叉树 Status CreatBiTree(BiTree &T){ TElemType ch,temp;printf("输入一个元素: ");scanf("%c",&ch);temp=getchar(); //结束回车 ...
帮忙用C++编一下:以二叉链表为存储结构,在二叉树中删除以值x为根结点...
答：} } int main(){ char str[100],x;BTnode *b;printf("请输入二叉树的字符串:");gets(str);printf("\n要删除的子树的根节点为：");scanf("%c",&x);create(b,str);printf("\n删除根节点为%c的子树后的二叉树字符串为：",x);Delete(b,x);printf("\n\n");system("pause");...
C++: 设计算法将一棵以二叉链表形式存储的二叉树转换为顺序存储形式存储...
答：//建立二叉链表存储结构的二叉树,以p1为根节点，p2,p3分别为p1的左右子树，p4为p3的左子树 struct BTNode p1,p2,p3,p4;struct BTNode *t=&p1;p1.data='a';p2.data='b';p3.data='c';p4.data='d';p1.lchild=&p2;p1.rchild=&p3;p2.lchild=NULL;p2.rchild=NULL;p3.lchild=&p4;...
采用二叉链表作为存储结构,完成二叉树的建立,前序、中序和后序遍历的...
答：void Traverse(BiTree T)//前序遍历二叉树 { if(NULL==T){ return;} else { printf("%d ",T->data);Traverse(T->Lchild);Traverse(T->Rchild);} } //中序遍历二叉树 void midTraverse(BiTree T){ if(T==NULL){return;} midTraverse(T->Lchild);printf("%d ",T->data);mid...
