先序和后序构造二叉树，后序和中序构造二叉树

红太狼 2022-09-21 00:29 120阅读 0赞

1.先序和后序构造二叉树

#include <stdio.h>
    
    typedef struct BiNode{
        int data;
        struct BiNode *lchild, *rchild;
    }BiTree;
    
    int g_index = 0;
    /*
    preOrder为左子树
    inOrder为右子树
    num为当前节点的左子树和右子树的总数目。
    */
    BiTree* create(int *preOrder, int *inOrder, int num)
    {
    	if(num == 0)
    		return NULL;
    
    	int i = 0,index; 
    	for(i = 0; i < num; i++){
    		if(preOrder[0] == inOrder[i]){
    			index = i;
    			break;
    		}
    	}
    	
    	BiTree *node = (BiTree*)malloc(sizeof(BiTree));
    	node->data = preOrder[0];	
    	int lnum = index;
    	int rnum = num-index-1;
    
    	if(!lnum)
    		node->lchild = NULL;
    	else{
    		node->lchild = create(&(preOrder[1]), &(inOrder[0]), lnum);
    	}
    
    	if(!rnum)
    		node->rchild = NULL;
    	else{
    		node->rchild = create(&preOrder[index+1], &(inOrder[index+1]), rnum);
    	}
    
    	return node;	
    }
    
    void preOrder_traverse(BiTree *tree)
    {
        if(tree != NULL){
            preOrder_traverse(tree->lchild);
            preOrder_traverse(tree->rchild);
            printf("data=%d\n",tree->data);
        }
    }
    
    void main(int argc, char **argv)
    {
        int pre[8]={1,2,4,7,3,5,6,8};
        int in[8]={4,7,2,1,5,3,8,6};
    
        BiTree *tree = create(&pre, &in, 8);
        preOrder_traverse(tree);
    }

2.后序和中序构造二叉树

#include <stdio.h>
    
    typedef struct BiNode{
    	int data;
    	struct BiNode *lchild, *rchild;
    }BiTree;
    
    
    BiTree* create(int *lastOrder, int *inOrder, int num)
    {
    	if(num == 0)
    		return NULL;
    
    	int i = 0,index;
    	for(i = 0; i < num; i++){
    //		if(inOrder[i] == lastOrder[num-1]){
    		//指向最后一个元素。
    		if(inOrder[i] == *lastOrder){
    			index = i;
    			break;
    		}
    	}
    
    	BiTree *node = (BiTree*)malloc(sizeof(BiTree));
    	node->data = *lastOrder;
    	int lnum = index;
    	int rnum = num - index -1; 	
    
    	printf("data=%d,l=%d,r=%d\n",node->data,lnum,rnum);
    	if(lnum == 0)
    		node->lchild = NULL;
    	else{
    		node->lchild = create(lastOrder-rnum-1, &(inOrder[0]), lnum);
    	}
    
    	if(rnum == 0)
    		node->rchild = NULL;
    	else{
    		node->rchild = create(--lastOrder, 
    								&(inOrder[index+1]), rnum);
    	}
    
    	return node;
    }
    
    void preOrder_traverse(BiTree *tree)
    {
    	if(tree != NULL){
    		printf("data=%d\n",tree->data);	
    		preOrder_traverse(tree->lchild);
    		preOrder_traverse(tree->rchild);
    	}
    }
    
    void main(int argc, char **argv)
    {
    //	int pre[8]={1,2,4,7,3,5,6,8};
    	int last[8]={7,4,2,5,8,6,3,1};
    	int in[8]={4,7,2,1,5,3,8,6};
    
    	BiTree *tree = create(&last[7], &in, 8);
    	preOrder_traverse(tree);
    }