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

数据结构：完全二叉树（递归实现）

news 2025/7/18 4:26:01

如果完全二叉树的深度为h，那么除了第h层外，其他层的节点个数都是满的，第h层的节点都靠左排列。

完全二叉树的编号方法是从上到下，从左到右，根节点为1号节点，设完全二叉树的节点数为sum，某节点编号为i，

当2*i <= sum时，有左孩子，其编号为2*i，否则没有左孩子，本身为叶节点。

当2*i+1 <= sum时，有右孩子，其编号为2*i+1，否则没有右孩子。

tree.h

/*===============================================
*   文件名称：tree.h
*   创 建 者：cxy     
*   创建日期：2024年01月23日
*   描    述：
================================================*/
#ifndef _TREE_H
#define _TREE_H#include <stdio.h>
#include <stdlib.h>typedef struct node{int data;struct node *lchild;struct node *rchild;
}Tree,*Ptree;Ptree init(int i,int sum); //i为节点编号，sum为总数
int preorder(Ptree root);  //先序遍历
int inorder(Ptree root);   //中序遍历
int postorder(Ptree root); //后序遍历#endif

tree.c

/*===============================================
*   文件名称：tree.c
*   创 建 者：cxy     
*   创建日期：2024年01月23日
*   描    述：
================================================*/
#include "tree.h"Ptree init(int i,int sum)
{Ptree root = malloc(sizeof(Tree));root->data = i;if(2*i <= sum){root->lchild = init(2*i,sum);}else{root->lchild = NULL;}if(2*i+1 <= sum){root->rchild = init(2*i+1,sum);}else{root->rchild = NULL;}return root;
}int preorder(Ptree root)
{if(NULL == root)return 0;printf("%d ",root->data);preorder(root->lchild);preorder(root->rchild);return 0;
}int inorder(Ptree root)
{if(NULL == root)return 0;inorder(root->lchild);printf("%d ",root->data);inorder(root->rchild);return 0;
}int postorder(Ptree root)
{if(NULL == root)return 0;postorder(root->lchild);postorder(root->rchild);printf("%d ",root->data);return 0;
}

main.c

/*===============================================
*   文件名称：main.c
*   创 建 者：cxy     
*   创建日期：2024年01月23日
*   描    述：
================================================*/
#include "tree.h"int main(int argc, char *argv[])
{ Ptree root;root = init(1,9);printf("-----先序遍历-----\n");preorder(root);puts("");printf("-----中序遍历-----\n");inorder(root);puts("");printf("-----后序遍历-----\n");postorder(root);puts("");return 0;
}

结果