入门选手建立二叉树

古城微笑少年丶 2022-05-19 04:56 181阅读 0赞

//建立一个二叉树  才能去吃饭
    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<queue>
    const int MAXN=50; 
    using namespace std; 
    class node{
    	private :
    		char  data; 
    		node* lchild;
    		node* rchild; 
    		static int m; 
    	public :
    		void createnode(node * &,char *);
    }; 
    
    void node::createnode(node *&b,char *a){//注意这里对函数命名空间的声明 
    	int top=-1,k,j=0;
    	char ch; 
    	ch=a[j]; 
    	node *s[MAXN],*p; 
    	while(ch!='\0'){
    		switch(ch){ 
    			case '(':
    				top++;
    				k=1;
    				s[top]=p;	
    				break; 
    			case ')':
    				top--; 
    				break; 
    			case ',':
    				k=2; 
    				break; 
    			default : 
    			if(b==NULL){
    			b=p; 
    			} else{ 
    			p=new node; //注意这里对p创建对象的操作； 
    				p->data=ch;
    				p->lchild=NULL;
    				p->rchild=NULL; 
    				switch (k){ 
    					case 1:
    						s[top]->lchild=p;
    						break;
    					case 2:
    						s[top]->rchild=p; 
    						} 
    				}
    			} 
    			j++;
    			ch=a[j];	
    	}
    }
    
    int main()
    {
    	node *b;
    	char a[]="A(B(D,E(H(J,K(L,M(,N))),)),C(F,G(,I)))" ; 
    	b->createnode(b,a); 
    	
    }

废话不多说，直接撸码，注释清晰，初学者务必手写一遍注释

下边是不放心自己能不能学会而自己动手的，初学者注意：大部分教材对二叉树有详细的解释，可是大部分人却看不懂，所以，这是一个只能意会不能言传的东西，多看代码，摸索精髓，over！

#include<iostream>
    #include<queue>
    #define maxsize 50
    using namespace std;
    class node{
    private:
    	char data;
    	node* lchild;
    	node* rchild;
    	static int i;
    	static int m;
    	public:
    	void createnode(node *&,char *);
    }; 
    int node::i=0;
    int node::m=0;
    /*懵逼之建立二叉树：
    	首先：要考虑初值条件，比如使top为-1使b为NULL 
    	其次：判断读入字符的处理方式：{
    		读入（使top（层深）+1，并且是s【top】指向上次建立的p，使k=1； 
    		读入）使top减一 ，
    		读入，使k=2 ，
    		读入字符，建立一个新的元素对象，并使该对象的左右孩子的指为NULL 
    					并且判断k，如果k为1，则s【top】左孩子为该新元素，否则右孩子是 
    	}
    */ 
    void node::createnode(node* &b,char* a){
    	node *st[maxsize],*p;//建立两个二叉树类型的指针， 
    	int top=-1,k,j=0;//赋初值，top为-1，这样才能在数组中从0开始 
    	char ch;		//从数组中读取字符 
    	b=NULL;			//使b指向NULL 
    	ch=a[j];	
    	while(ch!='\0')
    	{								
    		switch(ch)
    		{
    			
    		case '(':	// 层数加一 
    			top++;
    			st[top]=p;//上一次循环开辟的p为这一层的parent 
    			k=1;
    			break;
    		case ')':	//层数减一 
    			top--;
    			break;
    		case ',':	//左孩子，变为右孩子，k是一个标记，k改变 
    			k=2;
    			break;
    		default:
    			p=new node;		//倘若遇到字符：为p开辟一个新对象 
    			p->data=ch;		//为p的data赋值为该字符 
    			m++;			//元素数量+1 
    			p->lchild=p->rchild=NULL;//在建立该节点的时候，使其左右节点均为NULL 
    			if(b==NULL){	//判断是不是根节点，如果是，为b赋值 
    				b=p;
    			}
    			else{
    				switch(k)	//判断新输入的值是左孩子还是右孩子	 
    				{
    				case 1:		//左孩子的话使新开辟的节点被上层左孩子指针指 
    					st[top]->lchild=p;
    					break;
    				case 2:			//右孩子的话使新开辟的节点被上层右孩子指针指 
    					st[top]->rchild=p;
    					break;
    				}
    			}
    		}
    		j++;
    		ch=a[j];
    	}
    }
     
     void main()
    {
    	node *b;
    	char a[]="A(B(D,E(H(J,K(L,M(,N))),)),C(F,G(,I)))";
    	b->createnode(b,a);
    	//A(B(D,E(H(J,K(L,M(,N))),)),C(F,G(,I)))  样本输入
    }