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;
}
构成递归需具备的条件：
一、子问题须与原始问题为同样的事，且更为简单；
二、不能无限制地调用本身，须有个出口，化简为非递归状况处理。
在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。
例如，下列为某人祖先的递归定义：
某人的双亲是他的祖先（基本情况）。某人祖先的双亲同样是某人的祖先（递归步骤）。斐波纳契数列（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账号。