二叉树（纯代码）

tree.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int BTDatatype;
typedef struct BinaryTreeNode
{
BTDatatype data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;

//申请节点
BTNode* BuyNode(BTDatatype x);
//前序遍历打印
void PreOrder(BTNode* root);
//创造二叉树
BTNode* CreatTree();
//二叉树元素个数
int TreeSize(BTNode* root);
//二叉树的深度
int TreeHeight(BTNode*);
//求第k层节点个数
int TreeLevel(BTNode* root, int k);
//查找元素
BTNode* BinaryTreeFind(BTNode* root, BTDatatype x);

tree.c

#include "tree.h"
//前序打印
void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
//申请节点
BTNode* BuyNode(BTDatatype x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("malloc fail");
return NULL;
}
node->data = x;
node->left = NULL;
node->right = NULL;
return node;
}

BTNode* CreatTree()
{
BTNode* nodel1 = BuyNode(1);
BTNode* nodel2 = BuyNode(3);
BTNode* nodel3 = BuyNode(9);
BTNode* nodel4 = BuyNode(10);
BTNode* nodel5 = BuyNode(2);
BTNode* nodel6 = BuyNode(12);
BTNode* nodel7 = BuyNode(16);
BTNode* nodel8 = BuyNode(17);
nodel1->left = nodel2;
nodel1->right = nodel6;
nodel2->left = nodel3;
nodel2->right = nodel4;
nodel4->left = nodel5;
nodel6->right = nodel7;
nodel7->right = nodel8;
return nodel1;
}


//二叉树元素个数
int TreeSize(BTNode* root)
{
return root == NULL ? 0 :
TreeSize(root->left)
+ TreeSize(root->right)
+1;
}

//二叉树的深度
int TreeHeight(BTNode*root)
{
if (root == NULL)
return 0;
int LeftHeight = TreeHeight(root->left);
int RightHeight = TreeHeight(root->right);
return LeftHeight > RightHeight
? LeftHeight+1 : RightHeight+1;
}

//求第k层节点个数
int TreeLevel(BTNode* root, int k)
{
assert(k > 0);
if (root == NULL)
return 0;
if (k == 1)
return 1;
return TreeLevel(root->left, k - 1) 
+ TreeLevel(root->right, k - 1);
}
//查找元素
BTNode* BinaryTreeFind(BTNode* root, BTDatatype x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
BTNode* reft = BinaryTreeFind(root->left, x);
if (reft)
{
return reft;
}
BTNode* rreft = BinaryTreeFind(root->right, x);
if (rreft)
{
return rreft;
}
return NULL;
}

test.c

#include"tree.h"
void BTNodeTest()
{
BTNode* ret=CreatTree();
PreOrder(ret);
printf("\n%d\n", TreeSize(ret));
printf("%p\n",BinaryTreeFind(ret, 9));
printf("%d\n", TreeHeight(ret));
printf("%d\n", TreeLevel(ret,4));
}

int main(void)
{
BTNodeTest();
return 0;
}

原文地址：https://blog.csdn.net/Starry_tsx/article/details/142731595

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！