二叉排序树

二叉排序树的建立和遍历

标准做法，每次都从头结点开始遍历,并插入数据点

#include<iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include<vector>
#include<iterator>
using namespace std;
typedef struct node
{
    int data;
    struct node* l, * r;
}BiTode, * BiTree;
BiTree t1;
int flag;
vector<int>inorder;
vector<int>houxu;
vector<int>::iterator it;
BiTree& insert(BiTree& t, int x)
{
    if (t == NULL)
    {
        t = (struct node*)malloc(sizeof(struct node));
        t->data = x;
        t->l = NULL;
        t->r = NULL;
    }
    else if (x == t->data)
    {
        return t;
    }
    else if (x < t->data)
    {
        return insert(t->l, x);
    }
    else
    {
        return insert(t->r, x);
    }
}
void bianli(BiTree& head)
{
    if (head != NULL)
    {
        cout << head->data << " ";
        bianli(head->l);
        inorder.push_back(head->data);
        bianli(head->r);
        houxu.push_back(head->data);
    }
}
int main()
{
    BiTree t = NULL;
    BiTree head = NULL;
    int n;
    int a[110];
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        insert(t, a[i]);//t = head;并且t的值从来都不变,不能使用下面的t = insert(t,a[i]),因为这里insert函数直接return后返回的值并不是刚开始的根节点，而是插入的叶子节点，后面两个方法相当于只有一个return，而这里在每个insert函数执行中都return的后果就是return值一直不变，最终将叶子节点的位置赋给t，将导致下次插入时只能从叶子节点开始。
        if (flag == 0)
        {
            head = t;
            flag = 1;
        }
    }
    bianli(head);
    cout << "\n";
    for (it = inorder.begin(); it != inorder.end(); it++)
    {
        cout << (*it) << " ";
    }
    cout << "\n";
    for (it = houxu.begin(); it != houxu.end(); it++)
    {
        cout << (*it) << " ";
    }
    cout << "\n";
    return 0;
}

可以直接调用insert,让它在分配节点空间的时候完成赋值，此时return的位置在insert函数的结尾，而且请注意，即使在main函数中每次都令t为insert函数的返回值，t的值也一直是头结点，因为insert函数经过递归调用，最终返回的值一直是头结点。

#include<iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include<vector>
#include<iterator>
using namespace std;
typedef struct node
{
    int data;
    struct node* l, * r;
}BiTode, * BiTree;
BiTree t1;
int flag;
vector<int>inorder;
vector<int>houxu;
vector<int>::iterator it;
BiTree& insert(BiTree& t, int x)
{
    if (t == NULL)
    {
        t = (struct node*)malloc(sizeof(struct node));
        t->data = x;
        t->l = NULL;
        t->r = NULL;
    }
    else if (x == t->data)
    {
        return t;
    }
    else if (x < t->data)
    {
        insert(t->l, x);
    }
    else
    {
        insert(t->r, x);
    }
    return t;//和上一个方法的不同在于return只有这一处，返回的是当前插入值的位置，最终经过层层返回之后，一直返回的是头结点
}
void bianli(BiTree& head)
{
    if (head != NULL)
    {
        cout << head->data << " ";
        bianli(head->l);
        inorder.push_back(head->data);
        bianli(head->r);
        houxu.push_back(head->data);
    }
}
int main()
{
    BiTree t = NULL;
    BiTree head = NULL;
    int n;
    int a[110];
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        t = insert(t, a[i]);//这里虽然这样赋值，但是t的值一直是头结点。
        if (flag == 0)
        {
            head = t;
            flag = 1;
        }
    }
    bianli(head);
    cout << "\n";
    for (it = inorder.begin(); it != inorder.end(); it++)
    {
        cout << (*it) << " ";
    }
    cout << "\n";
    for (it = houxu.begin(); it != houxu.end(); it++)
    {
        cout << (*it) << " ";
    }
    cout << "\n";
    return 0;
}

可以在insert函数中显示地将递归调用的返回值赋给t的左子树或者是t的右子树，其余和方法二相同，以下只给出insert函数的代码

BiTree& insert(BiTree& t, int x)
{
    if (t == NULL)
    {
        t = (struct node*)malloc(sizeof(struct node));
        t->data = x;
        t->l = NULL;
        t->r = NULL;
    }
    else if (x == t->data)
    {
        return t;
    }
    else if (x < t->data)
    {
        t->l = insert(t->l, x);
    }
    else
    {
        t->r = insert(t->r, x);
    }
    return t;
}

判断两个序列是否能组成同一棵二叉排序树

#include<iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef struct node
{
    int data;
    struct node* l, * r;
}BiTode, * BiTree;
BiTree t1, t2;
int flag;
BiTree insert(BiTree t, int x)
{
    if (t == NULL)
    {
        t = (struct node*)malloc(sizeof(struct node));
        t->data = x;
        t->l = NULL;
        t->r = NULL;
    }
    else if (x < t->data)
    {
        t->l = insert(t->l, x);
    }
    else
    {
        t->r = insert(t->r, x);
    }
    return t;
}
BiTree creat(char a[], int n)
{
    int j = 0;
    BiTree t = NULL;
    while (j < n)
    {
        t = insert(t, a[j] - '0');
        j++;
    }
    return t;
}
int compare(BiTree t1, BiTree t2)
{
    if (t1 == NULL && t2 == NULL)
    {
        return 1;
    }
    else if (t1 == NULL || t2 == NULL)
    {
        flag = 0;
        return 0;
    }
    else if (t1->data != t2->data)
    {
        flag = 0;
        return 0;
    }
    else
        return compare(t1->l, t2->l) && compare(t1->r, t2->r);
}
int main()
{
    int n, len;
    char a[11], b[11];
    //while (scanf("%d", &n) != EOF && n)
    while(cin>>n&&n)
    {


        //scanf("%s", a);
        cin >> a;
        len = strlen(a);//strlen的参数只能是char 类型
        t1 = creat(a, len);
        while (n--)
        {
            //scanf("%s", b);
            cin >> b;
            t2 = creat(b, len);
            flag = 1;
            compare(t1, t2);
            if (flag == 1)
                printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;

}

二叉排序树插入节点并输出父结点

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
typedef struct node {
    int key;
    struct node* left;
    struct node* right;
}Node, * Tree;
int s;
int n;
int sav = -1;
void ins(Tree& T, int data) {
    if (!T) {
        T = (Tree)malloc(sizeof(Node));
        cout << sav << endl;
        T->key = data;
        T->left = NULL;
        T->right = NULL;
    }
    if (data < T->key) {
        sav = T->key;             //插入的同时保存父节点的数值
        ins(T->left, data);
    }
    if (data > T->key) {
        sav = T->key;
        ins(T->right, data);
    }
}
int main() {
    cin >> n;
    Tree T = NULL;
    for (int i = 0; i < n; i++) {
        cin >> s;
        ins(T, s);
    }
}