静态创建新结点、构造二叉树实现前序中序遍历还原
#include <iostream>
#include <string>
using namespace std;
//复原二叉树，。想出算法，
//静态版，递归的边界条件和递归式由str1的s1,e1,str2的s2,e2联合确定，缩小开头和结尾划分子问题
struct Node{
char data;
Node *rchild;
Node *lchild;
}Tree[50];
//静态如何创建新节点，就是loc游标移动
int loc;
Node *create(){
Tree[loc].lchild=Tree[loc].rchild=NULL;
//返回的是指针
return &Tree[loc++];
}
string str1,str2;
//在函数当中就要用到，提前定义
Node *build(int s1,int e1,int s2,int e2){
//直接每个都要创建新节点的！！我傻了
Node *ret=create();
ret->data=str1[s1];
int rootIdx=str2.find(str1[s1]);
//找到根节点在str2中的位置
//递归边界+递归式
if(rootIdx!=s2){
//左子树不为空
ret->lchild=build(s1+1,s1+(rootIdx-s2),s2,rootIdx-1);
//边界的确定最难了
}
if(rootIdx!=e2){
ret->rchild=build(s1+(rootIdx-s2)+1,e1,rootIdx+1,e2);
}
return ret;
}
//动态创建的办法，以及带出口边界的写法
node * create(int preL,int preR,int inL,int inR)
{
if(preL>preR)
return NULL;
node * p=new node;
p->data=pre[preL];
int k;
for(k=inL;k<inR;++k)
if(in[k]==pre[preL])
break;
int numleft=k-inL;
p->lchild=create(preL+1,preL+numleft,inL,k-1);
p->rchild=create(preL+numleft+1,preR,k+1,inR);
return p;
}
void postOrder(Node *r){
//遍历出口
if(r==NULL){
return;
}
postOrder(r->lchild);
postOrder(r->rchild);
printf("%c",r->data);
}
int main()
{
while(cin>>str1>>str2){
Node *T;
int e1=str1.size()-1;
int e2=str2.size()-1;
T=build(0,e1,0,e2);
postOrder(T);
printf("\n");
}
return 0;
}
二叉排序树查找、插入、构造科学方法
7
8 6 5 7 10 8 11
#include <iostream>
#include <vector>
using namespace std;
struct node{
int data;
node *rchild;
node *lchild;
};
//创建新结点还是要写一个，这样的话，才可以创建空结点，类似于链表知道到了链表尾部
node *newNode(int x){
node *Node=new node;
Node->data=x;
Node->rchild=Node->lchild=NULL;
return Node;
}
//如何构造二叉排序树
//有无到有，其实就是n次插入,而插入其实是查找的更进一步，找到空的位置！！
void insL(node *&root,int x)
{
//次数一定要加上引用，因为root结构发生了变化
if(root==NULL) {
//定义出口，空结点的位置创建新点
root=newNode(x);
return;
}
//原因在这里，相等时也可以插
/* if(x==root->data){
return;
//查找结点，如果发现这个结点被插入，就不用二次插入
}else if(x<root->data){
insL(root->lchild,x);
}else {
insL(root->rchild,x);
}*/
if(x<root->data) insL(root->lchild,x);
else insL(root->rchild,x);
}
//数组参数如何处理
//换成高级写法
void preOrder(node *T,vector<int> &vi){
if(T==NULL) return;
vi.push_back(T->data);
preOrder(T->lchild,vi);
preOrder(T->rchild,vi);
}
void postOrder(node *T,vector<int> &vi){
if(T==NULL) return;
postOrder(T->lchild,vi);
postOrder(T->rchild,vi);
vi.push_back(T->data);
}
void mirOrderPre(node *T,vector<int> &vi){
if(T==NULL) return;
vi.push_back(T->data);
mirOrderPre(T->rchild,vi);
mirOrderPre(T->lchild,vi);
}
void mirOrderPost(node *T,vector<int> &vi){
if(T==NULL) return;
mirOrderPost(T->rchild,vi);
mirOrderPost(T->lchild,vi);
vi.push_back(T->data);
}
vector<int> origin,pre,preM,post,postM;
int main()
{
int n;
while(cin>>n){
node *T=NULL;
for(int i=0;i<n;i++){
int x;
cin>>x;
origin.push_back(x);
//循环插入即可
insL(T,x);
}
preOrder(T,pre);
postOrder(T,post);
mirOrderPre(T,preM);
mirOrderPost(T,postM);
//容器vector可以直接相等！！！
if(origin==pre){
cout<<"YES"<<endl;
for(int i=0;i<post.size();i++){
cout<<post[i]<<" ";
}
}else if(origin==preM){
cout<<"YES"<<endl;
for(int i=0;i<postM.size();i++){
cout<<postM[i]<<" ";
}
}else{
cout<<"NO"<<endl;
}
cout<<endl;
}
return 0;
}
二叉排序树建立，非递归遍历方法
/*第三题：输入一个字符串，建立一个二叉排序树，并中序遍历输出；*/
/*这里采用了两种遍历，此处是非递归。下面注释的是递归*/
/*测试数据: poiuyt 输出数据;i o p t u y
测试数据: 621345 输出数据: 1 2 3 4 5 6*/
/*程序：*************************爱X的味道 07级华中农业大学计算机系*****************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 50
typedef struct Node
{
char data;
struct Node *Lchild;
struct Node *Rchild;
}Node,*BiTree;
typedef struct
{
BiTree elem[MAX];
int top;
}Stack;
void InitStack(Stack *s)
{
s->top=-1;
}
int Push(Stack *s,BiTree *T)
{
if(s->top>MAX-1) return 0;
s->top++;
s->elem[s->top]=(*T);
return 1;
}
int Pop(Stack *s,BiTree *T)
{
if(s->top<-1) return 0;
*T=s->elem[s->top];
s->top--;
return 1;
}
int IsEmpty(Stack s)
{
if(-1==s.top)
return 1;
else
return 0;
}
void InsertSortTree(BiTree *tree, char key)
{
BiTree T;
if(*tree == NULL)
{
T=(BiTree)malloc(sizeof(Node));
T->data=key;
T->Lchild=NULL;
T->Rchild=NULL;
*tree=T;
}
else
if((*tree)->data>key)
InsertSortTree(&((*tree)->Lchild),key);
else
if((*tree)->data<key)
InsertSortTree(&((*tree)->Rchild),key);
}
void CreateSortTree(BiTree *tree,char *str )
{
*tree=NULL;
int i=0;
while(str[i]!='\0')
{
InsertSortTree(&(*tree),str[i]);
i++;
}
}
void InOrdTree(BiTree T)
{
Stack s;
BiTree p=T;
InitStack(&s);
while(p!=NULL || !IsEmpty(s))
{
if(p!=NULL)
{
Push(&s,&p);
p=p->Lchild;
}
else
{
Pop(&s,&p);
printf(" %c ",p->data);
p=p->Rchild;
}
}
printf("\n\n");
}
int main()
{
char str[100]="\0";
BiTree tree;
printf("请输入一个字符串:\n\n");
gets(str);
CreateSortTree(&tree,str);
printf("中序遍历的结果是:\n\n");
InOrdTree(tree);
printf("\n\n");
return 0;
}
/*
/*输入一个字符串，建立一个二叉排序树，并中序遍历输出；
要考虑字符串，好难
#include <iostream>
#include <string>
#include <stdlib.h>
using namespace std;
typedef struct Node{
int data;
Node *lchild,*rchild;
}Node,*BiTree;
Node * creatNode(int data){
Node *T=(Node*)malloc(sizeof(Node));
if(T==NULL){
exit(0);
}
T->data=data;
T->lchild=NULL;
T->rchild=NULL;
return T;
}
//只有返回值时树节点才node *好不好
int InsertNode(BiTree &T,int key){
if(T==NULL){
T=creatNode(key);
return 1;
}
//应当要检查要插入的是否已经存在的，如果查找失败直接插入，则p指向遍历最后一个节点
//主要是根据key找位置
else if(key==T->data){
return 0;
}else if(key<T->data){
return InsertNode(T->lchild,key);
}else return InsertNode(T->rchild,key);
}
void inOrder(Node *T){
if(T!=NULL){
inOrder(T->lchild);
printf("%c ",T->data);
inOrder(T->rchild);
}
}
int main(){
Node *T=NULL;
string str;
cin>>str;
for(int i=0;i<str.size();i++){
//我错了，strcpy(c,s.c_str()); 用在一整个串
char c=str[i];
InsertNode(T,c);
}
//这个怎么能在循环内部呢.想看一下传值里面是怎么变化的！！
//刚才使用返回return，每次都返回当前节点~~
inOrder(T);
}
*/
无冗余字符串数组加建立二叉排序树
#include<stdio.h>
#include<malloc.h>
#include<string.h>
typedef struct BiNode
{
char *s;
struct BiNode *lchild;
struct BiNode *rchild;
}BiNode,*BiTree;
void PreOrder(BiTree T)
{
if(T)
{
printf("%s\n",T->s);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
int main()
{
char **str,e;
int row=1,col=1;
int tag,i,len;
BiTree T,r,t;
str=(char **)malloc(row*sizeof(char *));
str[col-1]=(char *)malloc(col*sizeof(char));
tag=1;
while((e=getchar())!='\n')
{
if(e==' ')
{
str[row-1][col-1]='\0';
tag=0;
continue;
}
else
{
if(tag==0)
{
row++;
col=2;
str=(char **)realloc(str,row*sizeof(char *));
str[row-1]=(char *)malloc(col*sizeof(char));
str[row-1][col-2]=e;
tag=1;
}
else
{
col++;
str[row-1]=(char *)realloc(str[row-1],col*sizeof(char));
str[row-1][col-2]=e;
}
}
}
str[row-1][col-1]='\0';
for(i=0;i<row;i++)
printf("%s\n",str[i]);
printf("\n");
len=strlen(str[0]);
T=(BiTree)malloc(sizeof(BiNode));
T->s=(char *)malloc((len+1)*sizeof(char));
strcpy(T->s,str[0]);
T->lchild=T->rchild=NULL;
t=T;
for(i=1;i<row;i++)
{
len=strlen(str[i]);
r=(BiTree)malloc(sizeof(BiNode));
r->s=(char *)malloc((len+1)*sizeof(char));
r->lchild=NULL;
r->rchild=NULL;
strcpy(r->s,str[i]);
while(t)
{
if(strcmp(t->s,r->s)>0)
{
if(t->lchild)
t=t->lchild;
else
{
t->lchild=r;
break;
}
}
else
{
if(t->rchild)
t=t->rchild;
else
{
t->rchild=r;
break;
}
}
}
t=T;
}
PreOrder(T);
return 0;
}
如何创建树链表，进行逆中序遍历
/*输入一个数列以0结尾，建立二叉遍历数，并对其进行逆中序遍历，释放空间*/
/*(2)输入一个数列以0位结束标志，建立二叉遍历树，并对其进行逆中序遍历，释放空间。*/
/*示例树为 : 1
/ \
2 3
\ \
4 5
/ \ \
6 7 8 每次输入一个数，按一次回车
输入的序列为 : 1 2 0 4 6 0 0 7 0 0 3 0 5 0 8 0 0
输出的结果应为: 8 5 3 1 7 4 6 2 */
————————————————
#include<stdio.h>
#include<stdlib.h>
typedef struct BiTNode{//二叉树数据结构定义；
int data;
BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree CreateTree(){//创建二叉树；
int value;
BiTree t;
scanf("%d",&value);
if(value==0)return NULL;
else{
t=(BiTree)malloc(sizeof(BiTNode));
t->data=value;
t->lchild=CreateTree();
t->rchild=CreateTree();
return t;
}
}
void ReInOrder(BiTree t){//逆中序遍历二叉树；
if(t!=NULL){
ReInOrder(t->rchild);
printf("%d ",t->data);
ReInOrder(t->lchild);
free(t);
}
}
int main(){
BiTree t;
printf("请按序输入二叉树结点的值(以0为标志结束)：\n");
t=CreateTree();
printf("逆中序遍历二叉树：\n");
ReInOrder(t);
system("pause");
}
//另一种写法
#include <iostream>
#include <32/bits/stdc++.h>
using namespace std;
struct node{
int data;
node *lchild,*rchild;
};
//两种方式，引用或者node *返回！！！
void insertT(node *&root){
int x;
cin>>x;
if(x==0) return;
if(root==NULL){
//应当创建新结点
root=new node;
root->data=x;
root->lchild=NULL;
root->rchild=NULL;
}
//每个结点应该都是空的，可以自己往下接s
insertT(root->lchild);
insertT(root->rchild);
}
void inOrdedr(node *root){
if(root!=NULL){
inOrdedr(root->rchild);
cout<<root->data<<" ";
inOrdedr(root->lchild);
}
}
int main()
{
node *T=NULL;
insertT(T);
inOrdedr(T);
return 0;
}
后序加中序还原加层序遍历
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
//后序加中序遍历推出
#include <iostream>
#include <queue>
#include <string>
using namespace std;
struct node{
int data;
node *lchild;
node *rchild;
};
int a[40],b[40];
node *build(int s1,int e1,int s2,int e2){
//终于知道了！！没有创建新结点，咋个有空间放数据和指针
if(s1>e1) return NULL;
//启示！！写法要配套，不然会出现没有NULL结点无法结束的情况
node *newNode=new node;
//后序遍历最后一个结点为根结点
newNode->data=a[e1];
int i;
for(i=s2;i<=e2;i++){
if(b[i]==a[e1]) break;
}
int pos=i;
int leftNum=pos-s2;
//左子树非空，构建左子树
newNode->lchild=build(s1,s1+leftNum-1,s2,pos-1);
newNode->rchild=build(s1+leftNum,e1-1,pos+1,e2);
return newNode;
}
void preOrder(node *T){
if(T==NULL) return;
cout<<T->data<<" ";
preOrder(T->lchild);
preOrder(T->rchild);
}
void floor(node *T){
queue<node*> q;
//注意队列当中存放的是地址
q.push(T);
//while条件就出口
while(!q.empty()){
//取队头，出队，访问
node *now=q.front();
q.pop();
cout<<now->data<<" ";
if(now->lchild!=NULL) q.push(now->lchild);
if(now->rchild!=NULL) q.push(now->rchild);
}
}
int main()
{
int n;
while(cin>>n){
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=0;i<n;i++){
cin>>b[i];
}
node *T;
T=build(0,n-1,0,n-1);
floor(T);
cout<<endl;
}
}
