二叉树---待完善
myTree.h
创新互联建站服务项目包括南沙网站建设、南沙网站制作、南沙网页制作以及南沙网络营销策划等。多年来,我们专注于互联网行业,利用自身积累的技术优势、行业经验、深度合作伙伴关系等,向广大中小型企业、政府机构等提供互联网行业的解决方案,南沙网站推广取得了明显的社会效益与经济效益。目前,我们服务的客户以成都为中心已经辐射到南沙省份的部分城市,未来相信会继续扩大服务区域并继续获得客户的支持与信任!
#ifndef MYTREE_H_INCLUDED #define MYTREE_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 */ #undef NULL #ifdef __cplusplus #define NULL 0 #else #define NULL ((void *)0) #endif typedef struct tag_myTree { int data; struct tag_myTree* pLeft; struct tag_myTree* pRight; }myTree; //为树分配一个新节点 myTree* getNewTreeNode(); //初始化树的根节点 void initBiTree(myTree *pTreeRoot); //销毁树----递归 void destoryBiTree(myTree *pTreeRoot); //前序遍历树----递归 void preOrderTraverse(myTree *pTreeRoot); //中序遍历----递归 void inOrderTraverse(myTree *pTreeRoot); //后序遍历----递归 void nexOrderTraverse(myTree *pTreeRoot); //获取树的深度---递归 int getTreeDepth(myTree* pTreeRoot); //构造一棵树 void createBiTree(myTree** pTreeRoot); #endif // MYTREE_H_INCLUDED
myTree.c
#include "myTree.h" void initBiTree(myTree *pTreeRoot) { //如果根节点不为空说明树在使用中,需要先销毁 if (NULL != pTreeRoot) { destoryBiTree(pTreeRoot); } pTreeRoot = NULL; } //思考如何使用循环销毁一棵树 void destoryBiTree(myTree *pTreeRoot) { if (NULL != pTreeRoot) { if (NULL != pTreeRoot->pLeft) { //递归,从最后一层向上销毁左孩子 destoryBiTree(pTreeRoot->pLeft); } //能用else if 吗??? if (NULL != pTreeRoot->pRight) { destoryBiTree(pTreeRoot->pRight); } free(pTreeRoot); pTreeRoot = NULL; } } void preOrderTraverse(myTree *pTreeRoot) { if (NULL == pTreeRoot) { return; } //访问根节点 printf("%d\t", pTreeRoot->data); preOrderTraverse(pTreeRoot->pLeft); preOrderTraverse(pTreeRoot->pRight); return; } void inOrderTraverse(myTree *pTreeRoot) { if (NULL == pTreeRoot) { return; } inOrderTraverse(pTreeRoot->pLeft); //访问根节点 printf("%d\t", pTreeRoot->data); inOrderTraverse(pTreeRoot->pRight); return; } void nexOrderTraverse(myTree *pTreeRoot) { if (NULL == pTreeRoot) { return; } nexOrderTraverse(pTreeRoot->pLeft); nexOrderTraverse(pTreeRoot->pRight); //访问根节点 printf("%d\t", pTreeRoot->data); return; } int getTreeDepth(myTree* pTreeRoot) { int leftDepth; int rightDepth; if (NULL == pTreeRoot) { return 0; } 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) { return NULL; } memset(pNewNode, 0, sizeof(myTree)); return pNewNode; } void createBiTree(myTree** pTreeRoot) { int data; 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#include "myTree.h" int main() { 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); return 0; }
网站题目:二叉树---待完善
文章地址:http://ybzwz.com/article/jpcdse.html