C語言實作二叉排序樹

程式以'#'結尾的二叉排序樹.

/*BinarySortTree*/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <stack>
#define SIZE 30
using namespace std;

/*二叉排序樹*/
typedef struct Node
{
    int data;
    struct Node *rchild,*lchild;
}*BSTree;
stack<char> s;
/*順序表*/
struct SeqList
{
    char data[SIZE];
};
/*建立順序表*/
SeqList Create_SeqList(SeqList L)
{
    gets(L.data);
    return L;
}
/*插入構造二叉排序樹*/
void Insert_BSTree(BSTree *T,char data)
{
    BSTree s; //新節點作為子節點或者根節點
    //樹為空，建立根節點
    if(*T==NULL)
    {
        s = (BSTree)malloc(sizeof(struct Node));
        s->data = data;
        s->lchild=NULL;
        s->rchild=NULL;
        *T=s;
    }
    //小插左大插右相等扔掉
    else if(data<(*T)->data)Insert_BSTree(&((*T)->lchild),data);
    else if(data>(*T)->data)Insert_BSTree(&((*T)->rchild),data);
}
/*插入建立二叉排序樹*/
void Create_BSTree(BSTree *T,SeqList L)
{
    *T=NULL;
    int k=0;
    char ch = L.data[k++];
    while(ch!='#')
    {
        Insert_BSTree(T,ch);
        ch = L.data[k++];
    }
}
/*利用棧中序周遊二叉排序樹*/
void StackInOrderTraverse(BSTree root)
{
    if(root!=NULL)
    {
        StackInOrderTraverse(root->lchild);//周遊左子樹
        s.push(root->data);
        StackInOrderTraverse(root->rchild);//周遊柚子樹
    }
    else
    {
        stack<char> s1;//輔助棧
        //輸出
        while(!s.empty())
        {
            s1.push(s.top());
            s.pop();
        }
        while(!s1.empty())
        {
            printf("%c",s1.top());
            s1.pop();
        }
    }
}

/*中序周遊二叉排序樹*/
void InOrderTraverse(BSTree root)
{
    if(root!=NULL)
    {
        InOrderTraverse(root->lchild);//周遊左子樹
        printf("%c",root->data);
        InOrderTraverse(root->rchild);//周遊柚子樹
    }
}
/*删除功能(好難)*/
void Delete_BSTree(BSTree *T,char data)
{
    BSTree p;
    BSTree p_parent;//儲存p的雙親節點
    BSTree s,s_parent;
    p = *T;
    while(p)
    {
        if(p->data==data)  //找到了
            break;
        p_parent = p; //記錄前驅賦初值
        if(p->data>data)  //根節點大的話找左子樹
            p = p->lchild;
        else p = p->rchild;
    }
    if(p==NULL)
    {
        printf("删除失敗，沒有這個資料\n");
        return;
    }
    //左子樹沒有的話,p可能是右子樹也可能是葉子
    if(p->lchild==NULL)
    {
        //根節點
        if(p_parent==NULL){
            *T = p->rchild;
        }
        //p是雙親的左子樹
        else if(p_parent->lchild==p){
            p_parent->lchild = p->rchild; //将其右子樹作為它雙親的左孩子
        }
        else  p_parent->rchild = p->rchild; //将其右子樹作為它雙親的右孩子
        free(p);
    }
    //左子樹有的話,p可能隻有左子樹或者右子樹左子樹都有
    else {
        s_parent = p;
        s = p->lchild;
        //找到p的最右下結點
        while(s->rchild){
            s_parent = s;
            s = s->rchild;
        }
        //如果p是s的雙親節點
        if(s_parent==p){
            s_parent->lchild = s->lchild; //将s的右子樹作為它右兒子
        }else s_parent->rchild = s->lchild;
        p->data = s->data;
        free(s);
    }
    printf("删除成功,删除後的序列為：\n");
    InOrderTraverse(*T);
}
int main()
{
    stack<char> s;
    char data;
    SeqList List;
    BSTree root=NULL;
    List = Create_SeqList(List);
    Create_BSTree(&root,List);
    InOrderTraverse(root);
    printf("\n");
    StackInOrderTraverse(root);
    printf("\n");
    printf("輸入你想删除的資料:");
    scanf("%c",&data);
    Delete_BSTree(&root,data);
    printf("\n");
    return 0;
}
           

　　

轉載于:https://www.cnblogs.com/liyinggang/p/5027426.html