可以用鏈表的方式存儲二叉樹

1. 數據結構 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");
}

2. 二叉樹採用鏈表存儲結構，實現建立、遍歷（先序、中序、後序）、求結點總數、葉子數、度為1.2的結點數。

前幾天寫的，輸入二叉樹的廣義表形式，建立二叉樹的鏈式存儲。輸出的是中序。有注釋。例如輸入：a(b,c(d,e(f)),g,h(i))
#include<stdio.h>
#include<stdlib.h>
int n=0; //全局變數
struct tree //二叉樹結構體
{
char data;
struct tree *lc;
struct tree *rc;
};
tree *creat(char a[]) //創建樹的二叉樹
{
tree *h;
h=(tree *)malloc(sizeof(tree));
h->lc=NULL;
h->rc=NULL;
if(a[n]!=')'&&a[n]!='('&&a[n]!=',') //當a[n]為字母存入a[]
{
h->data=a[n];
n++;
}
if(a[n]=='(') //a[n]為左括弧對h->lc遞歸操作
{
n++;
h->lc=creat(a);
}
if(a[n]==',') //a[n]為逗號對h->rc遞歸操作
{
n++;
h->rc=creat(a);
return h;
}
if(a[n]==')') //a[n]為右括弧返回h
{
n++;
return h;
}
else
return h;

}
void print(tree *h) //二叉樹中序輸出
{
if(h!=NULL)
{
print(h->lc);
printf("%c",h->data);
print(h->rc);
}

}

int high(char a[]) //判斷樹的高度
{
int i=0,max=0,p=0;
while(a[i]!=0)
{
if(a[i]=='(')
{
p++;
if(max<i)
max=p;
}
if(a[i]==')')
p--;
i++;
}
if(p!=0)
{
printf("左右括弧數不等,輸入錯誤\n"); //判斷左右括弧數是否相等
exit(1);
}
return max+1;
}
void main() //主函數
{
int i=0;
tree *h;
char a[50]={0};
gets(a);
while(a[i]!=0) //判斷各種可能出現的輸入錯誤
{

if(i==0&&(a[i]=='('||a[i]==')'||a[i]==',')) //判斷數組首元素是否為字母
{
printf("首節點錯誤\n");
exit(1);
}
if(a[i]=='(') //左括弧之前一定是字母
{
if(a[i-1]=='('||a[i-1]==')'||a[i-1]==',')
{
printf("輸入錯誤\n");
exit(1);
}
}
if(a[i]!='('&&a[i]!=')'&&a[i]!=',') //兩個字母不能在一起
{
if(a[i+1]!='('&&a[i+1]!=')'&&a[i+1]!=',')
{
printf("輸入錯誤,兩個字母不能在一起\n");
exit(1);
}
}
i++;
}
h=creat(a); //創建樹
printf("該樹的高度為:%d\n",high(a));
printf("該二叉樹的中序輸出為:");
print(h);
printf("\n");
}

3. 二叉鏈表存儲方式實現二叉樹

用C嗎？

4. 二叉樹只能採用二又鏈表來存儲.，這個是否正確，為什麼

不是的.
二叉鏈表只是最直觀的一種存儲方式.而事實上,大部分的情況都不會使用二叉鏈表.除了一些動態調整樹的演算法比如平衡樹.
更為普遍的存儲方式是用線性表來儲存二叉樹.這種方式下,線性表N存儲的節點是N div 2的兒子節點.

5. 怎麼建立一棵以二叉鏈表方式存儲的二叉樹，並且對其進行遍歷（先序、中序和後序）

#include<stdio.h>
#include<stdio.h>
#include<malloc.h>
#include"c6_2.h"
#include<stdlib.h>#define TRUE 1
#define NULL 0
#define FALSE 0
#define ERROR 0
#define WRONG 0
#define OK 1
#define OVERFLOW 0typedef int TElemType;
typedef int Status;//二叉樹結構體
typedef struct BiTNode
{ TElemType data;//結點的值
BiTNode *lchild,*rchild;
}BiTNode,*BiTree;//隊列結構體
typedef BiTree QElemType;
typedef struct QNode
{ QElemType data;
QNode *next;
}*QueuePtr;struct LinkQueue
{ QueuePtr front,rear;//隊頭，隊尾指針
};#define ClearBiTree DestoryBiTree//清空二叉樹的操作和銷毀二叉樹的操作一樣
void InitBiTree(BiTree &T)
{ T=NULL;
}
void DestroyBiTree(BiTree &T)
{ //銷毀二叉樹
if(T)
{ DestroyBiTree(T->lchild);//銷毀左子樹
DestroyBiTree(T->rchild);//銷毀右子樹
free(T);
T=NULL;
}
}
void PreOrderTraverse(BiTree T,void(*visit)(TElemType))
{//先序遍歷二叉樹
if(T)
{ visit(T->data);
PreOrderTraverse(T->lchild,visit);
PreOrderTraverse(T->rchild,visit);
}
}
void InOrderTraverse(BiTree T,void(*visit)(TElemType))
{ //中序遍歷二叉樹
if(T)
{ InOrderTraverse(T->lchild,visit);
visit(T->data);
InOrderTraverse(T->rchild,visit);
}
}
void PostOrderTraverse(BiTree T,void(*visit)(TElemType))
{ //後序遍歷二叉樹
if(T)
{ PostOrderTraverse(T->lchild,visit);
PostOrderTraverse(T->rchild,visit);
visit(T->data);
}
}
Status BiTreeEmpty(BiTree T)
{ //判斷二叉樹是否為空
if(T)
return FALSE;
else
return TRUE;
}
int BiTreeDepth(BiTree T)//返回T的深度
{ int i,j;
if(!T)
return 0;
i=BiTreeDepth(T->lchild);//i為左孩子的深度
j=BiTreeDepth(T->rchild);//j為右孩子的深度
return i>j?i+1:j+1;
}
TElemType Root(BiTree T)
{ //返回二叉樹的根結點
if(BiTreeEmpty(T))
return NULL;
else
return T->data;
}
TElemType Value(BiTree p)
{//返回P所指結點的值
return p->data;
}
void Assign(BiTree p,TElemType value)
{ //給P的結點賦新值
p->data=value;
}BiTree Point(BiTree T,TElemType s)//返回二叉樹T中指向元素值為S的結點指針
{ LinkQueue q;
QElemType a;
if(T)
{ InitQueue(q);//初始化隊列
EnQueue(q,T);//根指針入隊
while(!QueueEmpty(q))//隊不空
{ DeQueue(q,a);//出隊，隊列元素賦給e
if(a->data==s)//a所指結點為的值為s
return a;
if(a->lchild)//有左孩子
EnQueue(q,a->lchild);//入隊左孩子
if(a->rchild)//有右孩子
EnQueue(q,a->rchild);//入隊右孩子
}
}
return NULL;
}
TElemType LeftChild(BiTree T,TElemType e)
{//返回e的左孩子
BiTree a;
if(T)
{ a=Point(T,e);//a是指向結點e的指針
if(a&&a->lchild)
return a->lchild->data;
}
return NULL;
}
TElemType RightChild(BiTree T,TElemType e)
{ BiTree a;
if(T)
{ a=Point(T,e);//a是指向結點e的指針
if(a&&a->rchild)//T中存在結點e並且e存在右孩子
return a->rchild->data;
}
return NULL;
}
Status DeleteChild(BiTree p,int LR)
{ if(p)
{ if(LR==0)
DestroyBiTree(p->lchild);
else
DestroyBiTree(p->rchild);
return OK;
}
return ERROR;
}void visit(TElemType e)
{ printf("%d",e);
}
void LevelOrderTraverse(BiTree T,void(*visit)(TElemType))
{//層序遍歷
LinkQueue q;
QElemType a;
if(T)
{ InitQueue(q);//初始化隊列
EnQueue(q,T);//根指針入隊
while(!QueueEmpty(q))
{ DeQueue(q,a);//出隊元素，賦給a
visit(a->data);//訪問a所指結點
if(a->lchild!=NULL)
EnQueue(q,a->lchild);
if(a->rchild!=NULL)
EnQueue(q,a->rchild);
}
}
}
void CreateBiTree(BiTree &T)
{ TElemType ch;scanf("%d",&ch);//輸入結點的值
if(ch==0)//結點為空
T=NULL;
else
{T=(BiTree)malloc(sizeof(BiTNode));<br>//生成根結點<br>if(!T)<br>exit(OVERFLOW);<br>T->data=ch;//將值賦給T所指結點</p><p>CreateBiTree(T->lchild);//遞歸構造左子樹<br>CreateBiTree(T->rchild);<br>} } TElemType Parent(BiTree T,TElemType e)
{//返回雙親
LinkQueue q;
QElemType a;
if(T)
{ InitQueue(q);
EnQueue(q,T);//樹根入隊列
while(!QueueEmpty(q))//隊不空
{DeQueue(q,a);//出隊，隊列元素賦給a<br> if(a->lchild&&a->lchild->data==e||a->rchild&&a->rchild->data==e)//找到e<br> return a->data;<br> else<br> { if(a->lchild)<br> EnQueue(q,a->lchild);//入隊列左孩子<br> if(a->rchild)<br> EnQueue(q,a->rchild);//入隊列右孩子<br> }
}
}
return NULL;
}
TElemType LeftSibling(BiTree T,TElemType e)
{ //返回左兄弟
TElemType a;
BiTree p;
if(T)
{ a=Parent(T,e);//a為e的雙親
if(a!=NULL)
{ p=Point(T,a);//p指向結點a的指針
if(p->lchild&&p->rchild&&p->rchild->data==e)//p存在左右孩子而且右孩子是e
return p->lchild->data;
}
}
return NULL;
}
TElemType RightSibling(BiTree T,TElemType e)
{ //返回右孩子
TElemType a;
BiTree p;
if(T)
{ a=Parent(T,e);//a為e的雙親
if(a!=NULL)
{ p=Point(T,a);//p為指向結點的a的指針
if(p->lchild&&p->rchild&&p->lchild->data==e)
return p->lchild->data;
}
}
return NULL;
}
Status InsertChild(BiTree p,int LR,BiTree c)
{ //根據LR為0或1，插入C為T中P所指結點的左或右子樹，P所結點的原有左或右子樹則成為C的右子樹
if(p)
{ if(LR==0)//把二叉樹C插入P所指結點的子樹
{ c->rchild=p->lchild;//p所結點的原有左子樹成為C的右子樹
p->lchild=c;//二叉樹成為P的左子樹
}
else{ c->rchild=p->rchild;//p指結點的原有右子樹成為C的右子樹
p->rchild=c;
}
return OK;
}
return ERROR;
}
//隊列操作
void InitQueue(LinkQueue &Q)
{//初始化一個隊列
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)//生成頭結點失敗
exit(OVERFLOW);
Q.front->next=NULL;
}
Status QueueEmpty(LinkQueue Q)
{ //判斷隊列是否為空
if(Q.front->next==NULL)
return TRUE;
else return FALSE;
}void EnQueue(LinkQueue &Q,QElemType e)
{ //插入元素e為隊列Q的新的隊尾元素
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
//動態生成新結點
if(!p)
exit(OVERFLOW);
p->data=e;//將e的值賦給新結點
p->next=NULL;//新結點的指針為空
Q.rear->next=p;//原隊尾結點的指針域為指向新結點
Q.rear=p;//尾指針指向新結點
}
Status DeQueue(LinkQueue &Q,QElemType &e)
{ //若隊列不為空，刪除Q的隊頭元素，用e返回其值
QueuePtr p;
if(Q.front==Q.rear)//隊列為空
return ERROR;
p=Q.front->next;//p指向隊頭結點
e=p->data;//隊頭元素賦給e
Q.front->next=p->next;//頭結點指向下一個結點
if(Q.rear==p)//如果刪除的隊尾結點
Q.rear=Q.front;//修改隊尾指針指向頭結點
free(p);
return OK;
}
//主函數文件
#include<stdio.h>
#include"c6_2.h"main()
{ int i,j;
BiTree T,p,c;
TElemType e0,e1,e2,e3,e4;
InitBiTree(T);//初始化二叉樹
printf("構造二叉樹後，樹空否?%d(1,是,0否).樹的深度=%d.\n",BiTreeEmpty(T),BiTreeDepth(T));CreateBiTree(T);//建立二叉樹T
printf("構造二叉樹後，樹空否?%d(1,是,0否).樹的深度=%d.\n",BiTreeEmpty(T),BiTreeDepth(T));
e1=Root(T);//e1為二叉樹T的根結點的值
if(e1!=NULL)
printf("二叉樹的根為%d",e1);
else
printf("樹空，無根");e2=LeftChild(T,e1);
printf("左孩子:%d",e2);
e3=RightChild(T,e1);
printf("右孩子:%d",e3);
printf("\n");printf("先序遞歸遍歷:\n");
PreOrderTraverse(T,visit);
printf("\n");printf("後序遞歸遍歷:\n");
PostOrderTraverse(T,visit);
printf("\n");printf("中序遞歸遍歷:\n");
InOrderTraverse(T,visit);
printf("\n");printf("輸入一個結點的值:");
scanf("%d",&e1);
p=Point(T,e1);//p指向為e的指針
printf("結點的值為%d\n",Value(p));
e0=Parent(T,e1);//返回e1的雙親
printf("結點%d的雙親為%d",e1,e0);
printf("\n");e0=LeftChild(T,e1);//返回e1的左孩子
if(e0==NULL)
printf("沒有孩子");
else
printf("左孩子為%d",e0);
printf("\n");e0=RightChild(T,e1);//返回e1的右孩子
if(e0==NULL)
printf("沒有右孩子");
else
printf("右孩子為%d",e0);
printf("\n");
e0=RightSibling(T,e1);//返回e1的右兄弟
if(e0!=NULL)
printf("右兄弟為%d",e0);
else
printf("沒有右兄弟");
printf("\n");e0=LeftSibling(T,e1);//返回e1的左兄弟
if(e0!=NULL)
printf("左兄弟為%d",e0);
else
printf("沒有左兄弟");
printf("\n");
printf("要改變結點%d的值，請輸入新值:",e1);
scanf("%d",&e2);
Assign(p,e2);//將e2的值賦給p所指結點，代替e1
printf("層序遍歷二叉樹:\n");
LevelOrderTraverse(T,visit);
printf("\n");
printf("創建一棵根結點右子樹為空的新樹:");
CreateBiTree(c);//創建二叉樹
printf("先序遞歸遍歷二叉樹c:\n");
PreOrderTraverse(c,visit);
printf("將樹C插入樹T中，請輸入樹T中樹C的雙親結點C為左（0）或右（1）子樹:");
scanf("%d,%d",&e1,&i);
p=Point(T,e1);//p指向二叉樹T中將T中作為二叉樹C的雙親結點的e1
InsertChild(p,i,c);//將樹C插入到二叉樹T中作為結點的左或右子樹
printf("構造二叉樹後，樹空否?%d(1,是,0否).樹的深度=%d.\n",BiTreeEmpty(T),BiTreeDepth(T));
printf("先序遞歸遍歷二叉樹:\n");
PreOrderTraverse(T,visit);
}

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

7. 二叉鏈表存儲結構，實現二叉樹的遍歷

前幾天寫的，輸入二叉樹的廣義表形式，建立二叉樹的鏈式存儲。輸出的是中序。有注釋，看懂了應該其他的都能寫了吧。#include<stdio.h>
#include<stdlib.h>
int n=0; //全局變數
struct tree //二叉樹結構體
{
char data;
struct tree *lc;
struct tree *rc;
};
tree *creat(char a[]) //創建樹的二叉樹
{
tree *h;
h=(tree *)malloc(sizeof(tree));
h->lc=NULL;
h->rc=NULL;
if(a[n]!=')'&&a[n]!='('&&a[n]!=',') //當a[n]為字母存入a[]
{
h->data=a[n];
n++;
}
if(a[n]=='(') //a[n]為左括弧對h->lc遞歸操作
{
n++;
h->lc=creat(a);
}
if(a[n]==',') //a[n]為逗號對h->rc遞歸操作
{
n++;
h->rc=creat(a);
return h;
}
if(a[n]==')') //a[n]為右括弧返回h
{
n++;
return h;
}
else
return h;

}
void print(tree *h) //二叉樹中序輸出
{
if(h!=NULL)
{
print(h->lc);
printf("%c",h->data);
print(h->rc);
}

}

int high(char a[]) //判斷樹的高度
{
int i=0,max=0,p=0;
while(a[i]!=0)
{
if(a[i]=='(')
{
p++;
if(max<i)
max=p;
}
if(a[i]==')')
p--;
i++;
}
if(p!=0)
{
printf("左右括弧數不等,輸入錯誤\n"); //判斷左右括弧數是否相等
exit(1);
}
return max+1;
}
void main() //主函數
{
int i=0;
tree *h;
char a[50]={0};
gets(a);
while(a[i]!=0) //判斷各種可能出現的輸入錯誤
{

if(i==0&&(a[i]=='('||a[i]==')'||a[i]==',')) //判斷數組首元素是否為字母
{
printf("首節點錯誤\n");
exit(1);
}
if(a[i]=='(') //左括弧之前一定是字母
{
if(a[i-1]=='('||a[i-1]==')'||a[i-1]==',')
{
printf("輸入錯誤\n");
exit(1);
}
}
if(a[i]!='('&&a[i]!=')'&&a[i]!=',') //兩個字母不能在一起
{
if(a[i+1]!='('&&a[i+1]!=')'&&a[i+1]!=',')
{
printf("輸入錯誤,兩個字母不能在一起\n");
exit(1);
}
}
i++;
}
h=creat(a); //創建樹
printf("該樹的高度為:%d\n",high(a));
printf("該二叉樹的中序輸出為:");
print(h);
printf("\n");
}

8. 運用C++如何使用二叉鏈表存儲二叉樹，遍歷輸出葉子節點路徑，遞歸輸出葉子節點值，輸出樹的深度

構造的二叉樹結構如下：