myTree.h

#ifndefMYTREE_H_INCLUDED#defineMYTREE_H_INCLUDED/*二叉树性质：在二叉树上的第i（i>=1）层最多有2^(i-1)个节点。深度为k（K>=1）的二叉树最多有2^k-1个节点第i层节点的序号从2^(i-1)-1到2^i-1需要为i的节点的双亲的序号为(i+1)/2，它的左右孩子的序号为2i+1和2i+2*/#undefNULL#ifdef__cplusplus#defineNULL0#else#defineNULL((void*)0)#endiftypedefstructtag_myTree{intdata;structtag_myTree*pLeft;structtag_myTree*pRight;}myTree;//为树分配一个新节点myTree*getNewTreeNode();//初始化树的根节点voidinitBiTree(myTree*pTreeRoot);//销毁树----递归voiddestoryBiTree(myTree*pTreeRoot);//前序遍历树----递归voidpreOrderTraverse(myTree*pTreeRoot);//中序遍历----递归voidinOrderTraverse(myTree*pTreeRoot);//后序遍历----递归voidnexOrderTraverse(myTree*pTreeRoot);//获取树的深度---递归intgetTreeDepth(myTree*pTreeRoot);//构造一棵树voidcreateBiTree(myTree**pTreeRoot);#endif//MYTREE_H_INCLUDED

myTree.c

#include"myTree.h"voidinitBiTree(myTree*pTreeRoot){//如果根节点不为空说明树在使用中，需要先销毁if(NULL!=pTreeRoot){destoryBiTree(pTreeRoot);}pTreeRoot=NULL;}//思考如何使用循环销毁一棵树voiddestoryBiTree(myTree*pTreeRoot){if(NULL!=pTreeRoot){if(NULL!=pTreeRoot->pLeft){//递归，从最后一层向上销毁左孩子destoryBiTree(pTreeRoot->pLeft);}//能用elseif吗？？？if(NULL!=pTreeRoot->pRight){destoryBiTree(pTreeRoot->pRight);}free(pTreeRoot);pTreeRoot=NULL;}}voidpreOrderTraverse(myTree*pTreeRoot){if(NULL==pTreeRoot){return;}//访问根节点printf("%d\t",pTreeRoot->data);preOrderTraverse(pTreeRoot->pLeft);preOrderTraverse(pTreeRoot->pRight);return;}voidinOrderTraverse(myTree*pTreeRoot){if(NULL==pTreeRoot){return;}inOrderTraverse(pTreeRoot->pLeft);//访问根节点printf("%d\t",pTreeRoot->data);inOrderTraverse(pTreeRoot->pRight);return;}voidnexOrderTraverse(myTree*pTreeRoot){if(NULL==pTreeRoot){return;}nexOrderTraverse(pTreeRoot->pLeft);nexOrderTraverse(pTreeRoot->pRight);//访问根节点printf("%d\t",pTreeRoot->data);return;}intgetTreeDepth(myTree*pTreeRoot){intleftDepth;intrightDepth;if(NULL==pTreeRoot){return0;}if(NULL!=pTreeRoot->pLeft){leftDepth=getTreeDepth(pTreeRoot->pLeft);}else{leftDepth=0;}if(NULL!=pTreeRoot->pRight){rightDepth=getTreeDepth(pTreeRoot->pLeft);}else{rightDepth=0;}return((leftDepth>rightDepth)?leftDepth+1:rightDepth+1);}myTree*getNewTreeNode(){myTree*pNewNode=NULL;pNewNode=(myTree*)malloc(sizeof(myTree));if(NULL==pNewNode){returnNULL;}memset(pNewNode,0,sizeof(myTree));returnpNewNode;}voidcreateBiTree(myTree**pTreeRoot){intdata;myTree*pTmp=NULL;scanf("%d",&data);if(0!=data){pTmp=getNewTreeNode();if(NULL==pTmp){exit(0);}pTmp->data=data;*pTreeRoot=pTmp;createBiTree(&((*pTreeRoot)->pLeft));createBiTree(&((*pTreeRoot)->pRight));}}

main.c

#include<stdio.h>#include"myTree.h"intmain(){myTree*g_TreeRoot=NULL;createBiTree(&g_TreeRoot);printf("pre:\t");preOrderTraverse(g_TreeRoot);printf("\nin:\t");inOrderTraverse(g_TreeRoot);printf("\nnex:\t");nexOrderTraverse(g_TreeRoot);return0;}