1. 运用C++如何使用二叉链表存储二叉树，遍历输出叶子节点路径，递归输出叶子节点值，输出树的深度
构造的二叉树结构如下：
2. c++ 采用二叉链表作存储结构，实现二叉树非递归后序遍历算法
链接存储的二叉树类型和结构定义如下:
typedef
struct
bnode
{
ElemType
data;
struct
bnode
*lchild,
*rchild;
}
btree;
后序遍历
void
postorder(btree
*bt)
{
btree
*p=bt,
*stack[MAX];//p表示当前结点，栈stack[]用来存储结点
int
tag[MAX];
int
top=-1;
do
{
while(p
!=
NULL)//先处理结点的左孩子结点，把所有左孩子依次入栈
{
stack[++top]
=
p;
tag[top]
=
0;
p
=
p->lchild;
}
if(top
>=
0)
//所有左孩子处理完毕后
{
if(!tag[top])
//如果当前结点的右孩子还没被访问
{
p
=
stack[top];//输出栈顶结点
，但不退栈
，因为要先输出其孩子结点
p
=
p->rchild;
//处理其右孩子结点
tag[top]
=
1;
//表示栈中top位置存储的结点的右孩子被访问过了，下次轮到它退栈时可直接输出
}
else
//如果该结点的左右孩子都被访问过了
{
printf("%d",
stack[top--]->data);
//栈顶元素出栈，输出该结点，此时结点p指向NULL
}
}
}
while((p
!=
NULL)||(top
>=
0));
}
3. 用c语言定义二叉树的二叉链表存储结构，完成二叉树的建立，先序中序后序遍历的操作，求所有叶子结点总数
#include<stdio.h>
#include<malloc.h>
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 lchild: ",e);
create(&(*Tree)->lchild);
printf("input %d rchild: ",e);
create(&(*Tree)->rchild);
}
}
void print1(TLNode Tree){ //先序遍历
if(Tree!=NULL){
printf("%d-",Tree->data);
print1(Tree->lchild);
print1(Tree->rchild);
}
}
void print2(TLNode Tree){ //中序遍历
if(Tree!=NULL){
print2(Tree->lchild);
printf("%d-",Tree->data);
print2(Tree->rchild);
}
}
void print3(TLNode Tree){ //后序遍历
if(Tree!=NULL){
print3(Tree->lchild);
print3(Tree->rchild);
printf("%d-",Tree->data);
}
}
int leaf=0; //求叶子节点数
int depth(TLNode Tree){ //深度
int s1,s2;
if(Tree==NULL)
return 0;
else{
s1=depth(Tree->lchild);
s2=depth(Tree->rchild);
if(s1==0 && s2==0) leaf++;
return (s1>s2?s1:s2)+1;
}
}
int Cnode(TLNode Tree){ //总结点
int s1,s2;
if(Tree==NULL)
return 0;
else{
s1=Cnode(Tree->lchild);
s2=Cnode(Tree->rchild);
return s1+s2+1;
}
}
void main(){
TLNode Tree;
printf("input 根节点: ");
create(&Tree);
printf("先序遍历:");
print1(Tree);
printf("中序遍历");
print2(Tree);
printf("后序遍历");
print3(Tree);
printf(" 深 度:%d ",depth(Tree));
printf("总结点数:%d ",Cnode(Tree));
printf("叶子结点数:%d ",leaf);
}
4. 数据结构 c语言版二叉树(1) 建立一棵含有n个结点的二叉树，采用二叉链表存储；
#include<stdio.h>
#include<stdlib.h>
typedef struct node *tree_pointer;
struct node{
char ch;
tree_pointer left_child,right_child;
};
tree_pointer root=NULL;
tree_pointer create(tree_pointer ptr)
{
char ch;
scanf("%c",&ch);
if(ch==' ')
ptr=NULL;
else{
ptr=(tree_pointer)malloc(sizeof(node));
ptr->ch=ch;
ptr->left_child=create(ptr->left_child);
ptr->right_child=create(ptr->right_child);
}
return ptr;
}
void preorder(tree_pointer ptr)
{
if(ptr){
printf("%c",ptr->ch);
preorder(ptr->left_child);
preorder(ptr->right_child);
}
}
void inorder(tree_pointer ptr)
{
if(ptr){
inorder(ptr->left_child);
printf("%c",ptr->ch);
inorder(ptr->right_child);
}
}
void postorder(tree_pointer ptr)
{
if(ptr){
postorder(ptr->left_child);
postorder(ptr->right_child);
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);
printf("\n");
}
5. 采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作
#include<iostream>
#include<cstdio>
#include<stdlib.h>
using namespace std;
typedef int Elemtype;
typedef struct BiTnode
{
Elemtype data;//数据域
struct BiTnode* Lchild,*Rchild; //左右子树域；
}BiTnode,*BiTree;
int create(BiTree *T)
{
Elemtype ch;
Elemtype temp;
scanf("%d",&ch);
temp=getchar();
if(ch==-1)
{
*T=NULL;
}
else
{
*T=(BiTree)malloc(sizeof(BiTnode) );
if(!(*T))
{
exit(-1);
}
else
{
(*T)->data=ch;
printf("请输入%d的左节点的值",ch);
create(&(*T)->Lchild);
printf("请输入%d的右节点的值",ch);
create(&(*T)->Rchild);
}
}
return 1;
}
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);
midTraverse(T->Rchild);
}
//后序遍历二叉树
void lasTraverse(BiTree T)
{
if(T==NULL){return;}
lasTraverse(T->Lchild);
lasTraverse(T->Rchild);
printf("%d ",T->data);
}
//求二叉树的深度
int TreeDeep(BiTree T)
{
int deep=0;
if(T)
{
int leftdeep=TreeDeep(T->Lchild);
int rightdeep=TreeDeep(T->Rchild);
deep=leftdeep>=rightdeep?leftdeep+1:rightdeep+1;
}
return deep;
}
//求二叉树叶子节点个数
int Leafcount(BiTree T,int &num)
{
if(T)
{
if(T->Lchild==NULL&&T->Rchild==NULL)
{
num++;
}
Leafcount(T->Lchild,num);
Leafcount(T->Rchild,num);
}
return num;
}
int main()
{
BiTree T;
BiTree *p=(BiTree*)malloc(sizeof(BiTree));
int deepth=0,num=0;
printf("请输入第一个节点的值，-1代表没有叶节点: ");
create(&T);
printf("先序遍历二叉树： ");
Traverse(T);
printf(" ");
printf("中序遍历二叉树: ");
midTraverse(T);
printf(" ");
printf("后序遍历二叉树： ");
lasTraverse(T);
printf(" ");
deepth=TreeDeep(T);
printf("树的深度:%d ",deepth);
printf(" ");
Leafcount(T,num);
printf("二叉树的叶子节点个数为:%d ",num);
printf(" ");
return 0;
(5)c语言二叉树的链式存储及遍历扩展阅读：
二叉链表是树的二叉链表实现方式。
树的二叉链表实现方式：（孩子兄弟表示法）
以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。
结构描述：
typedefstruct CSNode{
ElemType data；
struct CSNode *firstchild ， *netsibling；
} CSNode，* CSTree；
由于二叉树的存储结构比较简单，处理起来也比较方便，所以有时需要把复杂的树，转换为简单的二叉树后再作处理。
6. 二叉树的顺序存储结构数据A B C D E
二叉树结构链式图：
A
/
\
B
C
/
\
D
E
前序遍历：（根，左，右）：
A
->
B -> D -> E -> C中序遍历：（左，根，右）：
D -> B -> E -> A -> C后序遍历：（左，右，根）：
D -> E -> B -> C -> A
前序
中序
后序
遍历，主要是以根节点做为参考点，进行遍历。（根，左，右）
遍历顺序中
‘根’
在第一个，所以叫前序遍历。（左，根，右） 遍历顺序中
‘根’
在第二个，所以叫中序遍历。（左，右，根） 遍历顺序中
‘根’
在第三个，所以叫后序遍历。
7. c语言如何实现一棵二叉树的遍历
今天我也遇到这道题了，经过我的研究，我觉得应该是如下的解答：
首先画出该树 ：如下图左边所示。然后根据树的二叉链表表示法表示存储结构如图右边所示：
注意这里的指针域为左边表示第一个孩子*firstchild，右边表示兄弟*nextsibling
8. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。
答案：C。用二叉链表存储结构也就是左孩子右兄弟的存储结构。
后序遍历比较合理。正常的逻辑应该就是：做好当前结点子树内部的交换，然后交换当前结点的左右子树。刚好符合后序遍历的算法逻辑。
1、交换好左子树
2、交换好右子树
3、交换左子树与右子树
其他算法如先序和按层次其逻辑都差不多，即访问当前结点时交换其左右子树。从逻辑上来看稍显别扭一点点。因此说最合适应该是后序遍历，但是从实现上来说先序和按层次都是可以的。
1、交换左子树与右子树
2、遍历左子树
3、遍历右子树
按层次遍历
1、根结点入队列
2、出队列，交换其左右子树，将子树的根入队列
3、重复2直到队列为空
中序遍历相对较难实现一些。
(8)c语言二叉树的链式存储及遍历扩展阅读：
树的遍历是树的一种重要的运算。树的3种最重要的遍历方式分别称为前序遍历、中序遍历和后序遍历。
以这3种方式遍历一棵树时，若按访问结点的先后次序将结点排列起来，就可分别得到树中所有结点的前序列表、中序列表和后序列表。相应的结点次序分别称为结点的前序、中序和后序。
9. 用C语言建立一棵二叉树,使用二杈链表存储,对其进行后续遍历,输出后序遍历序列
#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
#define Maxsize 100
typedef int datatype;
typedef struct node
{
datatype data;
struct node* lchild;
struct node* rchild;
}BTNode;
void CreatBTNode(BTNode *&b,char * str)
{
BTNode *p,*st[Maxsize];
int top=-1;
p=NULL;
b=NULL;
int j=0,k;
char ch=str[j];
while(ch!='\0')
{
switch(ch)
{
case '(':top++;st[top]=p;k=1;break;
case ')':top--;break;
case ',':k=2;break;
default:p=(BTNode *)malloc(sizeof(BTNode));
p->data=ch;p->lchild=p->rchild=NULL;
if(b==NULL)
{
b=p;
}
else
{
switch(k)
{
case 1:st[top]->lchild=p;break;
case 2:st[top]->rchild=p;break;
}
}
}
j++;ch=str[j];
}
}
void DispBTNode(BTNode *b)
{
if(b!=NULL)
{
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(b->data==x)
{
return b;
}
else
{
p=FindNode(b->lchild,x);
if(p!=NULL)
{
return p;
}
else
{
return FindNode(b->rchild,x);
}
}
}
void main()
{
BTNode *b,*q;
char str[100];
printf("您输入的二叉树为\n");
scanf("%s",&str);
CreatBTNode(b,str);
DispBTNode(b);
q=FindNode(b,'A');
printf("\n");
printf("*********************************\n");
printf("%c\n",q->data);
}