ツリー関連アルゴリズム
- #ifndef _TREE_H
- #define _TREE_H
- #define MAXSIZE 10
- #define MaxSize 10
- #define M 10
- //
-
- typedef int ElemType;
- typedef struct
- {
- ElemType data;
- int pos;
- }STree[MaxSize];
-
- //
-
- typedef struct tnode
- {
- ElemType data;
- struct tnode *child[M]; //M ， ，
- }CTree;
-
-
- //
- typedef struct cbnode
- {
- ElemType data;
- struct cbnode *child;
- struct cbnode *brother;
- }CBTree;
-
-
-
- typedef struct node
- {
- char data;
- struct node *left;
- struct node *right;
- }BTNode;
-
-
-
- #endif
-
-
- #include <stdio.h>
- #include "stdlib.h"
- #include "tree.h"
-
- // ，
-
-
-
- //
- void PreOrder(BTNode *b)
- {
- if(b != NULL)
- {
- printf("%d ",b->data);
- PreOrder(b->left);
- PreOrder(b->right);
- }
- }
-
- void PreOrder2(BTNode *b)
- {
- BTNode *st[MAXSIZE], *p;
- int top = -1;
- if(b != NULL)
- {
- top++;
- st[top]=b; //
- while(top>-1)
- {
- p=st[top];
- top--;
- printf("%d ",p->data); // ，
- if(p->right != NULL) // ，
- {
- top++;
- st[top]=p->right;
- }
- if(p->left != NULL) // ， ，
- {
- top++;
- st[top]=p->left;
- }
- printf("
");
- }
- }
- }
-
- //
- void InOrder(BTNode *b)
- {
- if(b != NULL)
- {
- InOrder(b->left);
- printf("%d ",b->data);
- InOrder(b->right);
- }
- }
-
- void InOrder2(BTNode *b)
- {
- BTNode *st[MAXSIZE], *p;
- int top=-1;
- if(b != NULL)
- {
- p=b;
- while(top>-1 || p!=NULL)
- {
- while(p != NULL) //
- {
- top++;
- st[top]=p->left;
- p=p->left;
- }
- if(top>-1)
- {
- p=st[top]; // ，
- top--;
- printf("%d ",p->data);
- p=p->right; //
- }
- }
- }
- }// ， ， ， ，
- // ， ， ，
- //
-
-
- //
-
- void PostOrder(BTNode *b)
- {
- if(b != NULL)
- {
- PostOrder(b->left);
- PostOrder(b->right);
- printf("%d ",b->data);
- }
- }
-
- void PostOrder2(BTNode *b)
- {
- BTNode *st[MAXSIZE], *p;
- int top=-1,flag=1;
- if(b!=NULL)
- {
- do
- {
- while(b!=NULL) // b
- {
- top++;
- st[top]=b;
- b=b->left;
- }
- p=NULL; //p
- flag=1;
- while(flag && top!=-1)
- {
- b=st[top]; //
- if(b->right == p) // ， *b
- {
-
- top--;
- printf("%d ",b->data);
- p=b; //p
- }else
- {
- b=b->right;
- flag=0;
- }
- }
-
- }while(top!=-1);
- }
- } // ，p ， p!=null ，
- //
-
-
- void CreateTree(BTNode * b, char *str)
- {
- BTNode *st[MAXSIZE], *p=NULL; // st ，
- int top=-1, k=1, j=0;
- char ch=str[j];
- b=NULL;
- while(ch != '\0')
- {
- switch(ch)
- {
- case '(' :
- top++; k=1; st[top]=p; break; // '(' , k=1
- case ')' :
- top--; break; //
- case ' ' :
- break;
- case ',' :
- k=2; break; // k=2
- default :
- p=(BTNode *)malloc(sizeof(BTNode));
- if(p == NULL) return ;
-
- p->data=ch;
- p->left=NULL;
- p->right=NULL;
-
- if(b == NULL) b=p;
- else
- switch(k)
- {
- case 1 :
- st[top]->left=p;break;
- case 2 :
- st[top]->right=p; break;
- }
- break; // ， (b) null, ，
- // ， p ‘（’‘）’ ， 。
-
- }
- ch=str[++j];
- }
- }
-
- //
- BTNode *FindNode(BTNode *root,char e)
- {
- BTNode *p;
- if(root == NULL) return NULL;
- else if(root->data == e) return root; //
- else
- {
- p = FindNode(root->left,e); // ， ，
- if(p == NULL) return FindNode(root->right,e); // ，
- else return p; //
- }
- }
- // b x
- void NodeLevel2(BTNode *b, char x, int &h, int ih)
- {
- if(b == NULL) h = 0;
- else if(b->data == x) h = ih;
- else
- {
- NodeLevel2(b->left,x,h,ih+1);
- if(h == 0)
- {
- NodeLevel2(b->right,x,h,ih+1);
- }
- }
- }
-
- // ， ， ， ， ，
-
-
-
-
- //
-
- int BTNodeDepth(BTNode *b)
- {
- int lDepth, rDepth;
- if(b == NULL) return 0;
- else
- {
- lDepth = BTNodeDepth(b->left);
- rDepth = BTNodeDepth(b->right);
- return (lDepth > rDepth) ? lDepth+1 : rDepth+1;
- }
- }
-
-
- //
-
- void DispBTNode (BTNode *b)
- {
- if(b != NULL)
- {
- printf("%c",b->data); //
- if(b->left != NULL || b->right != NULL)
- {
- if(b->left != NULL)
- {
- printf("("); // ， '('
- DispBTNode(b->left);
- }
- if(b->right != NULL) // ‘，’
- printf(",");
-
- DispBTNode(b->right);
- printf(")");
-
- }
- }
- }
-
-
- //
- void *CreateBT1(char *pre, char *in, int n)
- {
- BTNode *s;
- char *p;
- int k;
- if(n<0) return NULL;
- s=(BTNode *)malloc(sizeof(BTNode));
- s->data = *pre;
- for(p=in; p<in+n; p++)
- if(*pre == *p) break;
-
- k=p-in;
- s->left = CreateBT1(pre+1,in,k);
- s->right = CreateBT1(pre+k+1,p,n-k-1);
- return s;
- }
-
- // k
- char PreNode (BTNode *b, int k, int n)
- {
- char ch;
- if(b == NULL) return ' ';
- if(n == k) return b->data;
- ch = PreNode(b->left,k,n+1);
- if(ch != ' ' ) return ch;
- return PreNode(b->right,k,n+1);
- }
-
- char PreNode2(BTNode *b, int k)
- {
- BTNode *st[MAXSIZE], *p;
- int top=-1, n=0;
- if(b != NULL)
- {
- top++;
- st[top]=b; //
- while(top > -1)
- {
- p=st[top];
- top--; //
- n++;
- if(n == k) printf("%c ,%d ",p->data,n); //
- if(p->right != NULL) //
- {
- top++;
- st[top]=p->right;
- }
- if(p->left != NULL) //
- {
- top++;
- st[top]=p->left;
- }
- }
- printf("
");
- }
- return ' ';
- }
- // ， { ， ， ， }
-
-
-
- // k
- char InNode(BTNode *b, int k, int n, char ch)
- {
- if(b != NULL)
- {
- InNode(b->left ,k,n,ch);
- printf("%c %d ",b->data, n);
- if(n == k) ch=b->data;
- n++;
- InNode(b->right,k,n,ch);
- }
- }
-
-
- char InNode2(BTNode *b, int k)
- {
- BTNode *st[MAXSIZE], *p;
- int top=-1, n=0;
- if(b != NULL)
- {
- p=b;
- while(p != NULL || top > -1)
- {
- while(p != NULL) //
- {
- top++;
- st[top]=p;
- p=p->left;
- }
- if(top > -1) //
- {
- p=st[top];
- top--;
- n++; //
- if(n == k) return p->data; // n==k ，
- p=p->right; //
- }
- }
- printf("
");
- }
- return ' ';
- }
-
- // ， ， ，
-
- // k
- void PostNode(BTNode *b, int k, int n, char ch)
- {
-
- }
-
-
- void PostNode2(BTNode *b,int k)
- {
-
- }
-
-
-
- // ， ，
- // ，
-
-
-
- //
- void TravLevel(BTNode *b)
- {
- BTNode *st[MAXSIZE];
- int rear=0, front=0;
- if(b != NULL)
- {
- printf("%c ",b->data);
- rear ++;
- st[rear]=b; //
-
- while(rear != front) //
- {
- front = (front+1)%MAXSIZE;
- b = st[front]; // front ， ，
- if(b->left != NULL) // ， ，
- {
- printf("%c ",b->left->data);
- rear = (rear + 1)% MAXSIZE;
- st[rear]=b->left;
- }
- if(b->right != NULL) // ， ，
- {
- printf("%c ",b->right->data);
- rear = (rear +1)%MAXSIZE;
- st[rear] = b->right;
- }
- }
- printf("
");
- }
- }
- // ，
-
-
- //
-
- int digui(BTNode *st1[],int front1, int rear1, int max)
- {
- BTNode *st2[MAXSIZE], *temp;
- int front2 = 1, rear2 = 1;
-
- while(front1 <= rear1)
- {
- temp = st1[front1];
- if(temp->left != NULL)
- {
- st2[rear2] = temp->left;
- rear2++;
- }
- if(temp->right != NULL)
- {
- st2[rear2] = temp->right;
- rear2++;
- }
-
- front1++;
- }
- if(--rear2 > max)
- max = rear2;
- if(front2 == rear2 == 1) return max;
- digui(st2,1,rear2,max);
- }
-
- int TreeWeight(BTNode *b)
- {
- BTNode *st[MAXSIZE] ;
- st[1] = b ;
- return digui(st,1,1,1);
- }
-
- int BTWidth(BTNode *b)
- {
- struct
- {
- int lno; //
- BTNode *p;
- }qu[MAXSIZE];
-
-
- int front, rear;
- int lnum, max, i, n;
- front = rear = 0;
- if(b != NULL)
- {
- rear++;
- qu[rear].p = b;
- qu[rear].lno = 1; //
-
- while(rear != front)
- {
- front++;
- b = qu[front].p;
- lnum = qu[front].lno; // ，
- if(b->left != NULL)
- {
- rear ++;
- qu[rear].p = b->left;
- qu[rear].lno = lnum +1;
- }
- if(b->right != NULL)
- {
- rear ++;
- qu[rear].p = b->right;
- qu[rear].lno = lnum +1;
- }
- }
- printf(" ：
");
- for(i=0; i<rear; i++)
- printf(" %c ,%d
",qu[i].p->data, qu[i].lno);
-
- max = 0; lnum = 1; i = 1;
- while(i <= rear)
- {
- n = 0;
- while(i <= rear && qu[i].lno == lnum)
- {
- n++;
- i++;
- }
- lnum = qu[i].lno;
- if(n > max) max = n;
- }
- return max;
- }
- else return 0;
- }
-
-
- //
-
- // ， ， ， false
- //1 h
- //2 n
- //3 n [2 h-1 -1，2 h -1]
-
- int CompBTNode(BTNode *b)
- {
- if(b == NULL) return 0;
- if(b->left == NULL && b->right == NULL) return 1;
- if(b->left == NULL && b->right != NULL || b->left != NULL && b->right == NULL)
- return 0;
- return CompBTNode(b->left) && CompBTNode(b->right);
- }
-
- int CompBTNode2(BTNode *b)
- {
- BTNode *st[MAXSIZE], *p;
- int front=0,rear=0,flag=1;
- if(b != NULL)
- {
- rear++;
- st[rear]=b;
- while(front < rear)
- {
- front = front +1;
- p=st[front];
- if(p->left != NULL)
- {
- rear++;
- st[rear]=p->left;
- }
- if(p->right != NULL)
- {
- rear++;
- st[rear]=p->right;
- }
- if(p->left != NULL && p->right == NULL || p->left == NULL && p->right == NULL)
- break;
- }
- while(front < rear)
- {
- front = front+1;
- p=st[front];
- if(p->left != NULL || p->right !=NULL)
- { flag = 0; break;}
- else
- {
- rear++;
- st[rear]=p;
- }
- }
- return flag;
- }
- return 0;
- }
-
-
- //
- // ， ， ， ，
- void AllPath(BTNode *b)
- {
- struct snode
- {
- BTNode *node;
- int parent;
- }q[MAXSIZE];
- BTNode *tmp;
- int front =-1, rear =-1, index=0;
- if(b != NULL)
- {
- rear++;
- q[rear].node = b;
- q[rear].parent = -1;
-
- while(front < rear)
- {
- front ++;
- tmp = q[front].node;
- if(tmp->right == NULL && tmp->left == NULL) // ， parent
- {
- printf("%c ：
",tmp->data);
- index = front;
- while(q[index].parent >= -1)
- {
- index--;
- printf("%c -->",q[index].node->data);
- }
- }
- if(tmp->left != NULL) // ，
- {
- rear++;
- q[rear].node = tmp->left;
- q[rear].parent = front;
- }
- if(tmp->right != NULL) // ，
- {
- rear++;
- q[rear].node = tmp->right;
- q[rear].parent = front;
- }
- }
- }
-
- }
-
- //
-
- void AllPath2(BTNode *b, char path[], int pathlen)
- {
- int i;
- if(b != NULL)
- {
- if(b->left == NULL && b->right == NULL) //
- {
- for(i=pathlen-1; i>=0; i--)
- {
- printf("%c ",b->data);
- }
- }
- else
- {
- path[pathlen] = b;
- pathlen++; //
- AllPath2(b->left,path, pathlen);
- AllPath2(b->right,path,pathlen);
- pathlen--;
- }
- }
- } //
-
- //
- void LongPath(BTNode *b, char path[], int pathlen, char longPath[], int longPathlen)
- {
- int i;
- if(b == NULL)
- {
- if(pathlen > longPathlen ) // ，
- {
- for(i=pathlen-1; i>=0; i--)
- longPath[i] = path[i];
- longPathlen = pathlen;
- }
- }
- else
- {
- path[pathlen] = b->data; //
- pathlen++;
- LongPath(b->left, path, pathlen, longPath, longPathlen);
- LongPath(b->right, path, pathlen, longPath, longPathlen);
- pathlen--;
- }
- } //
-
-
- //
- // f(b) = 0 b=null ， f(b) = 1 b->left == NULL && b->right == NULL，
- int Nodes(BTNode *b)
- {
- int i, ii;
- if(b == NULL) return 0;
- else if(b->left == NULL && b->right == NULL) return 1;
- else
- {
- i = Nodes(b->left)
- ii = Nodes(b->right);
- return (i + ii +1);
- }
- }
-
- // null. null
-
- //
-
- int LeafNode(BTNode *b)
- {
- BTNode *st[MAXSIZE], *p;
- int num=0,front=0,rear=0;
- if(b != NULL)
- {
- rear = (rear + 1)%MAXSIZE;
- st[rear] = b;
- while(front < rear || rear +1 <= front)
- {
- front = (front + 1)% MAXSIZE;
- p=st[front];
- if(p->left == NULL && p->right == NULL)
- num++;
- else if(p->left != NULL)
- {
- rear = (rear + 1)%MAXSIZE;
- st[rear] = p->left;
- }else if(p->right != NULL)
- {
- rear = (rear + 1)%MAXSIZE;
- st[rear] = p->right;
- }
- }
- }
- }
-
- // ， ，
- // while(front < rear || rear +1 <= front)
-
- int LeafNode(BTNode *b)
- {
- int num1 =0, num2=0;
- if(b == NULL) return 0;
- else if(b->left == NULL && b->right == NULL) return 1;
- else
- {
- num1 = LeafNode(b->left);
- num2 = LeafNode(b->right);
- return num1+num2;
- }
- }
-
- // ， return num1 + num2; ，
- // ， ，
-
- //
- int DSonNode(BTNode *b)
- {
- int num1, num2,n=0; // n
- if(b == NULL) n = 0;
- else if(b->left == NULL || b->right == NULL) n = 0;
- else n++;
-
- num1 = DSonNode(b->left);
- num2 = DSonNode(b->right);
- return num1+num2+n;
- }
-
-
-
-
-
-
- //
- // ，
- void DeleteNodes(BTNode *b)
- {
- if(b != NULL)
- {
- DeleteNodes(b->left);
- DeleteNodes(b->right);
- free(b);
- }
- }
-
-
-
- //
- void Swap(BTNode *b)
- {
- BTNode *temp;
- if(b != NULL)
- {
- temp = (BTNode *) malloc(sizeof(BTNode));
- temp=b;
- temp->left->data = b->right->data;
- temp->right->data = b->left->data;
-
- Swap(b->left);
- Swap(b->right);
- }
- }
-
- void Swap(BTNode *b)
- {
- BTNode *t, *t1, *t2;
- if(b == NULL) t= NULL;
- else
- {
- t = (BTNode *)malloc(sizeof(BTNode));
- t->data = b->data;
- t1 = Swap(b->left);
- t2 = Swap(b->right);
- t->left = t2;
- t->right = t1;
- }
- return t;
- }