设二叉树的存储结构为二叉链表,编写有关二叉树的递归算法:
非递归,就是采用前序/中序/后序遍历所有节点,并统计。下面就给你提供//二叉树结构体 struct BTNode { int data; BTNode *rchild; BTNode *
#include
#include
#include
#define STACK_INT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
typedef char TElemType;
typedef int Status;
typedef char SElemType;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
typedef struct
{
BiTree *base;
BiTree *top;
int stacksize;
}SqStack;
typedef struct QNode
{
BiTree Queuedata;
struct QNode * next;
}QNode,* QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
Status InitStack(SqStack &S)
{
S.base = (BiTree *) malloc(sizeof(BiTree));
if(!S.base) exit(OVERFLOW);
S.top = S.base;
S.stacksize = STACK_INT_SIZE;
return OK;
}
Status GetTop(SqStack &S, BiTree &e)
{
if(S.top == S.base) return ERROR;
e = *(S.top-1);
return OK;
}
Status Push(SqStack &S, BiTree e)
{
if(S.top - S.base >= S.stacksize)
{
S.base = (BiTree *) realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(BiTree));
if(!S.base) return ERROR;
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top = e;
S.top++;
return OK;
}
Status Pop(SqStack &S,BiTree &e)
{
if(S.base == S.top) return ERROR;
S.top--;
e = *S.top;
return OK;
}
Status StackEmpty(SqStack S)
{
if(S.top == S.base) return TRUE;
else return FALSE;
}
Status PreOrderCreateBiTree(BiTree &T)
{
char ch;
scanf("%c",&ch);
if(ch == '0') T = NULL;
else
{
if(!(T = (BiTNode* ) malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T->data = ch;
PreOrderCreateBiTree(T->lchild);
PreOrderCreateBiTree(T->rchild);
}
return OK;
}
void PreOrder ( BiTree bt )
{
if ( bt )
{
printf("%c",bt->data);
PreOrder ( bt->lchild );
PreOrder ( bt->rchild );
}
}
void Inorder ( BiTree bt )
{
if ( bt )
{
Inorder ( bt->lchild );
printf("%c",bt->data);
Inorder ( bt->rchild );
}
}
void LastOrder ( BiTree bt )
{
if ( bt )
{
LastOrder( bt->lchild );
LastOrder( bt->rchild );
printf("%c",bt->data);
}
}
Status PreOrderTraverse(BiTree T)
{
SqStack s;
BiTree P=T;
InitStack(s);
while ( P!=NULL || !StackEmpty(s))
{
if (P!=NULL)
{
printf("%c",P->data);
Push(s,P);
P=P->lchild;
}
else
{
Pop(s,P);
P=P->rchild;
}
}
return OK;
}
Status InOrderTraverse(BiTree T)
{
SqStack S;
InitStack(S);
BiTree p;
p = T;
while(p || !StackEmpty(S))
{
if(p)
{
Push(S,p);
p = p->lchild;
}
else
{
Pop(S,p);
printf("%c",p->data);
p = p->rchild;
}
}
return OK;
}
Status LastOrderTraverse(BiTree T)
{
SqStack s,tag;
BiTree f,m,n,P=T;
m=(BiTNode*)malloc(sizeof(BiTNode));
m->data=1;
m->lchild=NULL;
m->rchild=NULL;
n=(BiTNode*)malloc(sizeof(BiTNode));
n->data=2;
n->lchild=NULL;
n->rchild=NULL;
InitStack(s);
InitStack(tag);
while (P ||!StackEmpty(s))
{
if (P)
{
Push(s,P);
Push(tag,m);
P=P->lchild;
}
else
{
Pop(s,P);
Pop(tag,f);
if (f==m)
{
Push(s,P);
Push( tag, n);
P=P->rchild;
}
else
{
printf("%c",P->data);
P=NULL;
}
}
}
return OK;
}
Status InitQueue(LinkQueue &Q)
{
Q.front=(QNode*)malloc(sizeof(QNode));
if (!Q.front)
exit(OVERFLOW);
Q.rear=Q.front;
Q.front->next=NULL;
return OK;
}
Status EnQueue(LinkQueue &Q,BiTree e)
{
QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
if (!s)
exit(OVERFLOW);
s->Queuedata=e;
s->next=NULL;
Q.rear->next=s;
Q.rear=s;
return OK;
}
int DelQueue(LinkQueue &Q, BiTree &e)
{
char data1;
QueuePtr s;
s=Q.front->next;
e=s->Queuedata;
data1=e->data;
Q.front->next=s->next;
if(Q.rear==s)
Q.rear=Q.front;
free(s);
return TRUE;
}
Status QueueEmpty(LinkQueue Q)
{
if (Q.front->next==NULL)
return OK;
else return ERROR;
}
Status HierarchyBiTree(BiTree bt)
{
LinkQueue Q;
InitQueue(Q);
BiTree p = bt;
if (bt == NULL) return ERROR;
EnQueue(Q,p);
while (!QueueEmpty(Q))
{
DelQueue(Q, p);
printf("%C",p->data);
if (p->lchild)
EnQueue(Q, p->lchild);
if (p->rchild)
EnQueue(Q, p->rchild);
}
return OK;
}
int sum=0;
int SumLefts(BiTree bt)
{
if (bt!=NULL)
{
if (bt->lchild==NULL && bt->rchild==NULL)
{
sum++;
}
sum=SumLefts(bt->lchild);
sum=SumLefts(bt->rchild);
}
return(sum);
}
void main()
{
printf("请输入先序建立二叉树所需要的数据(空树用0表示):
");
BiTree t;
PreOrderCreateBiTree(t);
printf("
");
printf("递归遍历输出为:
");
printf("先序输出: ");
PreOrder(t);
printf("
");
printf("中序输出: ");
Inorder(t);
printf("
");
printf("后序输出: ");
LastOrder(t);
printf("
");
printf("非递归遍历输出为:
");
printf("先序输出: ");
PreOrderTraverse(t);
printf("
");
printf("中序输出: ");
InOrderTraverse(t);
printf("
");
printf("后序输出: ");
LastOrderTraverse(t);
printf("
");
printf("按层次遍历输出为: ");
HierarchyBiTree(t);
printf("
");
printf("二叉树中叶子节点个数为:");
int leaves=SumLefts(t);
printf("%d",leaves);
printf("
");
}
提示:8功能可以用任意一种遍历方法,在程序中,将打印字符的部分换成自己的判断程序即可。
6功能用后续遍历,当遍历到任意一节点时,判断其孩子是不是叶子,是就删除。
7功能参考求广度的实现】
9功能参考6功能,用前序遍历也可以
10功能也参考求广度的方法
程序:
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
#define NUM_NODE 12
#define MOST_DEPTH 10
typedef struct BiTree{
int data;
BiTree *lchild;
BiTree *rchild;
}BiTree;
typedef struct Answear{
int Degree0;
int Degree1;
int Degree2;
int Depth;
} Answear;
BiTree* CreateTree(int n)
{
BiTree *t;
if (n <= 0 || n> NUM_NODE) return NULL;
if (!(t = (BiTree*)malloc(sizeof(BiTree))))
return NULL;
t->data = n;
printf("%d ", t->data);
t->lchild = CreateTree(2*n);
t->rchild = CreateTree(2*n+1);
return t;
}
void FreeTree(BiTree *t)
{
if (t)
{
if (t->lchild)
FreeTree(t->lchild);
if (t->rchild)
FreeTree(t->rchild);
printf("%d ", t->data);
free(t);
}
}
//中序遍历
void InOrder(BiTree *t)
{
BiTree **stack, **top, *p;
//创建堆栈
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
//初始化堆栈
top = stack;
p = t;
while (p || top>stack)//p不为NULL,堆栈不空
if (p)
{
*top++ = p;//p入堆栈
p = p->lchild;
}
else
{
p = *--top;//p出栈
if (p) printf("%d ", p->data);
p = p->rchild;
}
}
//前序遍历
void PreOrder(BiTree *t)
{
BiTree **stack, **top, *p;
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
top = stack;
p = t;
while (p || top>stack)
if (p)
{
*top++ = p;
if (p) printf("%d ", p->data);
p = p->lchild;
}
else
{
p = *--top;
p = p->rchild;
}
}
//后序遍历
void PostOrder(BiTree *t)
{
BiTree **stack, **top, *p, *p_old, *p_new;
int Flag;
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
top = stack;
Flag = 0;
*top++ = t;
while (top > stack)
{
p = *(top-1);
if (p->lchild && !Flag)
*top++ = p->lchild;
else
{
if (p->rchild)
{
*top++ = p->rchild;
Flag = 0;
}
else
{
p_old = *--top;
printf("%d ", p_old->data);
while (top > stack)
{
p_new = *(top-1);
if (p_old == p_new->lchild)
{
Flag = 1;
break;
}
else
{
p_new = *--top;
printf("%d ", p_new->data);
p_old = p_new;
Flag = 0;
}
}
}
}
}
}
//中序遍历求结点的深度和度为0,1,2的结点数,结果保存在pAns指的。。。
void InOrderDO(BiTree *t , Answear * pAns)
{
//遍历用的数据
BiTree **stack, **top, *p;
//求深度的数据
int curDeep, MostDeep;
//创建堆栈
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
//初始化堆栈
top = stack;
p = t;
//初始化数据
curDeep = MostDeep = 0;
pAns->Degree0 = pAns->Degree1 = pAns->Degree2 = 0;
//遍历循环
while (p || top>stack)//p不为NULL,堆栈不空
if (p)
{
*top++ = p;//p入堆栈
p = p->lchild;
curDeep++;
if (MostDeep < curDeep) MostDeep = curDeep; //保存最深度
}
else
{
p = *--top;//p出栈
curDeep--;
//if (p) printf("%d ", p->data); //Visit结点
//计算个结点的度
if (p->lchild && p->rchild) pAns->Degree2++;
else if (p->lchild || p->rchild) pAns->Degree1++;
else pAns->Degree0++;
p = p->rchild;
}
//得到深度
pAns->Depth = MostDeep;
return ;
}
//前序递归求广度
void Pre(BiTree *T, int* woed, int depth)
{
woed[depth]++;
if (T->lchild) Pre(T->lchild, woed, depth+1);
if (T->rchild) Pre(T->rchild, woed, depth+1);
}
//求广度的程序,返回值为广度
int GetTreeWidth(BiTree *root)
{
int i, WidthOfEachDepth[MOST_DEPTH]={0};
Pre(root, WidthOfEachDepth, 0);
for (i=1; i<MOST_DEPTH; i++)
if (WidthOfEachDepth[0] < WidthOfEachDepth[i])
WidthOfEachDepth[0] = WidthOfEachDepth[i];
return WidthOfEachDepth[0];
}
int main()
{
BiTree *root;
Answear ans;
printf("Create Tree\n");
root = CreateTree(1);
printf("\nInOrder\n");
InOrder(root);
printf("\nPreOrder\n");
PreOrder(root);
printf("\nPostOrder\n");
PostOrder(root);
InOrderDO(root, &ans);
printf("\nTheMostDepth is : %d\n", ans.Depth);
printf("TheMostWidth is : %d\n", GetTreeWidth(root));
printf("Each Degree (0,1,2)is: (%d, %d, %d)\n",
ans.Degree0, ans.Degree1, ans.Degree2);
printf("\nFree Tree\n");
FreeTree(root);
return 0;
}
设二叉树的存储结构为二叉链表,编写有关二叉树的递归算法:
(1)统计二叉树中度为1的结点个数。(2)统计二叉树中度为2的结点个数。(3)统计二叉树中度为0(叶结点)的结点个数。(4)统计二叉树的高度。(5)统计二叉树的宽度,即在二叉树的各层上,具有结点数最多的那一层上的结点总数。(6)从二叉树中删... 展开 972630969 | 浏览2043 次 |举报 我有更好的答案推荐...
二叉树的两种物理结构是什么
答:二叉树就物理结构来分可以分成:顺序存储结构和链式存储结构。(1)顺序存储结构:顺序存储结构,顾名思义就是二叉树的数据元素存放在一组连续的存储单元中。其主要有一下几个特点:①逻辑上相邻的两个元素在物理位置上也是相邻的;②操作删除和插入的时候,需要整体移动元素;③需要预先分配空间,不...
二叉树 两种存储结构的优缺点
链式存储相对顺序存储节省存储空间,插入删除节点时只需修改指针,但寻找指定节点时很不方便。不过普通的二叉树一般是用链式存储结构。
二叉链表存储结构是什么
二叉树的顺序存储结构由一组连续的存储单元依次从上到下,从左到右存储完全二叉树的结点元素。对于一般二叉树,应将其与完全二叉树对应,然后给每个结点从1到i编上号,依次存储在大小为i到1的数组中。
二叉树是非线性数据结构,所以
一般而言,完全二叉树(包括满二叉树)使用顺序存储,普通二叉树一般用二叉链表或者三叉链表存储。二叉树是n个有限元素的集合,该集合或者为空、或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成,是有序树。当集合为空时,称该二叉树为空二叉树。在二叉树中,一个元素...
二叉链表的结构是什么?
以二叉链表作为二叉树的储存结构,在具有n个结点的二叉链表中n(n>0),空链域的个数为n+1。二叉链表结构描述:typedef struct CSNode{ ElemType data;struct CSNode *firstchild , *netsibling;} CSNode,* CSTree;由于二叉树的存储结构比较简单,处理起来也比较方便,所以有时需要把复杂的树,...
计算机二级ms office高级应用基础知识
3.二叉树的存储结构 二叉树通常采用链式存储结构,存储节点由数据域和指针域(左指针域和右指针域)组成。二叉树的链式存储结构也称二叉链表,对满二叉树和完全二叉树可按层次进行顺序存储。 4.二叉树的遍历 二叉树的遍历是指不重复地访问二叉树中所有节点,主要指非空二叉树,对于空二叉树则结束返回。二叉树的遍历包括...
数据结构(树和二叉树)
* 二叉树的子树有左右之分,其次序不能任意颠倒。1.顺序存储结构:使用一组地址连续的存储单元来存储数据元素,将二叉树的结点依照自上而下,自左至右存储结点元素。2.链式存储结构:结点包含3个域:数据域,左右指针。遍历二叉树是指按某条搜索路径巡访树中每个结点,使的每个结点均被访问一次,而且...
二叉链表的存储结构
二叉树的存储结构 二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址
树- 二叉树 - 二叉树的存储结构(二)
DataType data;Struct node *lchild *rchild; \/\/左右孩子指针 }BinTNode; \/\/结点类型 typedef BinTNode *BinTree;\/\/BinTree为指向BinTNode类型结点的指针类型 二叉链表(二叉树的常用链式存储结构)在一棵二叉树中 所有类型为BinTNode的结点 再加上一个指向开始结点(即根结点)的BinTree型头指针(即...
骑畏重组:[答案] 给了一个程序给你参考,有前中后序遍历,实现了前5个功能.提示:8功能可以用任意一种遍历方法,在程序中,将打印字符的部分换成自己的判断程序即可.6功能用后续遍历,当遍历到任意一节点时,判断其孩子是不是叶子...
龙子湖区18999539790: 假设二叉树采用二叉链表作为存储结构,试编写一个算法:求任意一个指定结点所在的层次. - ?
骑畏重组: 非递归中序遍历 构造变量count记录当前层访问到的节点数,nextcount记录当前层的总个数; 每当访问过一层层数depth++; 此种方法同时可以求最大宽度,访问第几层的第几个节点,求带权路径长度WPL,是一种通用方法! int TreeDepth(...
龙子湖区18999539790: 假设二叉树用二叉链表存储结构.编写一个算法统计二叉树的结点个数. - ?
骑畏重组: int BiTreeCount(BiTree T) { int rNum,lNum; if(!T) return 0; else { lNum = BiTreeCount(T->lchild); rNum = BiTreeCount(T->rchild); return rNum + lNum + 1; }}
龙子湖区18999539790: 设一棵二叉树以二叉链表为存储结构 - ?
骑畏重组: void Leaf(BiTree T) {if(T=null){ return 0; } elseif(T->lchild==null&&T->rchild==null){ return 1; } else return leaves(T->lchild)+leaves(T->rchild); }
龙子湖区18999539790: 设一棵二叉树以二叉链表为存储结构,试写出求该二叉树中所有叶子结点数的算法. - ?
骑畏重组: //我做了一个程序,可以实现二叉树的左右子树的交换功能,#include<iostream.h>/* 二叉树类型的定义(二叉链表形式储存) */ typedef char datatype; // 树的结点数据类型为字符型,可以根据需要修改 typedef struct node *pointer; // 定义二叉...
龙子湖区18999539790: 假设以二叉链表作为二叉树的存储结构,试编写一个求树的高度的算法 - ?
骑畏重组: int length(BiTree T) { int h1,h2; if(T==NULL) return 0; if(T->lchild==NULL && T->rchild==NULL) return 1; h1=length(T->lchild); h2=length(T->rchild); return h1>=h2?h1:h2; } BiTree Find(BiTree T,ElemType x) //该函数2113返回5261给4102定值的1653结...
龙子湖区18999539790: 若用二叉链表作为二叉树的存储表示,试编写算法交换二叉树中各结点的左右子数. - ?
骑畏重组: 递归:void exchange(BTree *rt){ BTree *temp = NULL; if(rt->lchild == NULL && rt->rchild == NULL) return; else{ temp = rt->lchild; rt->lchild = rt->rchild; rt->rchild = temp; } if(rt->lchild) exchange(rt->lchild); if(rt->rchild) exchange(rt->rchild); } 非递归:...
龙子湖区18999539790: (1)以二叉链表作为二叉树的存储结构,写出二叉树的存储结构定义(C或C++表示). (2)编程实现以二叉链 - ?
骑畏重组: 思想上,可以构造“节点”这种结构体,该结构体包含自身的值,还有左孩子指针,右孩子指针.朝这个方向自己构思,希望能帮到你!欢迎追问
龙子湖区18999539790: 用C语言编写:建立一棵以二叉链表结构存储的二叉树,并对其进行遍历.求该二叉树中的结点个数等操作. - ?
骑畏重组: 存储结构 typedef struct { int weight; int parent, lchild, rchild; } HTNode ,*HuffmanTree; // 动态分配数组存储huffman树 算法设计 void createHuffmantree(){ ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode);// 动态分配数组存储huffman树,0号单元未用// m:huffman 树中的结点数(m=2*n-1)
龙子湖区18999539790: 用C++程序语言:以二叉链表作存储结构,编写一个算法将二叉树左、右子树进行交换的程序 - ?
骑畏重组: template t search(bstnode* tree, const t& elemt) { stack*> travstack; bstnode *p = root; //遍历指针 bstnode *q = root; //层数看守 int num = 1; if(p != null) travstack.push(p); while(!travstack.empty()) { p = travstack.pop(); if(p->data != elemt) if(p == q) ...