编程实现以上二叉树中序遍历操作,输出遍历序列,求写代码~~
#include
#include
#define MAX 50
using namespace std;
typedef char Elem_Type;
typedef struct BiTree
{
Elem_Type data;//数据
struct BiTree *Lchild;//左孩子
struct BiTree *Rchild;//右孩子
}BiTree;
//要查找的元素 查找的地方 数组的长度
int Search_Num(Elem_Type num, Elem_Type *array, int len)
{
for (int i = 0; i<len; i++)
if (array[i] == num)
return i;
//return -1;//没有找到
} //前序结果数组 中序结果数组 数组长度
//根据中后序生成二树
BiTree *Resume_BiTree(Elem_Type *post, Elem_Type *center, int len)
{
if (len <= 0)
return NULL;
BiTree *temp = new BiTree;
temp->data = post[len - 1];//后序最后一个元素即为根元素
int index = Search_Num(temp->data, center, len);
//遍历左孩子 (后序结果中,从第0个元素开始到第index-1个元素都是左子树)
temp->Lchild = Resume_BiTree(post, center, index);
//遍历右孩子 (后序结果中,从第index个元素开始到第Len-2个元素都是右子树(从0计数))
temp->Rchild = Resume_BiTree(post + index, center + index + 1, len - index - 1);
return temp;
}
void PreOrderTraverse(BiTree *root)//前序遍历输出
{
if (root != NULL)
{
cout data;
PreOrderTraverse(root->Lchild);
PreOrderTraverse(root->Rchild);
}
}
int main(void)
{
Elem_Type *postorder = new Elem_Type[MAX];//后序数组
Elem_Type *inorder = new Elem_Type[MAX];//中序前序数组
cin >> postorder; //先输入后序
cin >> inorder; //再输入前序
BiTree * root = Resume_BiTree(postorder, inorder, strlen(inorder));//由于本例结构元素为char,所以可以用strlen来获元素个数,其他情况可机变
PreOrderTraverse(root);
cout << endl;
delete[] postorder;//释放内存
delete[] inorder;
return 0;
}
#include
#include
struct BiTNode *stack[100];
struct BiTNode//定义结构体
{
char data;
struct BiTNode *lchild,*rchild;
};
void later(struct BiTNode *&p) //前序创建树
{
char ch;
scanf("%c",&ch);
if(ch==' ')
p=NULL;
else
{
p=(struct BiTNode *)malloc(sizeof(struct BiTNode));
p->data=ch;
later(p->lchild);
later(p->rchild);
}
}
void print(struct BiTNode *p) //前序遍历(输出二叉树)
{
int i=-1;
while(1)
{
while(p!=NULL)
{
stack[++i]=p->rchild;/*printf("ok?
");*/
printf("%c",p->data);
p=p->lchild;
}
if(i!=-1)
{
p=stack[i];
i--;
}
else
return;
}
}
void main()//主函数
{
struct BiTNode *p,*t;
later(p);
print(p);
}
#include<stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define OK 1
#define ERROR 0
#define OVERFLOW 0
typedef char TElemType;
typedef int Status;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef enum {Link,Thread} PointerTag;
typedef struct BiThrNode
{
TElemType data;
struct BiThrNode *lchild,*rchild;
PointerTag LTag,RTag;
}BiThrNode;
typedef BiThrNode *BiThrTree;
BiTree CreateBiTree(BiTree T) //先序遍历构造二叉树
{
char ch;
scanf("%c",&ch);
if(ch=='#') //#代表空指针
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode)); //申请结点
if(!T)
exit(OVERFLOW);
T->data=ch; //生成根结点
T->lchild=CreateBiTree(T->lchild); //构造左子树
T->rchild=CreateBiTree(T->rchild); //构造右子树
}
return T;
}
Status InOrderTraverse(BiTree T,Status(*visit)(TElemType))
{//中序遍历二叉树
if(T)
{
if(InOrderTraverse(T->lchild,visit))
if(visit(T->data))
if(InOrderTraverse(T->rchild,visit))
return OK;
return ERROR;
}
else
return OK;
}
Status PrintElement(TElemType e)
{
printf("%-2c",e);
return OK;
}
void main()
{
BiTree T=NULL;
printf("请输入构造二叉树的字符序列:");
T=CreateBiTree(T);
if(T)
printf("二叉树建立成功!
");
else
printf("二叉树构造失败!!!
");
printf("中序遍历二叉树:");
InOrderTraverse(T,PrintElement);
printf("
");
}
#include <iostream>
#define MAXSIZE 100
using namespace std;
typedef char TElemType;
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
bool InOrderTraverse1(BiTree T) {
if(T) {
cout<<T->data;
InOrderTraverse1(T->lchild);
InOrderTraverse1(T->rchild);
}
}
bool InOrderTraverse2(BiTree T) {
if(T) {
InOrderTraverse2(T->lchild);
cout<<T->data;
InOrderTraverse2(T->rchild);
}
}
bool InOrderTraverse3(BiTree T) {
if(T) {
InOrderTraverse3(T->lchild);
InOrderTraverse3(T->rchild);
cout<<T->data;
}
}
bool CreateBiTree(BiTree &T) {
char ch;
cin>>ch;
if(ch=='#')
T=NULL;
else {
T=new BiTNode;
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
int Depth(BiTree T) {
int n,m;
if(T==NULL)
return 0;
else {
m=Depth(T->lchild);
n=Depth(T->rchild);
if(m>n)
return(m+1);
else
return(n+1);
}
}
int NodeCount(BiTree T) {
if(T==NULL)
return 0;
else
return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
int main()
{
BiTree a;
int height,num;
cout<<"请输入二叉树的元素:\n";
CreateBiTree(a);
cout<<"先序遍历法输出:\n";
InOrderTraverse1(a);
cout<<"\n中序遍历法输出:\n";
InOrderTraverse2(a);
cout<<"\n后序遍历法输出:\n";
InOrderTraverse3(a);
height=Depth(a);
num=NodeCount(a);
cout<<"\n该二叉树深度为:";
cout<<height<<endl;
cout<<"该二叉树结点数为:";
cout<<num;
return 0;
}
如何用伪代码实现二叉树路径上的结点最大乘积
树形DP 设f[i]表示点i的子树中,一条以i结尾的乘积为正最大链 设g[i]表示点i的子树中,一条以i结尾的乘积为负的最小链 设dp[i]表示点i的子树中的最大链 对于叶节点i,显然有f[i]=dp[i]=1;g[i]不存在 对于非叶节点i,如果i是正数 点i自成一链,也可以与f[l]或者f[r]连接...
用C++写一个二叉树的程序
\/\/1. 在内存总开辟头结点的空间malloc \/\/2. 将头结点的next域置空NULL \/\/3. 返回创建并设置好的链表的首地址 linklist_t *create_linklist(){ linknode_t *node = (linknode_t *)malloc(sizeof(linknode_t));node->next = NULL;return node;} \/\/判断当前链表是否为空 int empty_link...
数据结构二叉树的程序,用c语言怎么实现?
您好,想要实现一个二叉树,需要用到结构体来存储每个节点的信息,并使用指针来存储每个节点的左右子节点的地址。具体的实现方法可以参考下面的代码示例:include <stdio.h> include <stdlib.h> struct TreeNode { int val;struct TreeNode *left;struct TreeNode *right;};struct TreeNode* createNode...
一棵二叉树中序遍历CBEDAHGIJF后序CEDBHJIGFA,二叉树是啥,前序是...
printf("本程序实现二叉树的操作。\\n");printf("叶子结点以空格表示。\\n");printf("可以进行建立二叉树,递归先序、中序、后序遍历等操作。\\n");\/\/--- printf("\\n");printf("请建立二叉树。\\n");printf("建树将以三个空格后回车结束。\\n");printf("例如:1 2 3 4 5 6 (回车)...
Pascal难题 最优二叉树
1.二叉树的基本形态: 二叉树也是递归定义的,其结点有左右子树之分,逻辑上二叉树有五种基本形态: (1)空二叉树——(a); (2)只有一个根结点的二叉树——(b); (3)右子树为空的二叉树——(c); (4)左子树为空的二叉树——(d); (5)完全二叉树——(e)注意:尽管二叉树与树有许多相似之处,但二叉树不...
编写程序,用先序递归遍历法建立二叉树的二叉链表存储结构,输出其先序...
include "stdio.h"include "malloc.h"define ELEMTYPE char BiTNode *bulid() \/*建树*\/ { BiTNode *q;BiTNode *s[20];int i,j;char x;printf("请按顺序输入二叉树的结点以输入0和*号结束\\n");printf("请输入要输入的为第几个结点i=\\n");scanf("%d",&i);printf("请输入你要输入该...
关于数据结构C语言二叉树的程序,请人帮忙看看~谢谢
给你完全调好了,一切正常运行:include "stdio.h"include "stdlib.h"typedef int status; \/\/C中没有status类型,所以想使用这个类型你必须定义它 define OK 0 define ERROR -1 define OVERFLOW -2 \/\/OK、OVERLFLOW、ERROR这些宏的定义头文件中是没有的,所以你必须自己定义它们 typedef struct ...
有谁能够告诉我c语言的实验报告怎么写?
实验题目:编程实现:二叉树采用二叉链表存储,要求建立一棵二叉树,并输出要求的树状形式与结点编号。结点结构为:lchiedData numrchied 其中二叉树的num编号域为整数类型,data数据域为字符类型,要求生成二叉树中编号,从1开始进行连续编号,每个结点的编号大于其左右子树中孩子的编号,同一个结点的左右...
【高手快来】不用栈实现二叉树的后序非递归(C)
【高手快来】不用栈实现二叉树的后序非递归(C) 用栈和递归写的就不用贴过来了,那个我已经知道了,现在我只要不用栈实现的。类似于这样的:voidpreorder(BiTreeT)\/\/先序遍历{BiTrees[100];inttop=0;while(T||top){while(T){s[++top...用栈和递归写的就不用贴过来了,那个我已经知道了,现在我只要不用...
用C语言编写可以进行加减乘除整数运算混合运算的计算器,要求写思路,越...
[设计要求]实现整数浮点数的四则运算。 三.需求分析 该程序实现的是实数型的四则运算,并在此运算上又加入了幂”^”运算,该程序用一二叉树表示整个输入的算术表达式: (1)实现对结点的打印,便于结果分析; (2)实现对结点的统计; (3)实现中间结果的显示,可以看打印的结点,验证运算结果的正确与否。 四.概要设计...
宾侵巴替: #include<stdio.h> #include <stdlib.h> #include <malloc.h> #define OK 1 #define ERROR 0 #define OVERFLOW 0 typedef char TElemType; typedef int Status; typedef struct BiTNode {TElemType data;struct BiTNode *lchild,*rchild; }BiTNode,*...
竹山县19261317896: 已知有一棵二叉树编写函数实现对二叉树的中序遍历输出(用c语言)急用考试!~ - ?
宾侵巴替: 这是我以前做过的一道填空题,你可以参考一下.void preorder1(Bnode *root) {/* 前序遍历二叉树*/ if (root) {printf("%c",root->data); if(root->lchild) preorder1(root->lchild); if( root->rchild) preorder1(root->rchild); } } /* preorder */ void preorder2(...
竹山县19261317896: 用C实现输入二叉树的前序和中序遍历用C实现:输入二叉树的前序和中 ?
宾侵巴替: /* ds7_1.c: 二叉树的创建、显示、查找、遍历、插入 */ #include "stdio.h" #include "string. h" #define MAXSIZE 50 typedef struct node { char data; struct node *...
竹山县19261317896: 用C语言编程实现在线索二叉树上进行遍历 - ?
宾侵巴替: #include<iostream>#include<stdlib.h> #include<stdio.h>#include<malloc.h> using namespace std;#define maxsize 30 typedef struct T { struct T *lchild,*rchild; int data; }BiTNode,*BiTree; typedef struct {BiTree *base; BiTree *top; int stacksize; }...
竹山县19261317896: 编写程序 实现对建立的二叉树进行后序遍历,并输出遍历结果.二叉树用二叉链表存储结构存储 - ?
宾侵巴替: void search(TreeNode t)//递归后序遍历二叉树 { search(t.leftchild);//遍历节点左子树 search(t.rightchild);//遍历节点右子树 printf(t.data);//打印当前节点 } 差不多就这个意思吧
竹山县19261317896: 用c或c++实现遍历二叉树的中序算法,急求 - ?
宾侵巴替: void InOrder(BiTree root) { if(root!=NULL) { InOrder(root->LChild); coutdata InOrder(root->RChild); } } 这是递归算法,非递归用栈存储结点,每次循环右孩子先入栈,然后左孩子入栈
竹山县19261317896: 编写一个程序实现二叉树的先序中序后序遍历 - ?
宾侵巴替: void prvorder(bitree * t){ //前序遍历 if (t!=Null){ printf("%4d",t->data); prvorder(t->lchild); prvorder(t->rchild); } } void PreOrderUnrec(bitree *t) //先序遍历非递归算法; { bitree *p = t,*Stack[M]; int top = -1; while (p != Null || top != -1) { while (p!=Null) //...
竹山县19261317896: 建立如下二叉树,分别使用先根、中根、和后根对以上二叉树进行遍历,并输出遍历结果解 - ?
宾侵巴替: // 示例代码如下:#include <iostream> using namespace std; typedef struct node { char data; struct node *lchild; struct node *rchild; }*BiTree;//建立一个二叉树的函数 void creatBT(BiTree &T) { char ch; cin>>ch; if(ch=='.') { T=NULL; // 代表空子树...
竹山县19261317896: 二叉树遍历(c语言实现) - ?
宾侵巴替: #include <stdio.h>#include <malloc.h> typedef struct node{ int data; struct node *lchild,*rchild; }*treetp,tree; treetp create (treetp t,int c); void print1(treetp); void print2(treetp); void print3(treetp); int number=0; void main() { treetp t=0,r;r=create (t,0);...
竹山县19261317896: 求C语言编译程序:从键盘输入某一二叉树前序遍历及中序遍历序列,构造二叉树并输出该二叉树后序遍历序列 - ?
宾侵巴替: 输入树的节点,输入0结束 1 2 3 4 5 6 7 8 9 0中序打印 1->2->3->4->5->6->7->8->9-> 后序打印 9->8->7->6->5->4->3->2->1-> 前序打印 1->2->3->4->5->6->7->8->9->////////////////////////////////////////////////////////////////////////////////////////// #include<stdlib.h>#...