0

4个回答

0
0

#include"stdio.h"
#include"malloc.h"
#include"stdlib.h"
typedef struct lNode
{
char data;
struct lNode *lchild;
struct lNode *rchild;
}LNODE,*Tree;

typedef struct Node
{
Tree data;
struct Node * Next;
}NODE, * PNODE;

typedef struct Stack
{
PNODE pBottom;
PNODE pTop;
}STACK, * PSTACK;

//函数声明
PSTACK initStack(void);//创建栈
void push(PSTACK S,Tree val);//压栈
void pop(PSTACK S);//出栈
bool stackEmpty(PSTACK pS);

Tree CreateBiTree();//建树
void pretraverse(Tree T);//先序递归遍历
void Intraverse(Tree T);//中序递归遍历
void posttraverse(Tree T);//后序递归遍历
void NoIntraverse(Tree T);//中序非递归遍历

int main()
{
Tree T;
T=CreateBiTree();

pretraverse(T);printf("\n");

Intraverse(T);
printf("\n");

posttraverse(T);printf("\n");

NoIntraverse(T);printf("\n");

return 0;
}
//建树
Tree CreateBiTree()
{
char ch;
Tree T;
scanf("%c",&ch);
if(ch=='#')T=NULL;
else{
T = (Tree)malloc(sizeof(LNODE));
T->data = ch;
T->lchild = CreateBiTree();
T->rchild = CreateBiTree();
}
return T;//返回根节点
}

//先序递归遍历(遍历顺序：根左右)
void pretraverse(Tree T)
{
if(T!=NULL)
{
printf("%c",T->data);//输出根节点数据
pretraverse(T->lchild);//遍历左子树
pretraverse(T->rchild);//遍历右子树
}
}
//中序递归遍历(遍历顺序：左根右)
void Intraverse(Tree T)
{
if(T!=NULL)
{
Intraverse(T->lchild);//遍历左子树
printf("%c",T->data);//输出根节点数据
Intraverse(T->rchild);//遍历右子树

}
}
//后序递归遍历(遍历顺序：左右根)
void posttraverse(Tree T)
{
if(T!=NULL)
{
posttraverse(T->lchild);//遍历左子树
posttraverse(T->rchild);//遍历右子树
printf("%c",T->data);//输出根节点数据

}
}

//中序遍历（非递归遍历）
void NoIntraverse(Tree T)
{
PSTACK s;
s=initStack();
Tree p=T;
while(p!=NULL||!stackEmpty(s))
{
while(p)
{
push(s,p);
p=p->lchild;
}
if(!stackEmpty(s))
{
pop(s);

p=p->rchild;
}
}
}
PSTACK initStack(void)
{
PSTACK pS;
pS->pTop=(PNODE)malloc(sizeof(NODE));
if(pS->pTop==NULL)
{
printf("动态内存分配失败！");
exit(-1);
}
else
{
pS->pBottom=pS->pTop;
pS->pBottom->Next=NULL;

}
return pS;
}
void push(PSTACK pS,Tree val)
{
PNODE q;
q=(PNODE)malloc(sizeof(NODE));
if(q==NULL)
{
printf("动态内存分配失败！");
exit(-1);
}
else
{
q->data=val;
q->Next=pS->pTop;
pS->pTop=q;
}

}
void pop(PSTACK pS)
{
PNODE q;
if(pS->pTop==NULL)
{
printf("动态内存分配失败！");
exit(-1);
}
else
{
q=pS->pTop;
printf("%c",q->data);
pS->pTop=q->Next;
free(q);

}

}
bool stackEmpty(PSTACK pS)
{
if(pS->pTop==pS->pBottom)
{
return true;
}
return false;
}

0

#include"stdio.h"
#include"malloc.h"
#include"stdlib.h"
typedef struct lNode
{
char data;
struct lNode *lchild;
struct lNode *rchild;
}LNODE,*Tree;

typedef struct Node
{
Tree data;
struct Node * Next;
}NODE, * PNODE;

typedef struct Stack
{
PNODE pBottom;
PNODE pTop;
}STACK, * PSTACK;

//函数声明
PSTACK initStack(void);//创建栈
void push(PSTACK S,Tree val);//压栈
void pop(PSTACK S);//出栈
bool stackEmpty(PSTACK pS);

Tree CreateBiTree();//建树
void pretraverse(Tree T);//先序递归遍历
void Intraverse(Tree T);//中序递归遍历
void posttraverse(Tree T);//后序递归遍历
void NoIntraverse(Tree T);//中序非递归遍历

int main()
{
Tree T;
T=CreateBiTree();

pretraverse(T);printf("\n");

Intraverse(T);
printf("\n");

posttraverse(T);printf("\n");

NoIntraverse(T);printf("\n");

return 0;
}
//建树
Tree CreateBiTree()
{
char ch;
Tree T;
scanf("%c",&ch);
if(ch=='#')T=NULL;
else{
T = (Tree)malloc(sizeof(LNODE));
T->data = ch;
T->lchild = CreateBiTree();
T->rchild = CreateBiTree();
}
return T;//返回根节点
}

//先序递归遍历(遍历顺序：根左右)
void pretraverse(Tree T)
{
if(T!=NULL)
{
printf("%c",T->data);//输出根节点数据
pretraverse(T->lchild);//遍历左子树
pretraverse(T->rchild);//遍历右子树
}
}
//中序递归遍历(遍历顺序：左根右)
void Intraverse(Tree T)
{
if(T!=NULL)
{
Intraverse(T->lchild);//遍历左子树
printf("%c",T->data);//输出根节点数据
Intraverse(T->rchild);//遍历右子树

}
}
//后序递归遍历(遍历顺序：左右根)
void posttraverse(Tree T)
{
if(T!=NULL)
{
posttraverse(T->lchild);//遍历左子树
posttraverse(T->rchild);//遍历右子树
printf("%c",T->data);//输出根节点数据

}
}

//中序遍历（非递归遍历）
void NoIntraverse(Tree T)
{
PSTACK s;
s=initStack();
Tree p=T;
while(p!=NULL||!stackEmpty(s))
{
while(p)
{
push(s,p);
p=p->lchild;
}
if(!stackEmpty(s))
{
pop(s);

p=p->rchild;
}
}
}
PSTACK initStack(void)
{
PSTACK pS;
pS->pTop=(PNODE)malloc(sizeof(NODE));
if(pS->pTop==NULL)
{
printf("动态内存分配失败！");
exit(-1);
}
else
{
pS->pBottom=pS->pTop;
pS->pBottom->Next=NULL;

}
return pS;
}
void push(PSTACK pS,Tree val)
{
PNODE q;
q=(PNODE)malloc(sizeof(NODE));
if(q==NULL)
{
printf("动态内存分配失败！");
exit(-1);
}
else
{
q->data=val;
q->Next=pS->pTop;
pS->pTop=q;
}

}
void pop(PSTACK pS)
{
PNODE q;
if(pS->pTop==NULL)
{
printf("动态内存分配失败！");
exit(-1);
}
else
{
q=pS->pTop;
printf("%c",q->data);
pS->pTop=q->Next;
free(q);

}

}
bool stackEmpty(PSTACK pS)
{
if(pS->pTop==pS->pBottom)
{
return true;
}
return false;
}

0

106. Construct Binary Tree from Inorder and Postorder Traversal/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeN

#include using namespace std; char post[20],ins[20]; typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; BiTree Build_tree(int post_begin,int post_end,

/***************************************** Author :Crazy_AC(JamesQi) Time :2015 File Name : *****************************************/ // #pragma comment(linker, "/STACK:1024000000,10240

#include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct node { char data; struct node *Lchild; struct node *Rchild; }*BiTree,BiNode;int Mark_Root_Pos(char in[], c

#include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct node* tree_pointer; typedef struct node{ tree_pointer left_child; tree_pointer right_child; char data; }tree; int find

L2-006 树的遍历（25 分）#include&amp;lt;stdio.h&amp;gt;#include&amp;lt;stdlib.h&amp;gt;#include&amp;lt;iostream&amp;gt;#include&amp;lt;queue&amp;gt;#include&amp;lt;string.h&amp;gt;#include&amp;lt;stdlib.h&amp;gt;using namespace std;typedef struct Node{   ...

#include #include "queue" using namespace std; class BinaryTreeNode { public: char data; BinaryTreeNode * lc; BinaryTreeNode * rc; BinaryTreeNode(char C){ data = C ;lc = rc = NULL;} }; cla

#include using namespace std; typedef int ElemType; struct BTNode{ ElemType data; BTNode * lchild; BTNode * rchild; }; //先序+中序=建树 BTNode * PreInCreate(ElemType pre[],ElemType in[],int len)

#include&amp;lt;bits/stdc++.h&amp;gt; using namespace std; struct tree { char data; tree *l,*r; }; char a[55],b[55];//a前序b中序 int l1,h1,l2,h2; tree *creat() //前序建立 { tree *root; char c; c ...

#include #include using namespace std; #include typedef struct BiTNode{ char data ; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; void Visit(char data){ cout<<" "<<data ; } void PreOrderTrav

1. 前序遍历：先遍历根结点，然后遍历左子树，最后遍历右子树。 ABDHECFG 2.中序遍历：先遍历左子树，然后遍历根结点，最后遍历右子树。 HDBEAFCG 3.后序遍历：先遍历左子树，然后遍历右子树，最后遍历根节点。 HDEBFGCA

#include&amp;lt;stdio.h&amp;gt; #include&amp;lt;malloc.h&amp;gt; struct node{//建树 过程中输入这个树 char info; struct node *llink,*rlink; }; typedef struct node NODE; NODE *creat(){ char x; NODE *p; scanf(&quot;%c&quot;,&amp;a...

int last[maxn], mid[maxn], first[maxn], lc[maxn], rc[maxn], tot, val[maxn]; int newnode() { tot++; lc[tot] = rc[tot] = val[tot] = -1; return tot; } //已知中序 前序 //l1,r1是中序的指针，l2,r2是前序的指针 void build(...

#include&amp;lt;stdio.h&amp;gt; #include&amp;lt;string&amp;gt; //using namespace std; struct Node{     Node *lch;     Node *rch;     char c; }tree[50]; int n;//静态内存中已经分配的节点个数 Node *create(){//申请节点空间并返回其指针     tree[...

#include<iostream> #include<cstdio> #include<vector> #include<cstring> using namespace std; const int maxn = 1000+10; char p[maxn], m[maxn], b[maxn]; int n;struct node { struct node *l, *r; cha

#include #include #define ElemType char typedef struct BiTNode *BiTree; struct BiTNode{ ElemType data; BiTree lchild,rchild; }; BiTree CreateBiTree(){ ElemType ch; BiTree T; scan

#include&amp;lt;stdio.h&amp;gt; #include&amp;lt;stdlib.h&amp;gt; typedef struct BitNode { char data; struct BitNode *lchild,*rchild; }BitNode; BitNode* CreateBiT() //建立二叉树 { char ch;...

package tree.test; import java.util.LinkedList; import tree.domian.TreeNode; public class Test {     public static void main(String[] args) {         String hx = "KBFDCAE";         Strin

/** * 实现二叉树的创建、前序遍历、中序遍历和后序遍历 **/ package DataStructure; /** * Copyright 2014 by Ruiqin Sun * All right reserved * created on 2014-9-9 下午2:34:15 **/ public class BinTreeInt { pr...

#include   #include #include #include #include #include #include using namespace std; struct TreeNode { char val; TreeNode *left; TreeNode *right; }; int i = 1; TreeNode* create(){ Tree

#include<iostream> using namespace std; struct tree { tree *left; tree *right; char on; }; void createtree(tree *w) { char x; cin>>x; if(x=='#') { w=NULL; }

#include #include typedef struct k { int data; struct k *lc,*rc; }Btree; void inputin(int in[],int n) { int i; for(i=0;i<n;i++) scanf("%d",&in[i]); } void inputpost(int post[