知其然而不知其所以然: 2006年12月

個人檔案知其然而不知其所以然相片部落格清單更多

工具

說明

部落格

摘要

排列方式：

<< 第一頁 < 上一頁下一頁 > 最後一頁 >>

12月29日

引線二元樹：免堆疊/遞迴的前/中/後序走訪

暈倒，久久沒寫程式

一碰到資料結構又是我沒寫過的東西

對於後序....我還想真久...花了2小時才想到

以下是引線二元樹的Source code

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

typedef struct tree treenode;
typedef treenode *btree;
struct tree
{
　　int data;
　　char LT,RT;
　　btree left;
　　btree right;
};

void Insert_Data(btree * root,int key)
{
　　btree temp;
　　if(*root == NULL)
　　{
　　　　*root = (btree)malloc(sizeof(treenode));
　　　　(*root)->left = (*root)->right = NULL;
　　　　(*root)->RT = (*root)->LT = 0;
　　　　(*root)->data = key;
　　}
　　else
　　{
　　　　while((((*root)->data>=key)&&((*root)->LT==1))||(((*root)->data<key)&&((*root)->RT==1)))
　　　　{
　　　　　　if((*root)->data>=key)
　　　　　　{
　　　　　　　　root = &((*root)->left);
　　　　　　}
　　　　　　else
　　　　　　{
　　　　　　　　root = &((*root)->right);
　　　　　　}
　　　　}
　　　　temp = (btree)malloc(sizeof(treenode));
　　　　temp->data = key;
　　　　temp->LT = temp->RT = 0;
　　　　
　　　　if((*root)->data>=key)
　　　　{
　　　　　　temp->left = (*root)->left;
　　　　　　temp->right = (*root);
　　　　　　(*root)->left = temp;
　　　　　　(*root)->LT = 1;
　　　　}
　　　　else
　　　　{
　　　　　　temp->right = (*root)->right;
　　　　　　temp->left = (*root);
　　　　　　(*root)->right = temp;
　　　　　　(*root)->RT = 1;
　　　　}
　　}
}

void inorder(btree root)
{
　　while(root->left!=NULL)
　　{
　　　　root = root->left;
　　}
　　
　　while(root!=NULL)
　　{
　　　　printf("%d ",root->data);
　　　　
　　　　if(root->RT==1)
　　　　{
　　　　　　root = root->right;
　　　　　　while(root->LT==1)
　　　　　　{
　　　　　　　　root = root->left;
　　　　　　}
　　　　}
　　　　else
　　　　{
　　　　　　root = root->right;
　　　　}
　　}
}

void preorder(btree root)
{
　　while(root!=NULL)
　　{
　　　　printf("%d ",root->data);
　　　　if(root->LT==1)
　　　　{
　　　　　　root = root->left;
　　　　}
　　　　else if(root->RT==1)
　　　　{
　　　　　　root = root->right;
　　　　}
　　　　else
　　　　{
　　　　　　while(root!=NULL)
　　　　　　{
　　　　　　　　if(root->RT==0)
　　　　　　　　{
　　　　　　　　　　root = root->right;
　　　　　　　　}
　　　　　　　　else
　　　　　　　　{
　　　　　　　　　　root = root->right;
　　　　　　　　　　break;
　　　　　　　　}
　　　　　　}
　　　　}
　　}
}

void RevOrder(btree root,int parm)
{
　　if(root!=NULL)
　　{
　　　　if(parm==1)printf("%d ",root->data);
　　　　if(root->LT==1)
　　　　　　RevOrder(root->left,parm);
　　　　if(parm==2)printf("%d ",root->data);
　　　　if(root->RT==1)
　　　　　　RevOrder(root->right,parm);
　　　　if(parm==3)printf("%d ",root->data);
　　}
}

void postorder(btree root)
{
　　btree a,b;
　　while(root!=NULL)
　　{
　　　　while(root->LT==1 || root->RT==1)
　　　　{
　　　　　　root = (root->LT==1)?root->left:root->right;
　　　　}
　　　　
　　　　while(1)
　　　　{
　　　　　　printf("%d ",root->data);
　　　　　　
　　　　　　for(a=root;a->LT==1;a=a->left);
　　　　　　if(a->left!=NULL)
　　　　　　{
　　　　　　　　for(a = a->left;a->RT==1 && a->right!=root;a=a->right);
　　　　　　}
　　　　　　
　　　　　　for(b=root;b->RT==1;b=b->right);
　　　　　　if(b->right!=NULL)
　　　　　　{
　　　　　　　　for(b=b->right;b->LT==1 && b->left!=root;b=b->left);
　　　　　　}

　　　　　　if(a->right==root && a->RT==1)
　　　　　　{
　　　　　　　　root = a;
　　　　　　}
　　　　　　else if(b->left==root && b->LT==1)
　　　　　　{
　　　　　　　　if(b->RT==1)
　　　　　　　　{
　　　　　　　　　　root = b->right;
　　　　　　　　　　break;
　　　　　　　　}
　　　　　　　　else
　　　　　　　　{
　　　　　　　　　　root = b;
　　　　　　　　}
　　　　　　}
　　　　　　else
　　　　　　{
　　　　　　　　return;
　　　　　　}
　　　　}
　　}
}

int main()
{
　　srand(time(0));
　　btree root = NULL;
　　int i,temp;
　　
　　for(i=0;i<25;i++)
　　{
　　　　temp = rand()%100+1;
　　　　printf("%d ",temp);
　　　　Insert_Data(&root,temp);
　　}
　　printf("\n\n");
　　
　　RevOrder(root,2);
　　printf("\n");
　　inorder(root);
　　printf("\n\n");
　　
　　RevOrder(root,1);
　　printf("\n");
　　preorder(root);
　　printf("\n\n");
　　
　　RevOrder(root,3);
　　printf("\n");
　　postorder(root);
　　printf("\n\n");
　　
　　system("pause");
}

Code by Dev C++

下午 12:25 | 新增回應 | 讀取回應 (1) | 永久連結 | 發佈至您的部落格