二叉树的简单实现

超强辅助 Bolt.diy ⼀步搞定创意建站

#ifndef BINARYTREE_H_INCLUDED
#define BINARYTREE_H_INCLUDED
typedef char Type;
typedef struct TreeNode{
    Type data;
    struct TreeNode* left,*right;
} Node,* NodePoint,** pNodePoint;
typedef struct {
    Node* root;
} BTR,* BTRPoint;

#endif // BINARYTREE_H_INCLUDED
#include "BinaryTree.h"
#include <stdio.h>
#include <stddef.h>
#include <string.h>
_Bool strLTrim(Type*);
void createFromArr(BTRPoint);
_Bool ReadFileToArray(char*,Type (*)[3],unsigned*);
_Bool CreateBTRFromFile(pNodePoint,Type (*)[3],unsigned,unsigned*);
void ReadFromFile(BTRPoint);

void ReadFromFile(BTRPoint p){
    printf("请输入文件地址：");
    char fileAddr[100];
    scanf("%s",fileAddr);
    Type str[100][3];
    unsigned len=0;
    unsigned currlen=0;
    if(!ReadFileToArray(fileAddr,str,len))
        printf("错误：文件读取失败！\n");
    if(!CreateBTRFromFile(p->root,str,len,currlen))
        printf("错误：节点创建失败！\n");
}
_Bool ReadFileToArray(char* fileName,Type (*strLine)[3],unsigned* nArrLen){
	FILE* pFile;
	char str[1000];
	pFile=fopen(fileName,"r");
	if(pFile==0){
		printf("错误：文件%s打开失败!\n",fileName);
		return 0;
	}
	while(fgets(str,1000,pFile)!=0){
		if(strLTrim(str)==0)
            break;
	}
	if(strstr(str,"BinaryTree")==0){
		printf("错误：打开的文件格式错误！\n");
		fclose(pFile);
		return 0;
	}
	*nArrLen=0;     //initial line number to be 0
	while(fgets(str,1000,pFile)!=0){
		if(strLTrim(str))
            continue;
		char* token=strtok(str," ");
		if(token==0){
			printf("错误：读取二叉树结点数据失败！\n");
			fclose(pFile);
			return 0;
		}
		strLine[*nArrLen][0]=*token;
		token = strtok( 0, " ");
		if(token==0){
			printf("错误：读取二叉树结点数据失败！\n");
			fclose(pFile);
			return 0;
		}
		strLine[*nArrLen][1]=*token;
		token = strtok( 0, " ");
		if(token==0){
			printf("错误：读取二叉树结点数据失败！\n");
			fclose(pFile);
			return 0;
		}
		strLine[*nArrLen][2]=*token;
		++(*nArrLen);
	}
	fclose(pFile);
	return 1;
}
_Bool CreateBTRFromFile(pNodePoint pBT,Type (*strLine)[3],unsigned nLen,unsigned* nRow){
	//nLen--数组长度，即：节点个数
	//nRow--数组当前行号
	if((*nRow>=nLen) || (nLen==0))
		return 0;  //数据已经处理完毕，或者没有数据，退出
	//根据数组数据递归创建子树
	*pBT=malloc(sizeof(Node));
	(*pBT)->data=strLine[*nRow][0];
	(*pBT)->left=(*pBT)->right=0;
	int nRowNext=*nRow;  //保留本次递归的行号
	if(strLine[nRowNext][1]=='1'){  //当前结点有左子树，递归创建左子树，读下一行数据
		++(*nRow);
		CreateBTRFromFile((*pBT)->left, strLine,nLen,nRow);
	}
	if(strLine[nRowNext][2]=='1'){  //当前结点有右子树，递归创建右子树，读下一行数组
		++(*nRow);
		CreateBTRFromFile((*pBT)->right, strLine,nLen,nRow);
	}
	return 1;
}
_Bool strLTrim(Type* str){
    unsigned i,j=0;
	unsigned n=strlen(str)+1;
	for(i=0;i<n||str[i]!=' ';++i){}//find the first space from left
	while(str[j++]=str[i++]){}//replace the space with the letters
	char* strTemp[10];
	if (str[0]=='\n')
        return 1;//skip the empty line
    strncpy(strTemp,str,2);//detect if there are double slash
    if(strstr(strTemp,"//")!=0)
        return 1;//detect comment line
    return 0;
}
//////////////////////////////////////////////
void createNode(pNodePoint p,Type* parr,unsigned len,unsigned currLen){
    if(currLen>len)
        return;
    *p=malloc(sizeof(Node));
	(*p)->data=parr[currLen-1];
	(*p)->left=(*p)->right=0;
    createNode(&(*p)->left,parr,len,currLen*2);
    createNode(&(*p)->right,parr,len,currLen*2+1);
}
void createFromArr(BTRPoint p){
    Type* arr[100];
    printf("请输入数组：");
    scanf("%s",arr);
    unsigned len=strlen(arr);
    createNode(&p->root,arr,len,1);
}
//////////////////////////////////////////////
void destoryNode(NodePoint p){
    if(p==0)    return;
    destory(p->left);
    destory(p->right);
    free(p);
}
void destory(BTRPoint tree){
    destoryNode(tree->root);
}
///////////////////////////////////////////////
void exchange(NodePoint p){
    if(p==0)    return;
    NodePoint temp;
    temp=p->left;
    p->left=p->right;
    p->right=temp;
    exchange(p->left);
    exchange(p->right);
}
void exchangeChild(BTRPoint tree){
    exchange(tree->root);
}
//////////////////////////////////////////////
//TODO:accomplish the type identity
void print(NodePoint p){
    size_t size=sizeof(Type);
    //to deal with different king of types' output
    switch(size){
    case 1:
        printf("%c ",p->data);
        break;
    case 4:
        printf("%d ",p->data);
        break;
    default:
        printf("%s ",p->data);
    }
}
void preOrderTravel(NodePoint p){
    if(p==0)    return;
    print(p);
    preOrderTravel(p->left);
    preOrderTravel(p->right);
}
void preOrder(BTRPoint tree){
    preOrderTravel(tree->root);
    printf("\n");
}
void inOrderTravel(NodePoint p){
    if(p==0)    return;
    inOrderTravel(p->left);
    print(p);
    inOrderTravel(p->right);
}
void inOrder(BTRPoint p){
    inOrderTravel(p->root);
    printf("\n");
}
void postOrderTravel(NodePoint p){
    if(p==0)    return;
    postOrderTravel(p->left);
    postOrderTravel(p->right);
    print(p);
}
void postOrder(BTRPoint p){
    postOrderTravel(p->root);
    printf("\n");
}
///////////////////////////////////////////////
unsigned max(unsigned lhs,unsigned rhs){
    return lhs>rhs?lhs:rhs;
}
unsigned getDepthTravel(NodePoint p){
    if(p==0)    return 0;
    return max(getDepthTravel(p->left),getDepthTravel(p->right))+1;

}
void getDepth(BTRPoint tree){
    if(tree->root==0)
        return;
    else
        printf("树高度：%d\n",getDepthTravel(tree->root));
}
//////////////////////////////////////////////
unsigned getDegreeOfTwoTravel(NodePoint p){
    if(p->left==0&&p->right==0)    return 0;
    else if(p->left!=0&&p->right!=0)
        return getDegreeOfTwoTravel(p->left)+getDegreeOfTwoTravel(p->right)+1;
    else if(p->left!=0)
        return getDegreeOfTwoTravel(p->left);
    else if(p->right!=0)
        return getDegreeOfTwoTravel(p->right);
}
void getDegreeOfTwo(BTRPoint tree){
    if(tree->root==0)
        return;
    else
        printf("双子节点数：%d\n",getDegreeOfTwoTravel(tree->root));
}
////////////////////////////////////////////////
unsigned getNumOfLeafTravel(NodePoint p){
    if(p->left==0&&p->right==0)    return 1;
    else if(p->left!=0&&p->right!=0)
        return getNumOfLeafTravel(p->left)+getNumOfLeafTravel(p->right);
    else if(p->left!=0)
        return getNumOfLeafTravel(p->left);
    else if(p->right!=0)
        return getNumOfLeafTravel(p->right);
}
void getNumOfLeaf(BTRPoint tree){
    if(tree->root==0)
        //TODO: here need error status handle
        return;
    else
        printf("叶子数量：%d\n",getNumOfLeafTravel(tree->root));
}
////////////////////////////////////////////////
unsigned getNumOfNodeTravel(NodePoint p){
    if(p->left==0&&p->right==0)     return 1;
    else if(p->left!=0&&p->right!=0)
        return getNumOfNodeTravel(p->left)+getNumOfNodeTravel(p->right)+1;
    else if(p->left!=0)
        return getNumOfNodeTravel(p->left)+1;
    else if(p->right!=0)
        return getNumOfNodeTravel(p->right)+1;
}
void getNumOfNode(BTRPoint tree){
    if(tree->root==0)
        return;
    else
        printf("节点数量：%d\n",getNumOfNodeTravel(tree->root));
}
///////////////////////////////////////////////
//TODO: need accomplish string handle
void searchNodeTravel(NodePoint p,Type element,unsigned depth){
    if(p==0)    return 0;
    if(p->data==element)
        printf("The depth of the element is %d\n",depth);
    searchNodeTravel(p->left,element,depth+1);
    searchNodeTravel(p->right,element,depth+1);
}
void searchElement(BTRPoint tree){
    if(tree->root==0){
        printf("ERROR: empty Tree!\n");
    }
    else{
        Type element;
        scanf(" %c",&element);
        searchNodeTravel(tree->root,element,1);
    }
}
////////////////////////////////////////////////
void searchNodeDetailTravel(NodePoint p,NodePoint pre,Type element){
    if(p==0) return;
    if(p->data==element){
        if(pre!=0){
            printf("Parent: %c\n",pre->data);
            if(pre->left!=0&&pre->right!=0){
                if(pre->left==p)
                    printf("Right Brother: %c\n",pre->right->data);
                else
                    printf("Left Brother: %c\n",pre->left->data);
            }else
                printf("No Brother!\n");
        }else{
            printf("No Parent!\n");
            printf("No Brother!\n");
        }
        if(p->left==0&&p->right==0)
            printf("No Child!\n");
        else if(p->left!=0&&p->right!=0){
            printf("Left Child: %c\n",p->left->data);
            printf("Right Child: %c\n",p->right->data);
        }else if(p->left!=0){
            printf("Left Child: %c\n",p->left->data);
            printf("No Right Child!\n");
        }else{
            printf("Right Child: %c\n",p->right->right);
            printf("No Left Child!\n");
        }
    }
    searchNodeDetailTravel(p->left,p,element);
    searchNodeDetailTravel(p->right,p,element);
}
void searchNodeDetail(BTRPoint p){
    if(p->root==0)
        printf("ERROR: empty Tree!\n");
    else{
        Type element;
        scanf(" %c",&element);
        searchNodeDetailTravel(p->root,0,element);
    }
}
////////////////////////////////////////////////////////
void inOrderDetailTravel(NodePoint p,unsigned dep){
    if(p==0)    return;
    inOrderDetailTravel(p->left,dep+1);
    printf("%c<%d> ",p->data,dep);
    inOrderDetailTravel(p->right,dep+1);
}
void inOrderDetail(BTRPoint p){
    inOrderDetailTravel(p->root,1);
}