注册 登录
编程论坛 → 数据结构与算法

[原创][开源]二叉树基本操作的程序实现.

nuciewth 发布于 2007-05-05 16:10， 22677 次点击

//Bintree.h
#include<stdio.h>
#include<malloc.h>
typedef struct Binnode{//二叉树结点结构体
char data;
struct Binnode *lchild;
struct Binnode *rchild;
};
typedef Binnode *Bintree ;

typedef struct stack{ //二叉树结点栈
Bintree data[100];
int flag[100];
int top;
};

typedef struct queue{ //二叉树结点队列
Bintree data[30];
int front;
int rear;
};



/*******************************************/
/* 按照前序遍历建立二叉树 */
/*******************************************/

void Creat_Bintree(Bintree *root)
{
char ch;
if((ch=getchar())==' ')
{
*root=NULL;

}
else
{
*root=(Binnode*)malloc(sizeof(Binnode));
(*root)->data=ch;
Creat_Bintree(&(*root)->lchild);
Creat_Bintree(&(*root)->rchild);
}
}

/*******************************************/
/* 按照前序递归遍历二叉树 */
/*******************************************/

void Preorder1(Bintree t)
{
if(t!=NULL)
{
printf("%c",t->data);
Preorder1(t->lchild);
Preorder1(t->rchild);
}
}


/*******************************************/
/* 按照中序递归遍历二叉树 */
/*******************************************/

void Inorder1(Bintree t)
{
if(t!=NULL)
{
Inorder1(t->lchild);
printf("%c",t->data);
Inorder1(t->rchild);
}
}

/*******************************************/
/* 按照后序递归遍历二叉树 */
/*******************************************/

void Posorder1(Bintree t)
{
if(t!=NULL)
{
Posorder1(t->lchild);
Posorder1(t->rchild);
printf("%c",t->data);
}
}
/*******************************************/
/* 按照前序非递归遍历二叉树 */
/*******************************************/

void Preorder2(Bintree t)
{
Bintree pre=t;
stack s;
s.top=0;
printf("输出前序遍历序列:");
while(pre||s.top>0)
{
if(pre)
{
printf("%c",pre->data);
s.data[s.top++]=pre;
pre=pre->lchild;
}
else
{
pre=s.data[--s.top]->rchild;
}
}
printf("\n\n");
}

/*******************************************/
/* 按照中序非递归遍历二叉树 */
/*******************************************/

void Inorder2(Bintree t)
{
Bintree pre=t;
stack s;
s.top=0;
printf("输出中序遍历序列:");
while(pre||s.top>0)
{
if(pre)
{
s.data[s.top++]=pre;
pre=pre->lchild;
}
else
{
pre=s.data[--s.top];
printf("%c",pre->data);
pre=pre->rchild;
}
}
printf("\n\n");
}

/*******************************************/
/* 按照后序非递归遍历二叉树 */
/*******************************************/

void Posorder2(Bintree t)
{
stack s;
s.top=-1;
printf("输出后序遍历序列:");
while(t!=NULL||s.top!=-1)
{
while(t)
{
s.top++;
s.flag[s.top]=0;
s.data[s.top]=t;
t=t->lchild;

}
while(s.top>=0&&s.flag[s.top]==1)
{
t=s.data[s.top];
printf("%c",t->data);
s.top--;
}
if(s.top>=0)
{
t=s.data[s.top];
s.flag[s.top]=1;
t=t->rchild;
}
else
{
t=NULL;
}
}
printf("\n\n");
}


/*******************************************/
/* 按照层次遍历二叉树 */
/*******************************************/
void Levelorder(Bintree t)
{
queue q;
q.data[0]=t;
q.front=0;q.rear=1;
printf("层次遍历二叉树结果:");
while(q.front<q.rear)
{
if(q.data[q.front])
{
printf("%c",q.data[q.front]->data);
q.data[q.rear++]=q.data[q.front]->lchild;
q.data[q.rear++]=q.data[q.front]->rchild;
q.front++;
}
else
{
q.front++;
}
}
printf("\n\n");
}

48 回复
#2
nuciewth2007-05-05 16:11

#include"Bintree.h"
/*******************************************/
/* 递归法将二叉树的左右子树互换 */
/*******************************************/
void Exchange1(Bintree t)
{
Bintree temp;
if(t)
{
Exchange1(t->lchild);
Exchange1(t->rchild);
temp=t->lchild;
t->lchild=t->rchild;
t->rchild=temp;
}
}
/*******************************************/
/* 非递归法将二叉树的左右子树互换 */
/*******************************************/
void Exchange2(Bintree t)
{
Bintree temp;
stack s;
s.top=0;
while(t||s.top)
{
if(t)
{
s.data[s.top++]=t;
temp=t->lchild;
t->lchild=t->rchild;
t->rchild=temp;
t=t->lchild;
}
else
{
t=s.data[--s.top]->rchild;
}

}
}
int main()
{
Bintree t;
Creat_Bintree(&t);
Exchange2(t);
Inorder2(t);
return 0;
}
#3
nuciewth2007-05-05 16:11

#include"Bintree.h"
/*******************************************/
/* 递归法求叶子结点个数 */
/*******************************************/
int Leaves_Num1(Bintree t)
{
if(t)
{
if(t->lchild==NULL&&t->rchild==NULL)
{
return 1;
}
return Leaves_Num1(t->lchild)+Leaves_Num1(t->rchild);
}
return 0;
}

/*******************************************/
/* 非递归法求叶子结点个数 */
/*******************************************/
int Leaves_Num2(Bintree t)
{
int count=0;
stack s;
s.top=0;
while(t||s.top>0)
{
if(t)
{
s.data[s.top++]=t;
if(t->lchild==NULL&&t->rchild==NULL)
{

count++;
}
t=t->lchild;
}
else
{
t=s.data[--s.top]->rchild;
}
}
return count;
}


int main()
{
int count=0;
Bintree t;
Creat_Bintree(&t);
count=Leaves_Num2(t);
printf("该二叉树的叶子结点数为:%d\n",count);
return 0;
}
#4
nuciewth2007-05-05 16:11

#include"Bintree.h"

/**********************************************/
/* 求一棵树的高度 */
/**********************************************/

int Depth(Bintree t)
{
int lh , rh ;
if( NULL == t )
{
return 0 ;
}
else
{
lh = Depth( t->lchild ) ;
rh = Depth( t->rchild ) ;
return ( lh > rh ? lh : rh ) + 1 ;
}
}

int main()
{
Bintree t ;
Creat_Bintree( &t ) ;
printf( "树的高度是%d\n" , Depth( t ) ) ;
return 0 ;
}
#5
nuciewth2007-05-05 16:13

#include"Bintree.h"
/*******************************************************/
/* 已知一课棵二叉树的中序和后序，建立这棵树 */
/*******************************************************/

void In_Pos_order(Bintree *t,char *s,char *r)
{
char La[30],Lb[30],Ra[30],Rb[30];
int i,len,length=strlen(r);
if(length>0&&r[length-1]!='\0')
{
*t=(Binnode *)malloc(sizeof(Binnode));
(*t)->data=r[length-1];
for(i=0;s[i]!=r[length-1];i++)
{
Ra[i]=s[i];
La[i]=r[i];
}
len=i;
Ra[len]='\0'; //左中
La[len]='\0'; //左后
for(i=len+1;i<strlen(s);i++)
{
Rb[i-len-1]=s[i];
}
Rb[i-len-1]='\0';
for(i=len;i<strlen(r)-1;i++)
{
Lb[i-len]=r[i];
}
Lb[i-len]='\0';
In_Pos_order(&(*t)->lchild,Ra,La);
In_Pos_order(&(*t)->rchild,Rb,Lb);
}
else
{
*t=NULL;
}
}

int main()
{
Bintree t;
char in[30]="ABCEFGHD",pos[30]="ABFHGEDC";//测试数据
printf("输入中序遍历序列:");
scanf("%s",in);
printf("输入后序遍历序列:");
scanf("%s",in);
In_Pos_order(&t,in,pos);
Preorder2(t);
}
#6
nuciewth2007-05-05 16:13

#include"Bintree.h"
/*******************************************************/
/* 判断两棵是否等价 */
/*******************************************************/

int Is_equal( Bintree t1 , Bintree t2 )
{
int t=0;
if(NULL == t1 && NULL == t2)
{
t=1;
}
else
{
if(NULL !=t1 &&NULL != t2 )
{
if(t1->data == t2->data)
{
if(Is_equal(t1->lchild,t2->lchild))
{
t=Is_equal(t1->rchild,t2->rchild);
}
}
}
}
return t;
}
int main()
{
Bintree t1,t2;
Creat_Bintree(&t1);
getchar();
Creat_Bintree(&t2);
if(Is_equal(t1,t2))
{
printf( "Yes!\n") ;
}
else
{
printf( "No!\n" ) ;
}

return 0 ;
}
#7
nuciewth2007-05-05 16:15

#include"Bintree.h"
/****************************************************/
/* 查找某个信息是否在这棵树中 */
/****************************************************/

Bintree locale_x(Bintree t,char x)
{
Bintree p;
if(t==NULL) return NULL;
else
{
if( t -> data == x ) return t;
else
{
p = locale_x(t->lchild,x);
if(p)return p;
else
return locale_x(t->rchild,x);
}
}
}

int main()
{
Bintree root,p;
char ch;
Creat_Bintree(&root);
getchar();
printf("输入要查找的值:");
scanf("%c",&ch);
p=locale_x(root,ch);
if(p)printf( "YES!\n" ) ;
else printf( "NO!\n" ) ;
return 0;
}
#8
nuciewth2007-05-05 16:16

#include"Bintree.h"

/****************************************************/
/* 树的结点个数 */
/****************************************************/
int num_of_node(Bintree t)
{
if(t==NULL)return 0 ;
else return num_of_node(t->lchild)+num_of_node(t->rchild)+1;
}


int main()
{
Bintree root,p;
Creat_Bintree(&root);
printf("%d\n",num_of_node(root));
return 0;
}
#9
nuciewth2007-05-05 16:17

#include"Bintree.h"

/*******************************************************/
/* 已知一课棵二叉树的中序和前序序列，建立这棵树 */
/*******************************************************/

void Pre_In_order(Bintree *t,char *s,char *r)
{
char La[30],Lb[30],Ra[30],Rb[30];
int i,len;
if(s[0]!='\0')
{
*t=(Binnode *)malloc(sizeof(Binnode));
(*t)->data=s[0];
for(i=0;r[i]!=s[0];i++)
{
Ra[i]=r[i];
}
len=i;
Ra[len]='\0'; //左中
for(i=0;i<len;i++)
{
La[i]=s[i+1];
}
La[len]='\0'; //左前
for(i=len+1;i<strlen(r);i++)
{
Rb[i-len-1]=r[i];
}
Rb[i-len-1]='\0';
for(i=len+1;i<strlen(s);i++)
{
Lb[i-len-1]=s[i];
}
Lb[i-len-1]='\0';
Pre_In_order(&(*t)->lchild,La,Ra);
Pre_In_order(&(*t)->rchild,Lb,Rb);
}
else
{
*t=NULL;
}
}

int main()
{
Bintree t;
char pre[30]="ABCDEF",in[30]="CBAEDF";//测试数据
printf("输入前序遍历序列:");
scanf("%s",pre);
printf("输入中序遍历序列:");
scanf("%s",in);
Pre_In_order(&t,pre,in);
Posorder1(t);
}
#10
nuciewth2007-05-05 16:19

#include<stdio.h>
#include<malloc.h>
typedef struct node{
int data;
struct node *lchild,*rchild,*next;
}hufnode;

typedef hufnode *linkhuf;
/****************************************************/
/* huffman树 */
/****************************************************/
linkhuf Creat_Node(int n) //创建一单链表
{
linkhuf head,pre,p;
int x;
head=NULL;
while(n--)
{
scanf("%d",&x);
p=(linkhuf)malloc(sizeof(hufnode));
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
if(NULL==head)
{
head=p;
pre=head;
}
else
{
p->next=pre->next;
pre->next=p;
pre=pre->next;
}
}
return head;
}
linkhuf insert(linkhuf root , linkhuf s)//将结点S插入到有序Huffman root中。
{
linkhuf p1,p2;
if(NULL == root ) root=s;
else
{
p1=NULL;
p2=root;
while(p2&&p2->data<s->data)
{
p1=p2;
p2=p2->next;
}
s->next=p2;
if(NULL==p1)
{
root=s;
}
else
{
p1->next=s;
}
}
return root;
}


void Preorder1(linkhuf t)
{
if(t!=NULL)
{
printf("%-6d",t->data);
Preorder1(t->lchild);
Preorder1(t->rchild);
}
}
void creathuffman(linkhuf *root)//构造Huffman树。
{
linkhuf s, rl,rr;
while(*root && (*root)->next)
{
rl=*root;
rr=(*root)->next;
*root=rr->next;
s=(linkhuf)malloc(sizeof(hufnode));
s->next=NULL;
s->data=rl->data+rr->data;
s->lchild=rl;
s->rchild=rr;
rl->next=rr->next=NULL;
*root=insert(*root,s);
}
}

int main()
{
linkhuf root;
int n;
scanf("%d",&n);
root=Creat_Node(n);
creathuffman(&root);
Preorder1(root);
printf("\n");
return 0;
}
#11
fyi11062007-05-05 16:26
我顶，虽然我没看，但实在感动楼主的用苦良心，我们做数据结构实验时就写了这些，写得好烦呀，楼主早贴出来该多好。
#12
lishiyong1102007-05-05 22:48
看了一些  特别是非递归形式非常好  非常感谢
#13
kongbei2007-05-07 08:52
写得很好呀！！！
#14
nuciewth2007-05-12 20:04

/************************************************************/
/* 按层次顺序建立一棵二叉树 */
/************************************************************/
#include"Bintree.h"

Bintree Level_Creat()
{
Bintree root,p,s;
queue node;
node.front=node.rear=0;
char ch;
ch=getchar();
if(ch==' ')
{
return NULL;
}
root=(Binnode*)malloc(sizeof(Binnode)); //生成根结点
root->data=ch;
node.data[node.rear++]=root; //用队列实现层次遍历
while(node.front<node.rear)
{
p=node.data[node.front++];
ch=getchar(); //为了简化操作，分别对左右子结点进行赋值。
if(ch!=' ')//子树不空则进队列进行扩充。下同
{
s=(Binnode*)malloc(sizeof(Binnode));
s->data=ch;
p->lchild=s;
node.data[node.rear++]=s;
}
else
{
p->lchild=NULL;
}
ch=getchar();
if(ch!=' ')
{
s=(Binnode*)malloc(sizeof(Binnode));
s->data=ch;
p->rchild=s;
node.data[node.rear++]=s;
}
else
{
p->rchild=NULL;
}
}
return root;
}
int main()
{
Bintree root;
root=Level_Creat();
Inorder1(root);//测试，中序遍历
return 0;
}
#15
Gislover2007-05-15 10:21

#16
yuesheng2007-05-15 11:46
  接受了你的算法思想，谢谢了啊，不过问下，递归建树，为什么要用指针的指针？不能直接用指针啊？
#17
nuciewth2007-05-15 12:32
对结点本身是个指针.如果你要修改根结点,那就得用指针的指针才可以保存修改.
#18
yuji5125122007-05-16 08:46
楼主写的很好，前几个看懂了，后几个不是太明白
#19
yuesheng2007-05-20 21:52
问下楼主，比较复杂的程序是怎样想到怎么做的？看的懂，但是自己通常编不出来
#20
nuciewth2007-05-21 21:51
练多了就可以了.有些经典的算法可以去背,不过我记性差点,至今没背好.
熟能生巧.呵呵.
#21
nuciewth2007-06-25 23:50

//中序穿线二叉树.
#include<stdio.h>
#include<malloc.h>

typedef struct Binnode {
char data;
int lflag,rflag;//左右标记
/*
lflag=0 表示结点的左指针指向其左子女。
lflag=1 表示结点的左指针指向其中序遍历的前驱。
rflag=0 表示结点的左指针指向其右子女。
rflag=1 表示结点的左指针指向其中序遍历的前驱。
*/
struct Binnode *lchild,*rchild;
};
typedef Binnode* Bintree;

Bintree pre=NULL; //初始化前驱结点

/*******************************************/
/* 按照前序遍历建立二叉树 */
/*******************************************/

void Creat_Bintree(Bintree *root)
{
char ch;
if((ch=getchar())==' ')
{
*root=NULL;

}
else
{
*root=(Binnode*)malloc(sizeof(Binnode));
(*root)->data=ch;
Creat_Bintree(&(*root)->lchild);
Creat_Bintree(&(*root)->rchild);
}
}

/*******************************************/
/* 对二叉树进行中序穿线 */
/*******************************************/
void Inthreading(Bintree *t)
{
if(*t)
{
Inthreading(&(*t)->lchild);// 中序线索化左子树
(*t)->lflag=((*t)->lchild)?0:1;//对当前结点及其前驱结点进行穿线
(*t)->rflag=((*t)->rchild)?0:1;
if(pre)
{
if((*t)->lflag==1) (*t)->lchild=pre;
if(pre->rflag==1) pre->rchild=*t;
}
pre=*t;
Inthreading(&(*t)->rchild);// 中序线索化右子树
}
}

/*******************************************/
/* 中序遍历穿线二叉树 */
/*******************************************/

Bintree Insuccnode(Bintree p) //寻找结点P在中序遍历下的后继结点
{
Bintree q;
if(p->rflag==1)//P的右指针为线索，恰巧指向P的后继结点
{
return p->rchild;
}
else //寻找P的右子树中最左下的结点
{
q=p->rchild;
while(q->lflag==0)
{
q=q->lchild;
}
return q;
}
}

/********************************************************/
/* 中序遍历中序穿线二叉树 */
/********************************************************/


void Inthrtree(Bintree p)
{
if(p)
{
while(p->lflag==0) //求P中序遍历下的第一个结点
{
p=p->lchild;
}
do
{
printf("%-3c",p->data);
p=Insuccnode(p); //求P中序遍历下的后继结点
}
while(p);
}
}


int main()
{
Bintree t;
Creat_Bintree(&t);
Inthreading(&t);
Inthrtree(t);
printf("\n\n");
return 0;
}
#22
AndyVS862007-06-26 08:49
#23
zklhp2007-07-13 00:43

谢了
#24
qxyaizzc2007-11-22 20:01
谢谢 楼住
#25
cosdos2007-12-01 22:27
我刚刚学到二叉树。
#26
静思2007-12-01 23:11
好东西，收藏了
#27
Lupkid2007-12-02 14:27
只能说牛B LE
#28
crazyboy2162007-12-02 14:38
好东西,在学校数据结构学的不是很好,现在有点后悔啊
#29
ba_wang_mao2007-12-06 08:43
好东西,数据结构学的不是很好,现在有点后悔啊！
楼主好人呀
#30
Love嵌入式2008-05-10 19:24
缘分啊！！！
#31
chenc2008-05-19 19:51
顶    高手啊
#32
漫游者李李西2008-05-26 14:27
谢谢楼主。
#33
雪城白鸟2008-05-26 14:57
厉害
我刚刚学不久数据结构，很吃力，尤其到树和图那，很让我头疼
#34
2008-06-01 12:39
只有树的遍历
#include<iostream.h>
typedef struct Binnode
{
    char data;
    struct Binnode *l;
    struct Binnode *r;
}Binnode;
typedef Binnode* BinTree;
typedef struct stack
{
    BinTree s[100];
    int top;
}stack;//堆栈的定义
typedef struct queue
{
    BinTree data[10];
    int front;
    int rear;
}queue;
typedef int Status;
Status Initialize(stack &S)
{
    S.top=-1;
    return 1;
}//堆栈初始化
Status push(stack &S,BinTree T)
{
    if(T==NULL)return 0;
    S.top++;
    S.s[S.top]=T;
    return 1;
}//压栈,空指针不压栈
Status pop(stack &S,BinTree &T)
{
    if(S.top==-1)return 0;
    if(T==NULL)T=new Binnode;
    T=S.s[S.top];
    S.top--;
    return 1;
}//退栈
Status empty(stack S)
{
    if(S.top==-1)return 1;
    return 0;
}//栈是否为空
Status CreateTree(BinTree &T)
{
    char n;
    cin>>n;
    if(n=='#')
    {
        T=NULL;
        return 1;
    }
    T=new Binnode;
    T->data=n;
    CreateTree(T->l);
    CreateTree(T->r);
}//中序创建树
Status Pre_Travel(BinTree T)
{
    if(T==NULL)
    {
        return 1;
    }
    cout<<T->data<<" ";
    Pre_Travel(T->l);
    Pre_Travel(T->r);
}//前序遍历二叉树递归
Status Pre_Travel1(BinTree T,stack &S)
{
    while(T||!empty(S))
    {
        while(push(S,T))
        {
            cout<<T->data<<" ";
            T=T->l;
        }
        pop(S,T);
        T=T->r;
    }
    return 1;
}
Status Pre_Travel2(BinTree T,stack &S)
{
    while(T||!empty(S))
    {
        while(T)
        {
            push(S,T);
            cout<<T->data<<" ";
            T=T->l;
        }
        pop(S,T);
        T=T->r;
    }
    return 1;
}//非递归前序遍历二叉树
Status In_Travel(BinTree T)
{
    if(T==NULL)
    {
        return 1;
    }
    In_Travel(T->l);
    cout<<T->data<<" ";
    In_Travel(T->r);
}//中序遍历二叉树
Status In_Travel1(BinTree T,stack &S)
{
    while(T||!empty(S))
    {
        if(T)
        {
            push(S,T);
            T=T->l;
        }
        else
        {
            pop(S,T);
            cout<<T->data<<" ";
            T=T->r;
        }
    }
    return 1;
}//中序遍历二叉树非递归
Status In_Travel2(BinTree T,stack &S)
{
    while(T||!empty(S))
    {
        while(T)
        {
            push(S,T);
            T=T->l;
        }
        pop(S,T);
        cout<<T->data<<" ";
        T=T->r;
    }
    return 1;
}
Status Pos_Travel(BinTree T)
{
    if(T==NULL)
    {
        return 1;
    }
    Pos_Travel(T->l);
    Pos_Travel(T->r);
    cout<<T->data<<" ";
}//后序遍历二叉树
Status Pos_Travel1(BinTree T,stack &S)
{
    BinTree node;
    while(T||!empty(S))
    {
        if(T)
        {
            push(S,T);
            T=T->l;
        }
        else
        {
            pop(S,T);
            if(T->r==NULL||T->r==node)
            {
                cout<<T->data<<" ";
                node=T;
                T=NULL;
            }
            else
            {
                push(S,T);
                T=T->r;
            }
        }
    }
    return 1;
}//非递归遍历二叉树
Status Layer_Travel(BinTree T)
{
    if(T==NULL)
    {
        return 1;
    }
    if(T->l)cout<<T->l->data<<" ";
    if(T->r)cout<<T->r->data<<" ";
    Layer_Travel(T->l);
    Layer_Travel(T->r);
}
Status Layer(BinTree T)
{
    cout<<T->data<<" ";
    cout<<endl;
    Layer_Travel(T);
    return 1;
}//层次遍历
void main()
{
    BinTree T;
    stack s;
    Initialize(s);
    cout<<"请按先序创建二叉树:";
    CreateTree(T);
    cout<<"中序遍历如下:"<<endl;
    In_Travel(T);
    cout<<endl;
    In_Travel1(T,s);
    cout<<endl;
    In_Travel2(T,s);
    cout<<endl;
    cout<<"先序遍历如下:"<<endl;
    Pre_Travel(T);
    cout<<endl;
    Pre_Travel1(T,s);
    cout<<endl;
    Pre_Travel2(T,s);
    cout<<endl;
    cout<<"后序遍历如下:"<<endl;
    Pos_Travel(T);
    cout<<endl;
    Pos_Travel1(T,s);
    cout<<endl;
    cout<<"层次遍历如下"<<endl;
    Layer(T);
    cout<<endl;
    return ;
}
#35
justtest2008-07-18 14:24
平衡二叉树实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>


typedef struct node
{
int data;
int blance;
struct node * left;
struct node * right;
}node_t, * node_tp;


static node_tp avl_tab_p = NULL;


void init_node(node_tp node, int data)
{
    if(node)
    {
        node->data = data;
        node->blance = 0;
        node->left = NULL;
        node->right = NULL;
    }
}


void free_tab_s(node_tp node)
{
    if(!node)
        return;
    free_tab_s(node->left);
    free_tab_s(node->right);
    printf("\nfree data=%d", node->data);
    free(node);
}

void free_tab(void)
{
    free_tab_s(avl_tab_p);
    avl_tab_p = NULL;
}


node_tp find_node(node_tp node, int data)
{
    if(!node)
        return node;
    else if(node->data > data)
        return find_node(node->left, data);
    else if(node->data < data)
        return find_node(node->right, data);
    else
        return node;    
}

int node_depth(node_tp node, int * blance)
{
    int l, r;
    if(!node)
        return 0;
    l = node_depth(node->left, blance);
    r = node_depth(node->right,blance);
    if(blance && (l - r > 1 || l - r < -1))
    {
        *blance = 0;
        printf("\ncha=%d, %d", l-r, node->data);
    }
    return 1 + ((l > r)? l:r);
}

int travesal_mid_s(node_tp node)
{
    int l, r;
    if(!node)
        return 0;
    l =  travesal_mid_s(node->left);
    printf(" %d(blance=%d depth=%d,) ", node->data, node->blance,node_depth(node,NULL));
    r = travesal_mid_s(node->right);
    return l + r + 1;
}

void travesal_mid(void)
{
    int blance = 1;
    int depth = node_depth(avl_tab_p, &blance);
    int count;    
    printf("\n---tree is:--------\n");
    count = travesal_mid_s(avl_tab_p);
    printf("\n-----count=%d----depth=%d----blance=%d-----------", count, depth, blance);
}

node_tp max_node(node_tp node)
{
    if(!node || !node->right)
        return node;
    return max_node(node->right);
}


node_tp left_rotate(node_tp node)
{
    node_tp p = NULL;
    if(node && node->right && node->right->right)
    {
        p  = node->right;
        node->right = p->left;
        p->left = node;
        
        if(p->blance == 0)
        {
            p->blance = -1;
            p->left->blance = 1;
        }
        else
        {
            p->blance = 0;
            p->left->blance = 0;
        }
    }
    return p;
}

node_tp right_rotate(node_tp node)
{
    node_tp p = NULL;
    if(node && node->left && node->left->left)
    {
        p = node->left;
        node->left = p->right;
        p->right = node;

                if(p->blance == 0)
                {
                        p->blance = 1;
                        p->right->blance = -1;
                }
                else
                {
                        p->blance = 0;
                        p->right->blance = 0;
                }

    }
    return p;
}

node_tp left_right_rotate(node_tp node)
{
    node_tp p = NULL;
    if(node && node->left && node->left->right)
    {
        p = node->left->right;
        node->left->right = p->left;
        p->left = node->left;

        node->left = p->right;
        p->right = node;
        
        switch(p->blance)
        {
            case -1:
                p->left->blance = p->blance = 0;
                p->right->blance = 1;
                break;
            case 0:
                p->left->blance = p->right->blance = p->blance = 0;
                break;
            case 1:
                p->left->blance = -1;
                p->blance = p->right->blance = 0;
                break;
            default:
                break;
        }        

    }
    return p;
}


node_tp right_left_rotate(node_tp node)
{
    node_tp p = NULL;
    if(node && node->right && node->right->left)
    {
        p = node->right->left;
        node->right->left = p->right;
        p->right = node->right;

        node->right = p->left;
        p->left = node;

        switch(p->blance)
        {
            case -1:
                p->left->blance = p->blance = 0;
                p->right->blance = 1;
                break;
            case 0:
                p->blance = p->left->blance = p->right->blance = 0;
                break;
            case 1:
                p->blance = p->right->blance = 0;
                p->left->blance = -1;
                break;
            default:
                break;
        }
    }
    return p;
}


int rotate_type(node_tp node)
{
    if(!node)
        return 0;
    if(node->left && node->blance == -2 && node->left->blance <= 0)
        return 1;
    else if(node->right && node->blance == 2 && node->right->blance >= 0)
        return -1;
    else if(node->left && node->left->right && node->blance == -2 && node->left->blance  == 1)
        return -2;
    else if(node->right && node->right->left && node->blance == 2 && node->right->blance == -1)
        return 2;
    return 0;
}


node_tp avl_rotate(node_tp node)
{
      switch(rotate_type(node))
      {
                  case -1:
                          node = left_rotate(node);
                          break;
                  case 1:
                          node = right_rotate(node);
                          break;
                  case -2:
                          node = left_right_rotate(node);
                          break;
                  case 2:
                          node = right_left_rotate(node);
                          break;
                  default:
                          node = NULL;
                          break;
      }
    return node;
}

int insert_node_s(node_tp father_p, node_tp node, int data)
{
    node_tp p;
    int flag;
    if(!father_p && !node)
    {
        p = (node_tp)malloc(sizeof(node_t));
                assert(p != NULL);
                init_node(p, data);
                avl_tab_p = p;
        return 0;
    }    
    if(!node)
        return 1;
    else if(node->data == data)
        return -1;
    else if(node->data > data)
        flag = insert_node_s(node, node->left, data);
    else
        flag = insert_node_s(node, node->right, data);

    if(flag <= 0)
        return flag;

    if(node->data > data && !node->left)
    {
        p = (node_tp)malloc(sizeof(node_t));
        assert(p != NULL);
        init_node(p, data);
        node->left = p;
    }
    else if(node->data < data && !node->right)
    {
                p = (node_tp)malloc(sizeof(node_t));
                assert(p != NULL);
                init_node(p, data);
                node->right = p;
    }
    
    if(node->data >  data)
        node->blance--;    
    else
        node->blance++;    

    if(node->blance == -2 || node->blance == 2)
    {
        if(avl_tab_p == node)
        {
             avl_tab_p = avl_rotate(node);
            node = avl_tab_p;
        }
        else
        {
                      node = avl_rotate(node);
            if(father_p->data > node->data)
                father_p->left = node;
            else
                father_p->right = node;
        }
    }

    if(node->blance == 0)
        return 0;        
    else
        return 1;
}

int insert_node(int data)
{
    return (!insert_node_s(avl_tab_p, avl_tab_p, data) ? 0: -1);
}

int del_node_s(node_tp father_p, node_tp node, int data, node_tp deleted_node)
{
    int flag;
    int old_blance;    
    if(!father_p && !node)
        return -1;
    else if(!node)
        return -1;
    else if(node->data > data)
        flag = del_node_s(node, node->left, data, deleted_node);
    else if(node->data < data)
        flag = del_node_s(node, node->right, data, deleted_node);
    else
    {
        if(father_p == node)
            avl_tab_p = NULL;
        else
        {
                    deleted_node->data = data;
                
            if(father_p->left == node)
            {
                if(node->left)
                    father_p->left = node->left;
                else
                    father_p->left = node->right;
            }
            else
                    {
                if(node->left)
                    father_p->right = node->left;
                else
                    father_p->right = node->right;
            }
        }
        printf("\nfree data=%d", node->data);
        free(node);
        if(!avl_tab_p)
            return 0;
        else
            return 1;
    }

    if(flag <= 0)
        return flag;

    old_blance = node->blance;
    if(node->data >= data)
        node->blance++;
    else
        node->blance--;

    if(node->blance == -2 || node->blance == 2)
    {
        if(avl_tab_p == node)
        {
            avl_tab_p = avl_rotate(node);
            node = avl_tab_p;
        }
        else
        {
                      node = avl_rotate(node);
            if(father_p->data > node->data)
                father_p->left = node;
            else
                father_p->right = node;
        }
    }
    if(old_blance == 0 || avl_tab_p == node)
        return 0;
    else
        return 1;
}

int del_node(int data)
{
    node_tp p, pre_p;
    p = find_node(avl_tab_p, data);    
    if(!p)
        return -1;
    printf("\nfind node=%d", p->data);
    pre_p =    max_node(p->left);
    if(!pre_p)
        pre_p = p;
    printf("\nfind pre node=%d", pre_p->data);
    
    return (!del_node_s(avl_tab_p, avl_tab_p,  pre_p->data, p)? 0: -1);
}

void input_data(void)
{
    char str[20];
    int data, ret;
    
        for(ret = 0; ret < 11; ret++)
            insert_node( ret);        
        travesal_mid();
    while(1)
    {
/*
        printf("\n\n\nenter data =");
        scanf("%s", str);
        if(strncmp(str, "ok", 2) == 0)
            break;
        ret = sscanf(str, "%d", &data);
        if(ret == 1)
        {
            travesal_mid();    
            ret = insert_node( data);
            if(ret != -1)
                printf("\n insert data=%d successful", data);
            
            travesal_mid();    
        }
        
*/
        printf("\n\n\ndel data =");
        scanf("%s", str);
        if(strncmp(str, "ok", 2) == 0)
            break;
        ret = sscanf(str, "%d", &data);
        if(ret == 1)
        {
            
            travesal_mid();    
            ret = del_node( data);
            if(ret != -1)
                printf("\n del data=%d successful", data);
            
            travesal_mid();    
            
        }
        

    }
    free_tab();


}



int main(int argc , char **argv)
{

    input_data();




    return 0;
}
#36
blueboy820062008-07-19 08:10
厉害。。。
#37
yw46332008-08-04 10:18
强！！！！
收藏了，还用考虑吗！！！！
#38
geninsf0092008-08-23 22:44
很好，很厉害，赞一个
#39
雄鹰2008-10-13 14:07
收藏了，非常感谢！
#40
雄鹰2008-10-13 14:09
我虽然还来的看，但我相信肯定非常好了，先收藏了，非常感谢！
#41
liyanhong2008-11-16 00:04
nuciewth  的代码 写的很条理

学习了
#42
bbsliyouyan2011-03-16 09:56
太强悍了，不过很有用，谢谢分享！
#43
niji2011-05-04 20:00
真好~
#44
阝子健2011-07-07 20:02
楼主太厉害了 辛苦啊
#45
麦迪依然2012-04-27 12:58
好霸气！收藏了！高手
#46
oulin2012-11-11 10:36
大厦，能否求教一个问题？
qq 1847228148
#47
weiziyi05302012-11-16 12:58
楼主 我也想求教    QQ251009358我照着我们书上的伪代码不能打出来啊  当然也可能是我编程太差了。。。。
#48
小淡定ZT2018-03-07 22:28
回复 5楼 nuciewth
如果根据输入的中序和后序序列无法构造二叉树，怎么让它在控制台上提示报错呢，求大神指点
#49
小淡定ZT2018-03-07 22:28
回复 5楼 nuciewth
如果根据输入的中序和后序序列无法构造二叉树，怎么让它在控制台上提示报错呢，求大神指点
1
©2025, BC-CN.NET
电脑版