赞
踩
- #include<stdio.h>
- #include<stdlib.h>
- #include<stdbool.h>
- #define QueueSize 200
- typedef char DataType;
- typedef struct TNode
- {
- DataType data;
- struct TNode* lchild;
- struct TNode* rchild;
-
- }BiTree;
-
- BiTree* Creat_Tree(); // 创建树
- DataType Get_Root(BiTree * root); // 返回根结点
- int Depth_BiTree(BiTree * root); // 树深度
- int Count_BiTree(BiTree * root); // 树结点数
- int LeafCount_BiTree(BiTree * root); // 树叶子结点数
- void PreOrder_Traverse(BiTree * root); // 前序遍历
- void InOrder_Traverse(BiTree * root); // 中序遍历
- void PostOrder_Traverse(BiTree * root); // 后序遍历
- void LevelOrder_Traverse(BiTree * root); // 层序遍历
- bool Destroy_Tree(BiTree * root); // 销毁树
-
- int main()
- {
- BiTree * root = Creat_Tree();
-
- printf("根结点:%c\n",Get_Root(root));
- printf("树深度:%d\n",Depth_BiTree(root));
- printf("树结点数:%d\n",Count_BiTree(root));
- printf("树叶子结点数:%d\n",LeafCount_BiTree(root));
-
- printf("先序遍历:");
- PreOrder_Traverse(root);
- printf("\n");
-
- printf("中序遍历:");
- InOrder_Traverse(root);
- printf("\n");
-
- printf("后序遍历:");
- PostOrder_Traverse(root);
- printf("\n");
-
- printf("层序遍历:");
- LevelOrder_Traverse(root);
- printf("\n");
-
- if(Destroy_Tree(root))
- printf("销毁成功!\n");
- else
- printf("销毁失败!\n");
-
- return 0;
- }
-
- BiTree* Creat_Tree()
- {
- // 创建结点
- BiTree * pA = (BiTree*)malloc(sizeof(BiTree));
- BiTree * pB = (BiTree*)malloc(sizeof(BiTree));
- BiTree * pC = (BiTree*)malloc(sizeof(BiTree));
- BiTree * pD = (BiTree*)malloc(sizeof(BiTree));
- BiTree * pE = (BiTree*)malloc(sizeof(BiTree));
-
- // 给结点赋值
- pA->data = 'A';
- pB->data = 'B';
- pC->data = 'C';
- pD->data = 'D';
- pE->data = 'E';
-
- // 构建左右子树
- pA->lchild = pB;
- pA->rchild = pC;
-
- pB->lchild = pD;
- pB->rchild = NULL;
-
- pC->lchild = NULL;
- pC->rchild = pE;
-
- pD->lchild = NULL;
- pD->rchild = NULL;
-
- pE->lchild = NULL;
- pE->rchild = NULL;
-
- return pA; // 返回根结点的地址
- }
-
- DataType Get_Root(BiTree * root)
- {
- return root->data;
- }
-
- int Depth_BiTree(BiTree * root)
- {
- if(!root)
- return 0;
-
- return Depth_BiTree(root->lchild) > Depth_BiTree(root->rchild) ? Depth_BiTree(root->lchild)+1 : Depth_BiTree(root->rchild)+1;
- // 深度:最大层数 + 1
- }
-
- int Count_BiTree(BiTree * root)
- {
- if(!root)
- return 0;
-
- return Count_BiTree(root->lchild) + Count_BiTree(root->rchild) + 1;// 树结点数:左子树结点 + 右子树结点+ 根结点
- }
-
- int LeafCount_BiTree(BiTree * root)
- {
- if(!root)
- return 0;
-
- if(!root->lchild && !root->rchild) // 左、右指针域均为空,为叶子结点
- return 1;
- else
- return LeafCount_BiTree(root->lchild) + LeafCount_BiTree(root->rchild); // 递归遍历左、右子树叶子结点
- }
-
- /*
- * 伪算法:
- * 先访问根节点
- * 再先序访问左子树
- * 再线序访问右子树
- */
- void PreOrder_Traverse(BiTree * root)
- {
- if(!root)
- return;
- else
- {
- printf("%2c", root->data);
- PreOrder_Traverse(root->lchild);
- PreOrder_Traverse(root->rchild);
- }
- }
-
- void InOrder_Traverse(BiTree * root)
- {
- if(!root)
- return;
- else
- {
- InOrder_Traverse(root->lchild);
- printf("%2c", root->data);
- InOrder_Traverse(root->rchild);
- }
- }
-
- void PostOrder_Traverse(BiTree * root)
- {
- if(!root)
- return;
- else
- {
- PostOrder_Traverse(root->lchild);
- PostOrder_Traverse(root->rchild);
- printf("%2c", root->data);
- }
-
- }
-
- void LevelOrder_Traverse(BiTree * root)
- {
- // 建一个队列并初始化队头、队尾指针
- BiTree* Queue[QueueSize];
- int front = 0;
- int rear = 0;
-
- // 如果根结点不为空,则将根结点入队
- if(root!=NULL)
- Queue[rear++] = root;
-
- while(front!=rear) // 队列不为空
- {
- BiTree * ch = Queue[front++];
- printf("%2c", ch->data);
-
- // 将原结点的左、右子树结点入队
- if(ch->lchild!=NULL)
- Queue[rear++] = ch->lchild;
-
- if(ch->rchild!=NULL)
- Queue[rear++] = ch->rchild;
- }
- }
-
- bool Destroy_Tree(BiTree * root)
- {
- if(!root)
- return false;
-
- Destroy_Tree(root->lchild); // 先销毁左子树
- Destroy_Tree(root->rchild); // 再销毁右子树
- free(root); // 释放根结点
- root = NULL; // 防止产生野指针
- return true;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。