编写算法:已知二叉排序树按二叉链表形式存储,树中结点各不相同,欲得到一个由小到大的结点值递增序列
#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("
");
}
中序遍历一遍
数据结构与算法,二叉排序树问题,这题怎么做啊,请教大神!!!
2)换了7次,a 右子树指向f节点;g 左指空,父节点指f;f 父指a,左指b,右指g;b 父指f。不知道e置空算不算
利用二叉排序树,统计随机从键盘上输入的字符个数,然后输出字符和对应...
1、统计字符串中字符出现的次数 编写一个程序,由键盘输入一个字符串,统计该字符串中出现的字符及其次数。然后输出结果。要求用一个二叉树来保存处理结果,字符串中每个不同的字符用树的结点表示,结点应该包含四个域:该字符、该字符出现的次数、左子树指针、右子树指针;其中左子树的字符的ASCII码均...
查找- 树上的查找 - 二叉排序树(二)
由输入实例(5,3,7,2,4,8),根据生成二叉排序树算法生成二叉排序树的过程 注意:输入序列决定了二叉排序树的形态。二叉排序树的中序序列是一个有序序列。所以对于一个任意的关键字序列构造一棵二叉排序树,其实质是对此关键字序列进行排序,使其变为有序序列。"排序树"的名称也由此而来。通常将...
二叉排序树查找的二叉排序树查找的程序实现:
② 以*p的中序前趋结点*s代替*p(即把*s的数据复制到*p中),将*s的左子树链到*s的双亲结点*q的左(或右)链上。6. 删除算法演示 :7. 二叉排序树的查找:在二叉排序树中进行查找的过程和二分查找类似,也是一个逐步缩小查找范围的过程。若查找成功,则是走了一条从根结点到待查结点的路径;...
二叉树先知道后序和中序,求先序
后序DABEC 中序DEBAC;由后序最后一个字母知:整个树的开始结点为C;由中序C的位置知:C前面的为结点C的左子树;C后面的为结点C的右子树;所以经过第一次推理,C为根结点,DEBA为其左子树;然后去掉C,考虑下面的左子树。后序DABE 中序DEBA由后序最后一个字母知:整个左子树的开始结点为E;由中...
已知一组权值(10 2 12 7 9 11 13)构建一颗二叉排序树
下载百度知道APP,抢鲜体验 使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。 扫描二维码下载× 个人、企业类侵权投诉 违法有害信息,请在下方选择后提交 类别 色情低俗 涉嫌违法犯罪 时政信息不实 垃圾广告 低质灌水 我们会通过消息、邮箱等方式尽快将举报结果通知您。 说明 0\/200 提交 取消...
查找- 树上的查找 - 二叉排序树(三)
上述三种情况都能统一到情况( ) 算法中只需针对情况( )处理即可 注意边界条件 若parent为空 被删结点*p是根 故删去*p后 应将child置为根 算法 void DelBSTNode(BSTree *Tptr KeyType key){\/\/在二叉排序树*Tptr中删去关键字为key的结点 BSTNode *parent=NUll *p=*Tptr *q *child;while(p)...
二叉排序树的删除一个节点的为码算法
bool Delete_Node(Tree& T,char key);删除二叉树中值为key的节点如果树中不含有对应节点返回fals否则返回true;算法如下 { 首先在循环中查找到值为key的节点,如果找不到,返回false,找到则跳出循环 如果找到的是根节点,则直接把根的左子树放到右子树最左边 根节点的值为改为右子树即可 如果不是根...
二叉排序树的插入算法
首先执行查找算法,找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意:新插入的结点总是叶子结点。 \/\/在二叉排序树中插入查找关键字keyvoidInsertBST(t,key){ if(t==NULL) { t=newBiTree; t...
已知一组元素(46,25,78,62,12,37,70,29),画出按元素排列顺序输入生成的...
先给出答案:根据二叉排列树的定义:(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;(3)左、右子树也分别为二叉排序树;简单的说,就是在这棵树中,左子树的值总是小于根结点,右子树的值总是大于根节点。
虞欣参七: 首先看下二叉排序树的定义:二叉排序树(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) //如果是叶子结点 { ...