编写算法:已知二叉排序树按二叉链表形式存储，树中结点各不相同，欲得到一个由小到大的结点值递增序列

已知二叉树按照二叉链表的方式存储.编写算法.计算二叉树度为0.度为1.度为2的结点~

#include //头文件
#include
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}
BiTNode,*BiTree;//定义结点类型
BiTree CreateBiTree()//创建树
{
char p;BiTree T;
scanf("%c",&p);
if(p==' ')
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));//为结点开辟空间
T->data=p;
T->lchild=CreateBiTree();
T->rchild=CreateBiTree();
}
return (T);
}

int Nochild(BiTree T)//叶子结点
{
if(T==NULL)
return(0);
if(T->lchild==NULL&&T->rchild==NULL)
return(1);
return(Nochild(T->lchild)+Nochild(T->rchild));
}
int Onechild(BiTree T)//度为1的
{
int n=0;
if(T==NULL)
return(0);
if((T->lchild==NULL&&T->rchild!=NULL)||(T->lchild!=NULL&&T->rchild==NULL))
n=1;
return(Onechild(T->lchild)+Onechild(T->rchild)+n);
}
int Twochild(BiTree T)//度为2的
{
int n=0;
if(T==NULL)
return(0);
if(T->lchild!=NULL&&T->rchild!=NULL)
n=1;
return( Twochild(T->lchild)+Twochild(T->rchild)+n);
}

void main()//主函数
{
BiTree Ta;
printf("请创建树：
");
Ta=CreateBiTree();
printf("叶子数为：%d，度为1的数为：%d，度为2的为：%d",Nochild(Ta),Onechild(Ta),Twochild(Ta));
}

及层次顺序遍历二叉树的算法。
#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("
按先序遍历次序生成的二叉树");
printf("
前序遍历二叉树");
preorder(root);
printf("
中序遍历二叉树");
inorder(root);
printf("
后序遍历二叉树");
postorder(root);
printf("
层次顺序遍历二叉树");
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("建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开

");
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("
按先序遍历次序生成的二叉树");
preorder(B);
printf("
二叉树深度:%d
",BTreeDepth(B));
printf("总结点个数:%d
",nodecount(B));
printf("叶子结点个数:%d
",leafcount(B));
printf("非叶子结点个数:%d
",notleafcount(B));
printf("具有双孩子结点个数:%d
",twosoncount(B));
printf("具有单孩子结点个数:%d
",onesoncount(B));
}
如果还没解决你的问题，可以加我百度HI账号。

首先看下二叉排序树的定义：

二叉排序树（Binary Sort Tree）又称二叉查找树，亦称二叉搜索树。 它或者是一棵空树；或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树；

由定义可知，采用中序遍历的输出序列，就是“一个由小到大的结点值递增序列”

代码参考如下：

#include <stdio.h>
#include <malloc.h>
typedef int KeyType;
typedef struct node             //记录类型
{
 KeyType key;                //关键字项
 struct node *lchild,*rchild; //左右孩子指针
} BSTNode;
int InsertBST(BSTNode *&p,KeyType k) 
{
    if (p==NULL)      //原树为空, 新插入的记录为根结点
 {
  p=(BSTNode *)malloc(sizeof(BSTNode));
  p->key=k;
  p->lchild=p->rchild=NULL;
  return 1;
 }
 else if (k==p->key)     //树中存在相同关键字的结点,返回0
  return 0;
 else if (k<p->key) 
  return InsertBST(p->lchild,k); //插入到*p的左子树中
 else  
  return InsertBST(p->rchild,k);  //插入到*p的右子树中
}
BSTNode *CreateBST(KeyType A[],int n) //返回BST树根结点指针
{
 BSTNode *bt=NULL;            //初始时bt为空树
 int i=0;
 while (i<n) 
 {
  InsertBST(bt,A[i]);     //将关键字A[i]插入二叉排序树T中
  i++;
    }
    return bt;                  //返回建立的二叉排序树的根指针
}
void mid_order(BSTNode *T)//中序遍历二叉树
{
    if(T)
    {
    mid_order(T->lchild);
    printf(" %d ",T->key);
    mid_order(T->rchild);
    }
}
void main()
{
 BSTNode *bt,*p,*f;
 int n=9;
 KeyType a[]={1,12,5,8,3,10,7,13,9};
 bt=CreateBST(a,n);
 printf("BST:");mid_order(bt);printf("
");
         
}

中序遍历一遍

---

丰泽区19658488085： 编写算法:已知二叉排序树按二叉链表形式存储,树中结点各不相同,欲得到一个由小到大的结点值递增序列 - ？
虞欣参七： 首先看下二叉排序树的定义:二叉排序树(Binary Sort Tree)又称二叉查找树,亦称二叉搜索树. 它或者是一棵空树;或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空...

丰泽区19658488085： 已知二叉树按照二叉链表的方式存储.编写算法.计算二叉树度为0.度为1.度为2的结点 - ？
虞欣参七： #include //头文件 #include typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; } BiTNode,*BiTree;//定义结点类型 BiTree CreateBiTree()//创建树 { char p;BiTree T; scanf(＂%c＂,&p); if(p==' ') T=NULL; else { T=(BiTNode *)malloc(sizeof...

丰泽区19658488085： 数据结构算法设计题1.已知一颗二叉树采用二叉链表存放,写一算法,要求统计出二叉树中叶子结点个数并输出(输出无顺序要求)1.已知一个带头结点的... - ？
虞欣参七：[答案] 某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素,则采用( )存储方式最节省运算时间.(A)...已知带头结点的单链表L中的结点是按整数值递增排列的,试写一算法,将值为x 的结点插入到表L中,使得L仍然有序

丰泽区19658488085： 已知一棵二叉树以二叉链表为存储结构,编写如下程序:对于树中每一个元素值为x的结点,删去以它为根的子 - ？
虞欣参七： 先前序遍历整个二叉树,找到符合要求的结点,然后后序遍历该结点的整个子树,逐一释放结点.//假设二叉树结构体如下 struct binTree { int data; binTree *lchild; binTree *rchild; }*BiTree;//函数如下 BiTree find(BiTree node, int x) { if(node) { if(...

丰泽区19658488085： 假设二叉树用二叉链表存储结构.编写一个算法统计二叉树的结点个数. - ？
虞欣参七： int BiTreeCount(BiTree T) { int rNum,lNum; if(!T) return 0; else { lNum = BiTreeCount(T->lchild); rNum = BiTreeCount(T->rchild); return rNum + lNum + 1; }}

丰泽区19658488085： 二叉树按照二叉链表的方式存储,编写算法,将该二叉树的左右子树进行交换! - ？
虞欣参七： 自顶向下顺序交换左右子树

丰泽区19658488085： 已知二叉树采用二叉链表存储结构,编写算法交换二叉树的所有左子树与右子树的位置 - ？
虞欣参七： f(Node* root,Node* child){if (root==child) {output the stack;return;}if (root->left) {stack.push(root->left);f(root->left,child);stack.pop();}if (root->right) {stack.push(root->right);f(root->right,child);stack.pop();}} void main(){stack.push(root);...

丰泽区19658488085： 二叉树采用二叉链表存储,编写计算整个二叉树深度的算法 - ？
虞欣参七： int depth(bitree root)//root为根指针 { if(!root)return 0; else { int m=depth(root->lchild); int n=depth(root->rchild); return (m>n?m:n)+1; } }

丰泽区19658488085： 设一棵二叉树T采用二叉链表表示,编写一个算法,求T的所有叶结点的值及其所在层次 - ？
虞欣参七： 调用如下方法即可,例如二叉树的根结点为T,此时调用形式如下:TraversalTree(&T,0); 具体实现如下:void TraversalTree(TreeNode *root, int level) { if (root == NULL) return; if (root->left == NULL && root->right == NULL) //如果是叶子结点 { ...