层次建树

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;

typedef struct BiTNode {
    char data;
    struct BiTNode* lchild;
    struct BiTNode* rchild;
}BiTNode, * BiTree;

typedef struct tag {
    BiTree p;//树的某一个结点的地址值
    struct tag* next;
}tag_t, * ptag_t;

//前序遍历
void PreOrder(BiTree t) {
    if (t != NULL) {
        putchar(t->data);
        PreOrder(t->lchild);
        PreOrder(t->rchild);
    }
}
//中序遍历
void InOrder(BiTree t) {
    if (t != NULL) {
        InOrder(t->lchild);
        putchar(t->data);
        InOrder(t->rchild);
    }
}
//后序遍历
void PostOrder(BiTree t) {
    if (t != NULL) {
        PostOrder(t->lchild);
        PostOrder(t->rchild);
        putchar(t->data);
    }
}

//中序遍历非递归，非递归执行效率更高，考的概率很低
void InOrder2(BiTree T)
{
    SqStack S;
    InitStack(S); BiTree p = T;
    while (p || !StackEmpty(S))//逻辑或||
    {
        if (p)
        {
            Push(S, p);
            p = p->lchild;
        }
        else {
            Pop(S, p); putchar(p->c);
            p = p->rchild;
        }
    }
}
//层次遍历,广度优先遍历
void LevelOrder(BiTree T)
{
    LinkQueue Q;
    InitQueue(Q);
    BiTree p;
    EnQueue(Q, T);//树根入队
    while (!IsEmpty(Q))
    {
        DeQueue(Q, p);
        putchar(p->c);
        if (p->lchild != NULL)
            EnQueue(Q, p->lchild);
        if (p->rchild != NULL)
            EnQueue(Q, p->rchild);
    }
}
int main() {
    //树的结点
    BiTree pnew;
    //树根
    BiTree Tree = NULL;

    ptag_t front,cur = NULL;
    ptag_t rear = NULL;
    char d;
    while (scanf("%c",&d)!=EOF) {
        if (d == '\n') {
            break;
        }
        //生成新的节点
        pnew = (BiTree)malloc(sizeof(BiTNode));
        pnew->data = d;
        pnew->lchild = NULL;
        pnew->rchild = NULL;
        //队列生成新的节点
        ptag_t tnew = (ptag_t)malloc(sizeof(tag));
        tnew->p = pnew;
        if (Tree == NULL) {
            Tree = pnew;
            front = tnew;
            rear = tnew;
            cur = tnew;
            continue;
        }
        else {
            rear->next = tnew;
            rear = tnew;
        }
        if (cur->p->lchild == NULL) {
            cur->p->lchild = pnew;
        }
        else if (cur->p->rchild == NULL) {
            cur->p->rchild = pnew;
            cur = cur->next;
        }

    }
    printf("前序遍历\n");
    PreOrder(Tree);
    printf("\n");
    printf("中序遍历\n");
    InOrder(Tree);
    printf("\n");
    printf("后序遍历\n");
    PostOrder(Tree);
    
    return 0;
}

二叉排序树的操作

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;

typedef struct BiTNode {
    int data;
    struct BiTNode* lchild;
    struct BiTNode* rchild;
}BiTNode,* BiTree;

int BST_Insert(BiTree& T,int d) {
    //将节点初始化
    if (T == NULL) {
        T = (BiTree)malloc(sizeof(BiTNode));
        T->data = d;
        T->lchild = NULL;
        T->rchild = NULL;
        return 1;
    }else if (d == T->data) {
        return 0;
    }else if (d < T->data) {
        return BST_Insert(T->lchild, d);
    }else {
        return BST_Insert(T->rchild, d);
    }
    
}

void Creat_BST(BiTree& T, int str[], int n) {
    T = NULL;
    int i = 0;
    while (i < n) {
        BST_Insert(T, str[i]);
        i++;
    }
}

//查找节点
BiTree BST_Search(BiTree T,int n, BiTree& P) {
    //父节点
    P = NULL;
    while (T != NULL && T->data != n) {
        P = T;
        if (n > T->data) {
            T = T->rchild;
        }else if(n<T->data){
            T = T->lchild;
        }
    }
    return T;
}

//删除节点
void DeleteNode(BiTree& root, KeyType x) {
    if (root == NULL) {
        return;
    }
    if (root->key > x) {
        DeleteNode(root->lchild, x);
    }
    else if (root->key < x) {
        DeleteNode(root->rchild, x);
    }
    else { //查找到了删除节点
        if (root->lchild == NULL) { //左子树为空
            BiTree tempNode = root;
            root = root->rchild;
            free(tempNode);
        }
        else if (root->rchild == NULL) { //右子树为空
            BiTree tempNode = root;//临时指针
            root = root->lchild;
            free(tempNode);
        }
        else {  //左右子树都不为空
            //一般的删除策略是左子树的最大数据 或 右子树的最小数据 代替要删除的节点(这里采用查找左子树最大数据来代替)
            BiTree tempNode = root->lchild;
            if (tempNode->rchild != NULL) {
                tempNode = tempNode->rchild;
            }
            root->key = tempNode->key;
            DeleteNode(root->lchild, tempNode->key);
        }
    }
}
void PreOrder1(BiTree T) {
    if (T != NULL) {
        printf("%3d", T->data);
        PreOrder1(T->lchild);
        PreOrder1(T->rchild);
    }
}
int main() {
    BiTree T = NULL;
    BiTree Search;
    int a[] = { 1,4,5,7,3,6,2 };
    Creat_BST(T, a, 7);
    PreOrder1(T);
    BST_Search(T, 7, Search);
    return 0;
}