靜態(tài)創(chuàng)建新結(jié)點、構(gòu)造二叉樹實現(xiàn)前序中序遍歷還原

#include <iostream>
#include <string>
using namespace std;

//復(fù)原二叉樹，。想出算法，

//靜態(tài)版，遞歸的邊界條件和遞歸式由str1的s1,e1,str2的s2,e2聯(lián)合確定，縮小開頭和結(jié)尾劃分子問題

struct Node{
    char data;
    Node *rchild;
    Node *lchild;
}Tree[50];

//靜態(tài)如何創(chuàng)建新節(jié)點，就是loc游標(biāo)移動
int loc;
Node *create(){
    Tree[loc].lchild=Tree[loc].rchild=NULL;
    //返回的是指針
    return &Tree[loc++];
}
string str1,str2;
//在函數(shù)當(dāng)中就要用到，提前定義
Node *build(int s1,int e1,int s2,int e2){
    //直接每個都要創(chuàng)建新節(jié)點的??！我傻了
    Node *ret=create();
    ret->data=str1[s1];
    int rootIdx=str2.find(str1[s1]);
    //找到根節(jié)點在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;
}
//動態(tài)創(chuàng)建的辦法，以及帶出口邊界的寫法
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;
}

二叉排序樹查找、插入、構(gòu)造科學(xué)方法

7
8 6 5 7 10 8 11

#include <iostream>
#include <vector>
using namespace std;

struct node{
    int data;
    node *rchild;
    node *lchild;
};

//創(chuàng)建新結(jié)點還是要寫一個，這樣的話，才可以創(chuàng)建空結(jié)點，類似于鏈表知道到了鏈表尾部
node *newNode(int x){
    node *Node=new node;
    Node->data=x;
    Node->rchild=Node->lchild=NULL;
    return Node;
}

//如何構(gòu)造二叉排序樹
//有無到有，其實就是n次插入,而插入其實是查找的更進(jìn)一步，找到空的位置?。?
void insL(node *&root,int x)
{
    //次數(shù)一定要加上引用，因為root結(jié)構(gòu)發(fā)生了變化
    if(root==NULL) {
            //定義出口，空結(jié)點的位置創(chuàng)建新點
        root=newNode(x);
        return;
    }
    //原因在這里，相等時也可以插
 /*   if(x==root->data){
        return;
        //查找結(jié)點，如果發(fā)現(xiàn)這個結(jié)點被插入，就不用二次插入
    }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);
}
//數(shù)組參數(shù)如何處理



//換成高級寫法
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);
            //循環(huán)插入即可
            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;
}

二叉排序樹建立，非遞歸遍歷方法

/*第三題：輸入一個字符串，建立一個二叉排序樹，并中序遍歷輸出；*/
 
/*這里采用了兩種遍歷，此處是非遞歸。下面注釋的是遞歸*/
/*測試數(shù)據(jù): poiuyt    輸出數(shù)據(jù);i o p t u y   
  測試數(shù)據(jù): 621345     輸出數(shù)據(jù): 1 2 3 4 5 6*/
/*程序：*************************愛X的味道 07級華中農(nóng)業(yè)大學(xué)計算機(jī)系*****************************/
 
#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("中序遍歷的結(jié)果是:\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;
}

//只有返回值時樹節(jié)點才node *好不好
int InsertNode(BiTree &T,int key){
    if(T==NULL){
        T=creatNode(key);
        return 1;
    }

    //應(yīng)當(dāng)要檢查要插入的是否已經(jīng)存在的，如果查找失敗直接插入，則p指向遍歷最后一個節(jié)點
    //主要是根據(jù)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);

    }
    //這個怎么能在循環(huán)內(nèi)部呢.想看一下傳值里面是怎么變化的??！
    //剛才使用返回return，每次都返回當(dāng)前節(jié)點~~
    inOrder(T);
}
*/

無冗余字符串?dāng)?shù)組加建立二叉排序樹

#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;
}

如何創(chuàng)建樹鏈表，進(jìn)行逆中序遍歷

/*輸入一個數(shù)列以0結(jié)尾，建立二叉遍歷數(shù)，并對其進(jìn)行逆中序遍歷，釋放空間*/
/*(2)輸入一個數(shù)列以0位結(jié)束標(biāo)志，建立二叉遍歷樹，并對其進(jìn)行逆中序遍歷，釋放空間。*/
/*示例樹為 :             1    
                        /   \
                       2      3
                        \      \
                         4       5
                       /  \       \
                      6    7       8       每次輸入一個數(shù)，按一次回車
   輸入的序列為 : 1 2 0 4 6 0 0 7 0 0 3 0 5 0 8 0 0  
   輸出的結(jié)果應(yīng)為: 8 5 3 1 7 4 6 2           */
————————————————

#include<stdio.h>
#include<stdlib.h>
typedef struct BiTNode{//二叉樹數(shù)據(jù)結(jié)構(gòu)定義；
    int data;
    BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

BiTree CreateTree(){//創(chuàng)建二叉樹；
    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("請按序輸入二叉樹結(jié)點的值(以0為標(biāo)志結(jié)束)：\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){
        //應(yīng)當(dāng)創(chuàng)建新結(jié)點
        root=new node;
        root->data=x;
        root->lchild=NULL;
        root->rchild=NULL;
    }
    //每個結(jié)點應(yīng)該都是空的，可以自己往下接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){
    //終于知道了?。]有創(chuàng)建新結(jié)點，咋個有空間放數(shù)據(jù)和指針
    if(s1>e1) return NULL;
    //啟示?。懛ㄒ涮?，不然會出現(xiàn)沒有NULL結(jié)點無法結(jié)束的情況
    node *newNode=new node;

    //后序遍歷最后一個結(jié)點為根結(jié)點
    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;

    //左子樹非空，構(gòu)建左子樹
    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;
    //注意隊列當(dāng)中存放的是地址
    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;
  }
}