数据结构与算法学习--二叉树
可以看下以前对数的总结https://blog.****.net/sjin_1314/article/details/8507490
下面是二叉树的遍历,创建及销毁的函数实现,层次遍历依赖队列;队列实现可以去github上查看https://github.com/jin13417/algo/tree/master/c-cpp/23_binarytree/tree
/*************************************************************************
> File Name: binarytree.c
> Author: jinshaohui
> Mail: [email protected]
> Time: 18-11-12
> Desc:
************************************************************************/
#include<assert.h>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include"list_queue.h"
typedef struct _treenode
{
int data;
struct _treenode *lchild;
struct _treenode *rchild;
}Tnode,Tree;
void binarytree_create(Tree **Root)
{
int a = 0;
printf("\r\n输入节点数值((当输入为100时,当前节点创建完成))):");
scanf("%d",&a);
if (a == 100)
{
*Root = NULL;
}
else
{
*Root = (Tnode *)malloc(sizeof(Tnode));
if (*Root == NULL)
{
return;
}
(*Root)->data = a;
printf("\r\n create %d 的左孩子:",a);
binarytree_create(&((*Root)->lchild));
printf("\r\n create %d 的右孩子:",a);
binarytree_create(&((*Root)->rchild));
}
return ;
}
void binarytree_destory(Tree *root)
{
if (root == NULL)
{
return;
}
binarytree_destory(root->lchild);
binarytree_destory(root->rchild);
free(root);
}
/*先序遍历:根结点--》左子树---》右子树*/
void binarytree_preorder(Tree *root)
{
if (root == NULL)
{
return;
}
printf(" %d ",root->data);
binarytree_preorder(root->lchild);
binarytree_preorder(root->rchild);
return;
}
/*中序遍历:左子树--》跟节点---》右子树*/
void binarytree_inorder(Tree *root)
{
if (root == NULL)
{
return;
}
binarytree_inorder(root->lchild);
printf(" %d ",root->data);
binarytree_inorder(root->rchild);
return;
}
/*后序遍历:左子树---》右子树-》根节点*/
void binarytree_postorder(Tree *root)
{
if (root == NULL)
{
return;
}
binarytree_postorder(root->lchild);
binarytree_postorder(root->rchild);
printf(" %d ",root->data);
return;
}
void binarytree_levelorder(Tree * root)
{
list_queue *queue = NULL;
Tnode * node = NULL;
if(root == NULL)
{
return;
}
queue = list_queue_create();
/*根节点先入队*/
list_queue_enqueue(queue,(void *)root);
while(!list_queue_is_empty(queue))
{
list_queue_dequeue(queue,(void *)&node);
printf(" %d ",node->data);
if(node->lchild != NULL)
{
list_queue_enqueue(queue,(void *)node->lchild);
}
if(node->rchild != NULL)
{
list_queue_enqueue(queue,(void *)node->rchild);
}
}
free(queue);
}
/*打印叶子节点*/
void binarytree_printfleaf(Tree *root)
{
if (root == NULL)
{
return;
}
if ((root->lchild == NULL) && (root->rchild == NULL))
{
printf(" %d ",root->data);
}
else
{
binarytree_printfleaf(root->lchild);
binarytree_printfleaf(root->rchild);
}
}
/*打印叶子的个数*/
int binarytree_getleafnum(Tree*root)
{
if (root == NULL)
{
return 0;
}
if ((root->lchild == NULL) && (root->rchild == NULL))
{
return 1;
}
return binarytree_getleafnum(root->lchild) + binarytree_getleafnum(root->rchild);
}
/*打印数的高度*/
int binarytree_gethigh(Tree *root)
{
int lhigh = 0;
int rhigh = 0;
if (root == NULL)
{
return 0;
}
lhigh = binarytree_gethigh(root->lchild);
rhigh = binarytree_gethigh(root->rchild);
return ((lhigh > rhigh)?(lhigh + 1):(rhigh + 1));
}
int main()
{
Tree *root = NULL;
setenv("MALLOC_TRACE","1.txt",1);
mtrace();
printf("\r\n创建二叉树:");
binarytree_create(&root);
printf("\r\n先序遍历二叉树:");
binarytree_preorder(root);
printf("\r\n中序遍历二叉树:");
binarytree_inorder(root);
printf("\r\n后序遍历二叉树:");
binarytree_postorder(root);
printf("\r\n层次遍历二叉树:");
binarytree_levelorder(root);
printf("\r\n打印二叉树叶子节点:");
binarytree_printfleaf(root);
printf("\r\n打印二叉树叶子节点个数:%d",binarytree_getleafnum(root));
printf("\r\n打印二叉树高度:%d",binarytree_gethigh(root));
binarytree_destory(root);
muntrace();
return 0;
}
思考:什么样的二叉树适合使用数组来存储
完全二叉树,堆排序就是一种完全二叉树使用数组来处理的。