#include <iostream>#include <stack>using namespace std;struct Node{int data;Node* next;Node(int d = int()):data(d){}};class List{friend class T;public:List():first(NULL){}void Insert(int a[],int n){Node *p = NULL;for(int i=0;i<n;i++){Node *s = new Node(a[i]);if(first==NULL){first=s;p=s;}else{s->next = p->next;p->next = s;p = s;}}}void Printf(){Node* p = first;while(p!=NULL){cout<<p->data<<" ";p=p->next;}cout<<endl;}private:Node *first;};/////////////////////////////////struct tNode{int val;int bf;//平衡因子。tNode *left;tNode *right;tNode(int d = int()):val(d),left(NULL),right(NULL),bf(0){}};class T{public:T():root(NULL){}void Create(List &list){Node *p = list.first;tNode *q = NULL;while(p!=NULL){tNode *s = new tNode(p->data);if(root==NULL){root = s;q = s;}else{tNode* pr = NULL;stack<tNode*> st;while(q->right!=NULL){pr=q;st.push(pr);q=q->right;}s->right = q->right;q->right = s;int count = 0;while(st.empty()==false){tNode *tnode = st.top();st.pop();if(tnode->val>q->val)tnode->bf–;elsetnode->bf++;if(tnode->bf==0){break;}else if(tnode->bf==1){continue;}else{tNode* temp = NULL;int flags = 0;if(st.empty()==true)root=q;//判断是否是根节点旋转。else{temp = st.top();st.pop();if(temp->right==tnode)flags=1;elseflags=-1;}LR(tnode,q);//旋转。if(flags==1){temp->right=q;}else{temp->left=q;}break;}q=tnode;}}p=p->next;}}void LR(tNode* &t,tNode* &p){t->right = p->left;p->left = t;p->bf=0;t->bf=0;}void Printf(){Printf(root);}private:void Printf(tNode *t){if(t==NULL)return;else{Printf(t->left);cout<<t->val<<" ";Printf(t->right);}}private:tNode *root;};int main(){int a[] = {1,2,3,4,5,6,7,8,9};List list;list.Insert(a,sizeof(a)/sizeof(int));T t;t.Create(list);t.Printf();//二叉树中序打印。return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，别让别人徘徊的脚步踩碎你明天美好的梦想，
