当前位置：首页 > article >正文

二叉树的实现

article 2025/1/5 6:44:30

树是一种 非线性 的数据结构，它是由 n （ n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。树形结构中，子树之间不能有交集，否则就不是树形结构。孩子兄弟表示法表示。

一棵二叉树是结点的一个有限集合，该集合 :

1. 或者为空

2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

从上图可以看出：

满二叉树 ：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K ，且结点总数是，则它就是满二叉树。

2. 完全二叉树 ：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

二叉树的遍历： 前序、中序以及后序遍历

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include "Queue.h"

typedef char BTDataType;
typedef struct BinaryTreeNode
{
   BTDataType _data;
   struct BinaryTreeNode* _left;
   struct BinaryTreeNode* _right;
} BTNode;

void PrevOrder(BTNode* root)
{
   if (root == NULL)
   {
       printf("NULL ");
       return;
   }
   printf("%c ", root->_data);
   PrevOrder(root->_left);
   PrevOrder(root->_right);
}

void InOrder(BTNode* root)
{
   if (root == NULL)
   {
       printf("NULL ");
       return;
   }
   InOrder(root->_left);
   printf("%c ", root->_data);
   InOrder(root->_right);
}

void PostOrder(BTNode* root)
{
   if (root == NULL)
   {
       printf("NULL ");
       return;
   }
   PostOrder(root->_left);
   PostOrder(root->_right);
   printf("%c ", root->_data);
}

BTNode* CreateNode(BTDataType x)
{
   BTNode* node = (BTNode*)malloc(sizeof(BTNode));
   if (node == NULL)
   {
       printf("申请内存失败\n");
       exit(-1);
   }
   node->_data = x;
   node->_left = NULL;
   node->_right = NULL;
   return node;
}

//求二叉树有多少个结点
//int TreeSize(BTNode* root)
//{
//   if (root == NULL)
//   {
//       return 0;
//   }
//   static int size = 0;
//   size++;
//   TreeSize(root->_left);
//   TreeSize(root->_right);
//   return size;
//}

//void TreeSize(BTNode* root, int* psize)
//{
//   if (root == NULL)
//   {
//       return 0;
//   }
//   (*psize)++;
//   TreeSize(root->_left,psize);
//   TreeSize(root->_right,psize);
//}

int TreeSize(BTNode* root)
{
   if (root == NULL)
   {
       return 0;
   }
   return 1 + TreeSize(root->_left) + TreeSize(root->_right);
}

int TreeLeafSize(BTNode* root)
{
   if (root == NULL)
   {
       return 0;
   }
   else if (root->_left == NULL && root->_right == NULL)
       return 1;
   return TreeLeafSize(root->_left) + TreeLeafSize(root->_right);
}

//二叉树k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
return 0;

if (k == 1)
return 1;

return BinaryTreeLevelKSize(root->_left, k - 1)
+ BinaryTreeLevelKSize(root->_right, k - 1);
}

//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, int x)
{
if (root == NULL)
return NULL;

if (root->_data == x)
return root;

   BTNode* node = BinaryTreeFind(root->_left, x);
   if (node->_data == x)
       return node;

   node = BinaryTreeFind(root->_right, x);
   if (node->_data == x)
       return node;

return NULL;
}

//二叉树的层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
   Queue q;
   QueueInit(&q);
   if (root == NULL)
       return;
   QueuePush(&q, root);

   while (!QueueEmpty(&q))
   {
       BTNode* front = QueueFront(&q);
       QueuePop(&q);

printf("%c ", front->_data);

       if (front->_left)
       {
           QueuePush(&q, front->_left);
       }

       if (front->_right)
       {
           QueuePush(&q, front->_right);
       }
   }
   printf("\n");
}

//判断二叉树是否是完全二叉树,使用队列来实现
//是返回1，不是返回0
int BinaryTreeComplete(BTNode* root)
{
   Queue q;
   QueueInit(&q);
   if (root == NULL)
       return 1;

   QueuePush(&q, root);
   while (!QueueEmpty(&q))
   {
       BTNode* front = QueueFront(&q);
       QueuePop(&q);

       if (front == NULL)
       {
           break;
       }

       QueuePush(&q, front->_left);
       QueuePush(&q, front->_right);
   }

   while (!QueueEmpty(&q))
   {
       BTNode* front = QueueFront(&q);
       QueuePop(&q);

       if (front)
       {
           QueueDestory(&q);
           return 0;
       }
   }
   return 1;
}

void DestoryTree(BTNode* root)
{
if (root == NULL)
return;

   //后序销毁
   DestoryTree(root->_left);
   DestoryTree(root->_right);

free(root);
}

int main()
{
   BTNode* A = CreateNode('A');
   BTNode* B = CreateNode('B');
   BTNode* C = CreateNode('C');
   BTNode* D = CreateNode('D');
   BTNode* E = CreateNode('E');
   A->_left = B;
   A->_right = C;
   B->_left = D;
   B->_right = E;

   PrevOrder(A);
   printf("\n");
   InOrder(A);
   printf("\n");
   PostOrder(A);
   printf("\n");
   //printf("TreeSize=%d\n", TreeSize(A));
   //int sizea = 0;
   //TreeSize(A, &sizea);
   //printf("TreeSize=%d\n",sizea);
   printf("TreeSize=%d\n", TreeSize(A));
   printf("TreeSize=%d\n", TreeLeafSize(A));
   printf("BinaryTreeLevelKSize=%d\n", BinaryTreeLevelKSize(A,3));

   BinaryTreeLevelOrder(A);
   printf("BinaryTreeComplete:%d\n", BinaryTreeComplete(A));

   DestoryTree(A);
   return 0;
}