1. 編寫演算法，判斷一個二叉樹鏈存儲的二叉樹是否為完全二叉...
nclude stdio.h>
#include stdlib.h>
#define Max 100
typedef struct Node
{
char data;
struct Node * LChild,*RChild;
}BiTNode,*BiTree;
void CreateBiTree(BiTree * bt)
{
char ch;
ch=getchar();
if(ch==10)ch=getchar();//如果為 回車換行 讀取下一個字元
if(ch=='.') *bt=NULL; //如果為 . 代表此節點為空
else
{
* bt=(BiTree)malloc(sizeof(BiTNode));
(* bt)->data=ch; //賦值
CreateBiTree(&((* bt)->LChild));
CreateBiTree(&((* bt)->RChild));
}
}
bool fullBiTree(BiTree b)
{
if(b->LChild==NULL && b->RChild==NULL)return true;// 如果左右子樹為空，返回真
if(b->LChild==NULL || b->RChild==NULL)return false;// 如果左右子樹只有一個為空，返回假
return fullBiTree(b->LChild) && fullBiTree(b->RChild);// 通過遞歸，返回
}
void main()
{
printf("請依次輸入字元\n");
BiTree b;
CreateBiTree(&b); //創建二叉樹
bool cm=fullBiTree(b);
if(cm)printf("´此二叉樹為完全二叉樹\n");
else printf("´此二叉樹不是完全二叉樹\n");
}
7.問候你我的朋友：送你陽光，替你把痛苦蒸發，送你細雨，替你把齷齪沖刷。送你流星，替你帶走噩夢，你開心了吧！
2. 這是一道數據結構的題：試寫一個判別給定二叉樹是否為二叉排序樹的演算法，設此二叉樹以二叉鏈表作存儲結構
用遞歸：
a=當前節點是否為排序樹，是為1，不是為0
f(x)=1 當x為葉節點
f(x)= a&&f(x->lchid)&&f(x-rchild) 當x非葉節點
----------------------------------------------------------------------
int IsAVTree(BiTree t)
{
int a=1;
if(t->Child==NULL&&t->Rchild==NULL) return 1; //葉子節點判斷
if((t->Lchild->data>t->data)||(t->Rchild->datadata))
{
a=0;
a=a&&(isAVTree(t->Lchild))&&(IsAVTree(t->Rchild));
}
return a;
}
(2)設二叉樹按二叉鏈表存放寫演算法判別擴展閱讀：
構成遞歸需具備的條件：
一、子問題須與原始問題為同樣的事，且更為簡單；
二、不能無限制地調用本身，須有個出口，化簡為非遞歸狀況處理。
在數學和計算機科學中，遞歸指由一種（或多種）簡單的基本情況定義的一類對象或方法，並規定其他所有情況都能被還原為其基本情況。
例如，下列為某人祖先的遞歸定義：
某人的雙親是他的祖先（基本情況）。某人祖先的雙親同樣是某人的祖先（遞歸步驟）。斐波納契數列（Fibonacci Sequence），又稱黃金分割數列，指的是這樣一個數列：1、1、2、3、5、8。
3. 急求:設二叉樹以二叉鏈表為存儲結,試給出判斷一棵二叉樹是否為滿二叉樹的演算法
一個n層的滿二叉樹結點總數為2的n次冪-1，利用遞歸遍歷，一個計數器就可以了！以下為該子程序：int i=0;/*計數器I為全局變數*/ int sumtree(Bitree T){if(T) {i++; Preordertraverse(T->lchild); } else return; Preordertraverse(T->rchild);}最後I的值就是結點總數。
4. 設二叉樹以二叉鏈表存儲，試設計演算法，實現二叉樹的層序遍歷。
按層次遍歷演算法如下：
#include <iostream>
using namespace std;
typedef struct treenode { //樹結點結構
int data;
struct treenode *left;
struct treenode *right;
}TreeNode;
typedef struct stack{ //棧結點結構
TreeNode *node;
struct stack *next;
}STACK;
void Traversal(TreeNode *root)
{
STACK *head = NULL;
STACK *tail = NULL;
if (root != NULL) //根結點入棧
{
head = new STACK();
head->next = NULL;
head->node = root;
tail = head;
}
while(head != NULL)
{
STACK *temp;
if (head->node->left != NULL) //棧頂結點的左結點入棧
{
temp = new STACK();
temp->next = NULL;
temp->node = head->node->left;
tail->next = temp;
tail = temp;
}
if (head->node->right != NULL) //棧頂結點的右結點入棧
{
temp = new STACK();
temp->next = NULL;
temp->node = head->node->right;
tail->next = temp;
tail = temp;
}
cout<<head->node->data<<endl; //結點出棧
temp = head;
head = head->next;
delete(head);
}
}
5. 編寫一演算法，判別給定的二叉樹是否是完全二叉樹。二叉樹用二叉鏈表儲存結構儲存
#include <stdio.h>#define MaxNum 10000BinTree buildTree(elementype BT[],int i , int n){ BinTree r;if(i>n)return(NULL);r=(BinTree)malloc(sizeof(BinNode));r->data=BT[i];r->Lchild=buildTree(BT,2*i,n);r->Rchild=buildTree(BT,2*i+1,n);return(r);}Int checkTree(BinTree t){ int maxn0=0;n=num(t,1,&maxn0);if(n==maxn0)return(1); else return(0); }int num(BinTree t,int i,int *m){ if(t==NULL) return(0); if(*m<i)*m=i;return(1+num(t->Lchild,2*i,m)+num(t->Rchild,2*i+1,m));}main( ){ int data,int t,int i,int *m; printf("input data:\n") scanf("%d,&data");if(t==NULL)printf("F\n")if(*m<i)*m=i;printf("T\n")}
6. 假設二叉樹用二叉鏈表表示；設計一演算法，判別該二叉樹是否為完全二叉樹。(求完整源代碼）如題 謝謝了
一定要完整源碼？如果沒有人給的話，建議你還是看一下我說的：就是一個二叉樹的遍歷。1.只要在遍歷的時候，發現當前深度大於log2(n)+1，就可以判斷不是。2.有一個變數，cnt初始化為n個節點的完全二叉樹最後一層節點的數目，計算方法：n - (2^k - 1)然後，只要不是後序遍歷，每次遍歷到深度為floor(log2(n))時，如果cnt不為0，而且兒子是空節點，則判斷不是，否則cnt--。遍歷完後，如果一直沒有判斷成不是，則一定是。
7. 假設二叉樹採用二叉鏈表存儲結構，請編寫一個演算法，求一棵二叉樹中的最大結點值。
Status PostOrderTraverse(BiTree T)
{
//後序遍歷二叉鏈表樹的非遞歸演算法
//找到結點最大值
SqStack S;
InitStack(S);
BiTree p = T;
BiTree pre = NULL;//pre指向上次訪問的結點
TElemType Maxdata = T->data;//用來儲存最大值
while (p || !StackEmpty(S))
{
while (p)
{
Push(S, p);
p = p->lchild;
}
GetTop(S, p);
if (p->rchild == NULL || pre == p->rchild)
{
if (p->data > Maxdata)
Maxdata = p->data;//更新最大值
Pop(S, pre);
p = NULL;//避免下次重新進入p的左子樹
}
else
p = p->rchild;//走向p的右子樹
}
return OK;
}
8. 編寫演算法,實現判別二叉鏈表存儲的二叉樹是否為二叉排序樹
int IsSearchTree(const BTNode *t){ if(!t) //空二叉樹情況 return 1; else if(!(t-
9. 編寫演算法，判斷一個二叉樹鏈存儲的二叉樹是否為完全二叉樹
#include <stdio.h>
#include <stdlib.h>
#define Max 100
typedef struct Node
{
char data;
struct Node * LChild,*RChild;
}BiTNode,*BiTree;
void CreateBiTree(BiTree * bt)
{
char ch;
ch=getchar();
if(ch==10)ch=getchar();//如果為 回車換行 讀取下一個字元
if(ch=='.') *bt=NULL; //如果為 . 代表此節點為空
else
{
* bt=(BiTree)malloc(sizeof(BiTNode));
(* bt)->data=ch; //賦值
CreateBiTree(&((* bt)->LChild));
CreateBiTree(&((* bt)->RChild));
}
}
bool fullBiTree(BiTree b)
{
if(b->LChild==NULL && b->RChild==NULL)return true;// 如果左右子樹為空，返回真
if(b->LChild==NULL || b->RChild==NULL)return false;// 如果左右子樹只有一個為空，返回假
return fullBiTree(b->LChild) && fullBiTree(b->RChild);// 通過遞歸，返回
}
void main()
{
printf("請依次輸入字元\n");
BiTree b;
CreateBiTree(&b); //創建二叉樹
bool cm=fullBiTree(b);
if(cm)printf("´此二叉樹為完全二叉樹\n");
else printf("´此二叉樹不是完全二叉樹\n");
}
10. 設二叉樹的存儲結構為二叉鏈表，試寫出演算法（C函數）：將所有結點的左右子樹互換
1、以二叉鏈表作存儲結構，試編寫前序、中序、後序及層次順序遍歷二叉樹的演算法。
#define M 10
typedef int DataType;/*元素的數據類型*/
typedef struct node
{ DataType data;
struct node *lchild,*rchild;
}BitTNode,*BiTree;
int front=0,rear=0;
BitTNode *que[10];
BitTNode *creat()
{BitTNode *t;
DataType x;
scanf("%d",&x);
if(x==0) t=NULL;
else{ t=(BitTNode *)malloc(sizeof(BitTNode));
t->data=x;
t->lchild=creat();
t->rchild=creat();
}
return(t);
}/*creat*/
/* 前序遍歷二叉樹t */
void preorder(BiTree t)
{ if(t!=NULL)
{ printf("%4d",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
/* 中序遍歷二叉樹t */
void inorder(BiTree t)
{ if(t!=NULL)
{ inorder(t->lchild);
printf("%4d",t->data);
inorder(t->rchild);
}
}
/* 後序遍歷二叉樹t */
void postorder(BiTree t)
{ if(t!=NULL)
{ postorder(t->lchild);
postorder(t->rchild);
printf("%4d",t->data);
}
}
void enqueue(BitTNode *t)
{if (front!=(rear+1)%M)
{ rear=(rear+1)%M;
que[rear]=t;
}
}/*enqueue*/
BitTNode * delqueue()
{ if(front==rear)return NULL;
{ front=(front+1)%M;
return (que[front]);
}
}/*delqueue*/
/* 按層次遍歷二叉樹t */
void levorder(BiTree t)
{ BitTNode *p;
if(t!=NULL)
{ enqueue(t);
while (front!=rear)
{ p=delqueue();
printf("%4d",p->data);
if(p->lchild!=NULL) enqueue(p->lchild);
if(p->rchild!=NULL) enqueue(p->rchild);
}
}
}/* levorder */
main()
{BitTNode *root;
root=creat();
printf("\n按先序遍歷次序生成的二叉樹");
printf("\n前序遍歷二叉樹");
preorder(root);
printf("\n中序遍歷二叉樹");
inorder(root);
printf("\n後序遍歷二叉樹");
postorder(root);
printf("\n層次順序遍歷二叉樹");
levorder(root);
}
2、以二叉鏈表作存儲結構，試編寫計算二叉樹深度、所有結點總數、葉子結點數、雙孩子結點個數、單孩子結點個數的演算法
#include <stdio.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *left,*right;
} BTree;
BTree * createbt( )
{ BTree *q;
struct node1 *s[30];
int j,i,x;
printf("建立二叉樹，輸入結點對應的編號和值,編號和值之間用逗號隔開\n\n");
printf("i,x = ");
scanf("%d,%c",&i,&x);
while(i != 0 && x != '$')
{ q = (BTree*)malloc(sizeof(BTree)); /*建立一個新結點q*/
q->data = x; q->left = NULL; q->right = NULL;
s[i] = q; /*q新結點地址存入s指針數組中*/
if(i != 1) /*i = 1，對應的結點是根結點*/
{ j = i / 2; /*求雙親結點的編號j*/
if(i % 2 == 0)
s[j]->left = q; /*q結點編號為偶數則掛在雙親結點j的左邊*/
else
s[j]->right = q; /*q結點編號為奇數則掛在雙親結點j的右邊*/
}
printf("i,x = ");
scanf("%d,%c",&i,&x);
}
return s[1]; /*返回根結點地址*/
}
void preorder(BTree *BT)
/* 前序遍歷二叉樹t */
{ if(BT!=NULL)
{ printf("%4c", BT ->data);
preorder(BT ->left);
preorder(BT ->right);
}
}
int BTreeDepth(BTree *BT)
{
int leftdep,rightdep;
if (BT==NULL)
return(0);
else
{
leftdep=BTreeDepth(BT->left);
rightdep=BTreeDepth(BT->right);
if (leftdep>rightdep)
return(leftdep+1);
else
return(rightdep+1);
}
}
int nodecount(BTree *BT)
{
if (BT==NULL)
return(0);
else
return(nodecount(BT->left)+nodecount(BT->right)+1);
}
int leafcount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL && BT->right==NULL)
return(1);
else
return(leafcount(BT->left)+leafcount(BT->right));
}
int notleafcount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL && BT->right==NULL)
return(0);
else
return(notleafcount(BT->left)+notleafcount(BT->right)+1);
}
int onesoncount(BTree *BT)
{
if (BT==NULL)
return(0);
else if ((BT->left==NULL && BT->right!=NULL) ||
(BT->left!=NULL && BT->right==NULL))
return(onesoncount(BT->left)+onesoncount(BT->right)+1);
else
return(onesoncount(BT->left)+onesoncount(BT->right));
}
int twosoncount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT->left==NULL || BT->right==NULL)
return(twosoncount(BT->left)+twosoncount(BT->right));
else if (BT->left!=NULL && BT->right!=NULL)
return(twosoncount(BT->left)+twosoncount(BT->right)+1);
}
main()
{
BTree *B;
B=creatree();
printf("\n按先序遍歷次序生成的二叉樹");
preorder(B);
printf("\n二叉樹深度:%d\n",BTreeDepth(B));
printf("總結點個數:%d\n",nodecount(B));
printf("葉子結點個數:%d\n",leafcount(B));
printf("非葉子結點個數:%d\n",notleafcount(B));
printf("具有雙孩子結點個數:%d\n",twosoncount(B));
printf("具有單孩子結點個數:%d\n",onesoncount(B));
}
如果還沒解決你的問題，可以加我網路HI賬號。