排序二叉树

编程技术  /  houtizong 发布于 3年前   57

#include <iostream>#include <stdlib.h>using namespace std;typedef int Elemtype;struct TNode {    Elemtype data;    struct TNode *lChild, *rChild;};typedef struct Head {    TNode *root;} *Tree;//函数声明Tree init();TNode * initNode();void displayDESC(TNode *);void add(Tree , Elemtype);void displayASC(TNode *);int main(){    Tree tree = init();    int iSize;    Elemtype insertValue;    cout << "请输入要插入结点数：" << endl;    cin >> iSize;    for(int i = 0; i < iSize; i++) {        cin >> insertValue;        add(tree , insertValue);    }    cout << "排序后的树为(从小到大)：" << endl;    displayDESC(tree->root);    cout << endl;    cout << "排序后的树为(从大到小)：" << endl;    displayASC(tree->root);    return 0;}//初始化一棵树Tree init() {    Tree t = (Tree)malloc(sizeof(Head));    t->root = NULL;    return t;}//初始化一个树结点TNode * initNode() {    TNode *t = (TNode *)malloc(sizeof(TNode));    t->lChild = NULL;    t->rChild = NULL;    return t;}//从小到大展示树中所有元素void displayDESC(TNode *root) {    if(root == NULL) {        return;    }    displayDESC(root->lChild);    cout << root->data << " ";    displayDESC(root->rChild);}//从大到小展示树中所有元素void displayASC(TNode *root) {    if(root == NULL) {        return;    }    displayASC(root->rChild);    cout << root->data << " ";    displayASC(root->lChild);}//向树中添加元素结点void add(Tree tree , Elemtype value) {    //如果没有指向根结点的指针，直接返回    if(tree == NULL) {        return;    }    //初始化要插入的数据为一个树结点    TNode *t = initNode();    t->data = value;    //如果没有根结点，把要插入的结点当作根结点插入    if(tree->root == NULL) {        tree->root = t;        return;    }    //将要插入的点与树中的各结点值进行比较，小的放左树，大的放右树    TNode *tCurr = tree->root;    while(tCurr != NULL) {        if(t->data <= tCurr->data) {            if(tCurr->lChild != NULL) {                tCurr = tCurr->lChild;                continue;            } else {                tCurr->lChild = t;                break;            }        } else {            if(tCurr->rChild != NULL) {                tCurr = tCurr->rChild;                continue;            } else {                tCurr->rChild = t;                break;            }        }    }}