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