1. 二叉樹的存儲結構是怎樣的有哪些類型的存儲結構對應的c語言描述是
線性表的鏈式存儲結構：
typedef
int
elemtype;
typedef
struct
lnode
{
elemtype
data;
struct
lnode
*next;
}lnode,*linklist;
(被封裝好的每個節點，都有一個數據域data和一個指針域*next用於指向下一個節點)
二叉樹的二叉鏈表：
typedef
int
telemtype;
typedef
struct
bitnode
{
telemtype
data;
struct
bitnode
*lchild,*rchild;
}bitnode,*bitree;
(被封裝好的每個節點，都有一個數據域data和兩個指針域
*lchild,*rchild分別指向左右子樹)
需要什麼類型的數據作為數據域可更改，或者typedef
int
elemtype;和typedef
int
telemtype;中的int，比如改為char、float等或者自定義數據類型。
2. 以二叉鏈表為存儲結構,寫一演算法交換各結點的左右子樹
問題：以二叉鏈表為存儲結構， 寫一演算法交換各結點的左右子樹核彎。
答案：
要交換各結點的左右子樹，最方便的辦法是用後序遍歷演算法，每訪問一個結點時把兩棵子樹的指針進行交換，最後一次訪問是交換根結點的子樹。
void ChangeBinTree(BinTree *T)
{ //交換子樹
if(*T)
{ //這里孝模以指針為參數使得交換在實參的結點上進巧氏緩行後序遍歷
BinTree temp;
ChangeBinTree(&(*T)->lchild);
ChangeBinTree(&(*T)->rchild);
temp=(*T)->lchild;
(*T)->lchild=(*T)->rchild;
(*T)->rchild=temp;
}
}
3. 分別寫出線性表的鏈式存儲結構、二叉樹的二叉鏈表存儲機構的類C語言描述
線性表的鏈式存儲結構：
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
(被封裝好的每個節點，都有一個數據域data和一個指針域*next用於指向下一個節點)
二叉樹的二叉鏈表：
typedef int TElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
(被封裝好的每個節點，都有一個數據域data和兩個指針域 *lchild,*rchild分別指向左右子樹)
需要什麼類型的數據作為數據域可更改，或者typedef int ElemType;和typedef int TElemType;中的int，比如改為char、float等或者自定義數據類型。
4. 二叉鏈表作存儲結構
//偶爾看到提問，翻了翻以前的課程設計，大部分功能類似...就直接復制上來啦，不知道能幫上忙不...都這么久了
//vc++ 6.0
#include "iostream.h"
#include "stdlib.h"
#include "stdio.h"
#define OK 1
#define NULL 0
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef char ElemType;//定義二叉樹結點值的類型為字元型
const int MaxLength=10;//結點個數不超過10個
typedef struct BTNode{
ElemType data;
struct BTNode *lchild,*rchild;
}BTNode,* BiTree;
void CreateBiTree(BiTree &T){//按先序次序輸入，構造二叉鏈表表示的二叉樹T，空格表示空樹
char ch;
ch=getchar(); //不能用cin來輸入，在cin中不能識別空格。
if(ch==' ') T=NULL;
else
{
if(!(T=(BTNode *)malloc(sizeof(BTNode)))) cout<<"malloc fail!";
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
void PreOrderTraverse(BiTree T){//先序遍歷
if(T){
cout<<T->data<<' ';
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiTree T){ //中序遍歷
if(T){
InOrderTraverse(T->激渣做lchild);
cout<<T->data<<' ';
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiTree T){ //後序遍歷
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data<<' ';
}
}
void LevelOrderTraverse(BiTree T){ //層序遍歷
BiTree Q[MaxLength];
int front=0,rear=0;
BiTree p;
if(T){ //根梁歲結點入隊
Q[rear]=T;
rear=(rear+1)%MaxLength;
}
while(front!=rear){
p=Q[front]; //隊頭元素出隊
front=(front+1)%MaxLength;
cout<<p->data<<' ';
if(p->lchild){ //左孩明衡子不為空，入隊
Q[rear]=p->lchild;
rear=(rear+1)%MaxLength;
}
if(p->rchild){ //右孩子不為空，入隊
Q[rear]=p->rchild;
rear=(rear+1)%MaxLength;
}
}
}
int BTDepth(BiTree T){ //二叉樹的深度
if(!T) return 0;
else{
int h1=BTDepth(T->lchild);
int h2=BTDepth(T->rchild);
if(h1>h2) return h1+1;
else return h2+1;
}
}
int Leaf(BiTree T){ //二叉樹的葉子數
if(!T)
return 0;
else if(!T->lchild&&!T->rchild)
return 1;
else
return(Leaf(T->lchild)+Leaf(T->rchild));
}
int NodeCount(BiTree T){ //二叉樹的結點總數
if(!T)
return 0;
else
return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
int Initbitree (BiTree T) //空樹
{
T=NULL;
return FALSE;
}
int Isempty(BiTree T) //判斷為空否
{
if(T!=NULL)
return FALSE;
else
return TRUE;
}
int Destroy (BiTree &T) //銷毀
{
if( T != NULL )
{ if(T->lchild!=NULL)
Destroy ( T->lchild );
if(T->rchild!=NULL)
Destroy ( T->rchild );
free(T);
T=NULL;
}
return 1;
}
char Root(BiTree T) //返回根節點
{
if(T==NULL)
return NULL;
else
return T->data;
}
ElemType Value(BiTree &p)
{//返回P所指結點的值
return p->data;
}
ElemType Assign(BiTree p,ElemType value)
{ //給P的結點賦新值
return p->data=value;
}
BiTree Parent(BiTree T, BiTree p)//返回父節點
{
if(T!=NULL)
{
if(T->lchild->data==p->data)
{return T;}
if(T->rchild->data==p->data)
return T;
if(T->lchild)
return Parent(T->lchild,p);
if(T->rchild)
return Parent(T->rchild,p);
}
else return NULL;
}
char LeftChild(BiTree p) //返回p的左孩子的值
{
if(p->lchild) //若p存在左孩子
return p->lchild->data;
if(p->lchild==NULL)
return NULL;
}
char RightChild(BiTree p) // 返回p的右孩子的值
{
if(p->rchild)
return p->rchild->data;
if(p->rchild==NULL)
return NULL;
}
int Deletelchild(BiTree p) //刪除此二叉樹中p節點的左子樹
{
if(p)
{
Destroy(p->lchild);
return OK;
}
return ERROR;
}
int Deleterchild(BiTree p) //刪除此二叉樹中p節點的右子樹
{
if(p)
{
Destroy(p->rchild);
return OK;
}
return ERROR;
}
void search(BiTree T,char h,BiTree &p)//查詢節點
{
if(T==NULL)
return ;
else{
if(T->data==h)p=T;
search(T->lchild,h,p);
search(T->rchild,h,p);
}
}
void main()
{
BiTree T;
BiTree p;
BiTree q;
char ch;
T=NULL;
int select;
while(1){
cout<<"\n\n";
cout<<"**********************************\n";
cout<<"1.創建二叉樹\n";
cout<<"2.前序遞歸遍歷序列\n";
cout<<" 中序遞歸遍歷序列\n";
cout<<" 後序遞歸遍歷序列\n";
cout<<"3.層次遍歷序列\n";
cout<<"4.二叉樹的深度\n";
cout<<"5.葉子結點數目\n";
cout<<"6.求結點總數目\n";
cout<<"7.返回樹根節點\n";
cout<<"8.返回節點p的左孩子\n";
cout<<" 返回節點p的右孩子\n";
cout<<" 返回節點p的 雙親\n";
cout<<"9.判斷是否為空(是返回1，否返回0)\n";
cout<<"10.刪除p節點的左子樹\n";
cout<<"11.刪除p節點的右子樹\n";
cout<<"12.銷毀樹!\n";
cout<<"0.退出\n";
cout<<"**********************************\n";
cout<<"\n請選擇要執行的操作(選擇數字0-12):";
cin>>select;
switch(select){
case 0:
cout<<"退出!";
return;
case 1:
cout<<"請按先序次序輸入各結點的值，以空格表示空節點:"<<endl;
CreateBiTree(T);
cout<<"成功！";
break;
case 2:
if(!T) cout<<"未建立樹，請先建樹！";
else{
cout<<"\n先序遍歷:\n";
PreOrderTraverse(T);
cout<<"\n中序遍歷:\n";
InOrderTraverse(T);
cout<<"\n後序遍歷:\n";
PostOrderTraverse(T);
}
break;
case 3:
if(!T) cout<<"未建立樹，請先建樹！";
else{
cout<<"\n層序遍歷:\n";
LevelOrderTraverse(T);
}
break;
case 4:
cout<<"二叉樹的深度為:\n";
cout<<BTDepth(T);
break;
case 5:
cout<<"\n葉子節點數:\n";
cout<<Leaf(T);
break;
case 6:
cout<<"總節點數:\n";
cout<<NodeCount(T);
break;
case 7:
cout<<"返回根節點："<<Root(T);
break;
case 8:
cout<<"\n請輸入要查詢的節點p值：";
cin>>ch;
search(T,ch,p);
cout<<ch<<"的左孩子是："<<LeftChild(p)<<endl;
cout<<ch<<"的右孩子是："<<RightChild(p)<<endl;
q=Parent(T,p);
cout<<ch<<"的父親是："<<Value(q)<<endl;
break;
case 9:
cout<<"判斷是否為空(是為1，否為0：)"<<Isempty(T);
break;
case 10:
cout<<"\n請輸入節點p值：";
cin>>ch;
search(T,ch,p);
cout<<Deletelchild( p);
cout<<"刪除了"<<ch<<"的左孩子";
break;
case 11:
cout<<"\n請輸入節點p值：";
cin>>ch;
search(T,ch,p);
cout<<Deleterchild( p);
cout<<"刪除了"<<ch<<"的右孩子";
break;
case 12:
cout<<"銷毀樹!"<<Destroy(T);
break;
default:
cout<<"請確認選擇項為數字1-12!\n";
}
}
}
5. 二叉鏈表存儲結構，實現二叉樹的遍歷
前幾天寫的，輸入二叉樹的廣義表形式，建立二叉樹的鏈式存儲。輸出的是中序。有注釋，看懂了應該其他的都能寫了吧。#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");
}
6. 以二叉鏈為存儲結構，寫一演算法求二叉樹的葉子結點個數
只要在遍歷右子樹之前加上判斷統計就可以了，下面給出一個Vc的程序例子，包括建樹、遍歷等等，下面先序建立一棵樹abcd,
輸入（輸入一個字元回車一次）：
a
b
#
#
c
#
d
#
#
輸出;中序遍歷結果和葉子節點數
實現程序如下：
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
typedef int Status;
//----二叉樹-----
typedef char TElemType; //元素類型為字元類型
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild, *rchild; //左右孩子指針
}BiTNode, *BiTree;
int NUM=0;
//------基本操作的函數
Status InitBitTree(BiTree &T) //構造一個空二叉樹T
{
T=new BiTNode;
if(!T){ cout<<"構造空樹時出錯"<升者<endl; return false;}
T->data =NULL;
T->lchild =NULL;
T->rchild =NULL;
return true;
}//InitBitTree
Status CreateBiTree(BiTree &T) //構造一個二叉鏈中肆表表示的二叉樹T
{
char ch;
cout<<"請輸入結點的值(字元型,若空則用'#'): ";
cin>>ch;
if(ch=='#') T=NULL;
else
{
/賣笑轎/if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(1);
T=new BiTNode;
if(!T) exit(1);
T->data =ch; //生成根結點
CreateBiTree(T->lchild ); //構建左子樹
CreateBiTree(T->rchild ); //構建右子樹
}
return 0;
} //CreateBiTree
Status Visit(TElemType e) //對結點的操作函數
{
cout<<e;
return ' ';
}
void InOrderTraverse(BiTree T,Status (*visit)(TElemType )) //中序遍歷T,對每個結點調用函數Visit一次且僅一次,一旦失敗,則操作失敗
{
if(T) //若二叉樹不為空
{
InOrderTraverse(T->lchild, visit); //遞歸調用訪問左子樹
visit(T->data ); //訪問根結點,
if(T->rchild==NULL)
NUM++;
InOrderTraverse(T->rchild ,visit); //遞歸調用訪問右子樹
}
}
int main()
{
BiTree T;
InitBitTree(T);
CreateBiTree(T);
cout<<"中序遍歷(列印); "<<endl;
InOrderTraverse(T,Visit);
printf("葉子節點數：%d\n",NUM);
cin.get();
//cin.get();
return 0;
}
7. 編寫演算法及程序，採用二叉鏈表作為存儲結構
#include "stdio.h"
#include "malloc.h"
#define ELEMTYPE char
typedef struct BiTNode
{ ELEMTYPE data;
struct BiTNode *lchild,*rchild;
} BiTNode;
BiTNode *bulid() /*建樹*/滑槐
{ BiTNode *q;
BiTNode *s[20];
int i,j;
char x;
printf("請按順序輸入二叉樹的結茄讓嫌點以輸入0和*號結束\n");
printf("請輸入你要顫手輸入的為第幾個結點i=\n");
scanf("%d",&i);
printf("請輸入你要輸入該結點的數為x=");
getchar();
scanf("%c",&x);
while(i!=0&&x!='*')
{q=(BiTNode*)malloc(sizeof(BiTNode));
q->data=x;
q->rchild=NULL;
q->lchild=NULL;
s[i]=q;
if(i!=1)
{ j=i/2;
if(i%2==0)
s[j]->lchild=q;
else
s[j]->rchild=q;
}
printf("請輸入你要輸入的為第幾個結點x=\n");
scanf("%d",&i);
printf("請輸入你要輸入該結點的數x=");
getchar();
scanf("%c",&x);
}
return s[1];
}
void preoder(BiTNode *bt) /*先序遍歷*/
{ if(bt!=NULL)
{
printf("%c\n",(bt->data));
preoder(bt->lchild);
preoder(bt->rchild);
}
}
void InOrder(BiTNode *bt) /*中序遍歷*/
{ if(bt!=NULL)
{ InOrder(bt->lchild);
printf("%c\n",bt->data);
InOrder(bt->rchild);
}
}
void postOrder(BiTNode *bt) /*後序遍歷*/
{ if(bt!=NULL)
{ postOrder(bt->lchild);
postOrder(bt->rchild);
printf("%c\n",bt->data);
}
}
main()
{ int a;
BiTNode *bt;
bt=bulid();
k1: printf("需要先序遍歷輸出請輸入1，中序遍歷請輸入2，後序遍歷請輸入3,結束輸入0:");
scanf("%d",&a);
switch(a)
{
case(1): preoder(bt); goto k1;
case(2): InOrder(bt); goto k1;
case(3): postOrder(bt); goto k1;
case(0): break;
}
}
8. 二叉樹的二叉鏈表存儲結構如何實現
大概這個樣子，這個是我以前寫的二叉搜索樹：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
int data,rep;
struct node *left,*right;
} node;
node* insert(node *tree,int x);
int search(node *tree,int x);
node* del(node *tree,int x);
int main()
{
char str[20],ch;
int x;
struct node *tree = NULL;
gets(str);
while (strcmp(str,"quit"))
{
if (!strcmp(str,"insert"))
{
scanf("%d",&x);
tree = insert(tree,x);
}
else if (!strcmp(str,"delete"))
{
scanf("%d",&x);
tree = del(tree,x);
}
else if (!strcmp(str,"search"))
{
scanf("%d",&x);
if (search(tree,x))
puts("Found!");
else
puts("Not Found!");
}
else
puts("There is an error!");
ch = getchar();
gets(str);
}
return 0;
}
node* insert(node *tree,int x)
{
if (tree == NULL)
{
tree = (struct node *)malloc(sizeof(struct node *));
tree->data = x;
tree->rep = 1;
tree->left = (struct node *)malloc(sizeof(struct node *));
tree->right = (struct node *)malloc(sizeof(struct node *));
tree->left = NULL;
tree->right = NULL;
}
else if (tree->data == x)
tree->rep++;
else if (x < tree->data)
tree->left = insert(tree->left,x);
else if (x > tree->data)
tree->right = insert(tree->right,x);
return tree;
}
int search(node *tree,int x)
{
if (tree == NULL)
return 0;
else if (tree->data == x)
return 1;
else if (x < tree->data)
return search(tree->left,x);
else if (x > tree->data)
return search(tree->right,x);
}
node* del(node *tree,int x)
{
struct node *p,*q;
if (tree == NULL) {}
else if (x < tree->data)
tree->left = del(tree->left,x);
else if (x > tree->data)
tree->right = del(tree->right,x);
else if (tree->data == x)
{
if (tree->rep > 1)
tree->rep--;
else
{
if (tree->left == NULL)
return tree->right;
else if (tree->right == NULL)
return tree->left;
else
{
p = tree->left;
q = tree;
while (p->right)
{
q = p;
p = p->right;
}
tree->data = p->data;
tree->rep = p->rep;
q->right = p->left;
}
}
}
return tree;
}
9. 以二叉鏈表為存儲結構,寫出求二叉樹高度和寬度的演算法
原題：
以二叉鏈表為存儲結構，分別寫出求二叉樹高度及寬度的演算法。所謂寬度是指在二叉樹的各檔基層上，具有結點數最多的那一層上的結點總數。
標准答案：
①求樹的高度
思想：對非空二叉樹，其深度等於左子樹的最大深度加1。
Int
Depth(BinTree
*T)
{
int
dep1,dep2;
if(T==Null)
return(0);
else
{
dep1=Depth(T->lchild);
dep2=Depth(T->rchild);
if(dep1>dep2)
return(dep1+1);
else
return(dep2+1);
}
②求樹的寬度
思想：按層遍歷二叉樹，採用一個隊列q，讓根結點入隊列，最後出隊列，若有左右子樹，則左右子樹根正碼結點入隊列，如此反復，直到隊列為空。
int
Width(BinTree
*T)
{
int
front=-1,rear=-1;/*
隊列初始化*／
int
flag=0,count=0,p;
/*
p用於指向樹中層的最右邊的結點，標志flag記錄層中結點數的最大值。*／if(T!=Null)
{
rear++;
q[rear]=T;
flag=1;
p=rear;
}
while(front<p)
{
front++;
T=q[front];
if(T->lchild!=Null)
{
rear++;
q[rear]=T->lchild;
count++;
}
if(T->rchild!=Null)
{
rear++;
q[rear]=T->rchild;
count++;
}
if(front==p)
/*
當前層已遍歷完畢*/
{
if(flag<行清謹count)
flag=count;
count=0;
p=rear;
/*
p指向下一層最右邊的結點*/
}
}
/*
endwhile*/
return(flag);
}