10. 二叉排序树问题

题目来源和说明

本题来源于2005年华中科技大学计算机保研机试真题，试通过本次专题梳理和总结二叉排序树的问题。

题目描述

输入一系列整数，建立二叉排序树，并进行前序，中序，后序遍历。

样例

输入：
5
1 6 5 9 8
输出：
1 6 5 9 8
1 5 6 8 9
5 8 9 6 1

简要分析

这个程序的主要代码，是节点x插入树T中，保持二叉排序树的性质，即Insert(Node* T,int x)函数。这个主要是递归的思想。如果x<T.c，即插入左子树；如果x>T.c，即插入右子树。还需要特判一下，T是否为空。因为如果不处理T.c就会出问题。T为空，就直接创建一个节点赋值给T就可以啦~

C++ 代码

#include<iostream>
#include<string.h>
using namespace std;
struct Node {
    Node *l;
    Node *r;
    int c;
}Tree[110]; //静态数组

int idx;
Node *create() { //创建新节点
    Tree[idx].l=NULL;
    Tree[idx].r=NULL;
    return &Tree[idx++];
}

void postOrder(Node *T) { //后序遍历
    if(T->l!=NULL) {
        postOrder(T->l);
    }
    if(T->r!=NULL) {
        postOrder(T->r);
    }
    printf("%d ",T->c);
}

void inOrder(Node *T) { //中序遍历
    if(T->l!=NULL) {
        inOrder(T->l);
    }
    printf("%d ",T->c);
    if(T->r!=NULL) {
        inOrder(T->r);
    }
}

void preOrder(Node *T) { //后续遍历
    printf("%d ",T->c);
    if(T->l!=NULL) {
        preOrder(T->l);
    }
    if(T->r!=NULL) {
        preOrder(T->r);
    }
}

Node* Insert(Node *T,int x) { //插入数字
    if(T==NULL) { //当前树为空
        T=create();
        T->c=x;
        return T;
    }
    else if(x<T->c){
        T->l=Insert(T->l,x); //插入左子树
    }
    else if(x>T->c) {
        T->r=Insert(T->r,x); //插入右子树
    }
    return T;
}

int main() {
    int n;
    while(scanf("%d",&n)!=EOF) {
        idx=0;
        Node *T=NULL;
        for(int i=0;i<n;i++) {
            int x;
            scanf("%d",&x);
            T=Insert(T,x); //插入到排序树中
        }
        preOrder(T);
        printf("\n");
        inOrder(T);
        printf("\n");
        postOrder(T);
        printf("\n");
    }
    return 0;
}

同类题目

1. 二叉搜索树

C++代码