早上起来后,决定把昨天的第二题解决一下,当时我都不知道完全二叉树的概念,所以今天就上度娘理解了一下完全二叉树的概念。
完全二叉树:假设一棵树有h层,则除了第h层外,其他层(1~h-1)的结点数都达到了最大,而第h层的所有节点都连续集中在左边。
引用度娘的图片
这道题目用到了完全二叉树的一个重要性质:
即当2*i<n,树的左孩子结点为tree[2*i];当2*i+1<n时,树的右孩子结点为tree[2*i+1]。
主要包括三个函数,一个是建立完全二叉树,一个实现左右孩子结点交换,一个实现先序输出。
代码如下:
1 #include"iostream" 2 using namespace std; 3 #include<string> 4 5 typedef struct BTLnode 6 { 7 char data; 8 struct BTLnode *lchild; 9 struct BTLnode *rchild; 10 }*BigTree; 11 12 bool creatree(BigTree &T,string s,int i) 13 { 14 if(i>s.size()) 15 return 0; 16 17 char c=s.at(i-1); 18 if(c==' ') 19 { 20 T=NULL; 21 } 22 else 23 { 24 T=(BigTree)malloc(sizeof(BTLnode)); 25 26 27 T->data=c; 28 T->lchild=NULL; 29 T->rchild=NULL; 30 31 creatree(T->lchild,s,2*i); 32 creatree(T->rchild,s,2*i+1); 33 34 } 35 36 } 37 void change(BigTree &T) 38 { 39 BigTree k; 40 k=(BigTree)malloc(sizeof(BTLnode)); 41 if(T) 42 { 43 k=T->lchild; 44 T->lchild=T->rchild; 45 T->rchild=k; 46 change(T->lchild); 47 change(T->rchild); 48 49 } 50 } 51 void preorder(BigTree &T) 52 { 53 if(T) 54 { 55 cout<<T->data<<" "<<endl; 56 preorder(T->lchild); 57 preorder(T->rchild); 58 } 59 } 60 61 int main() 62 { 63 BigTree T; 64 string s; 65 cout<<"请输入字符串:"<<endl; 66 cin>>s; 67 creatree(T,s,1); 68 change(T); 69 preorder(T); 70 71 return 0; 72 }
2013-01-20 今天是第二天,continue.....
这篇文是昨天写的,刚从日记里边转出来的 2013-01-21