定义
- 树(Tree) 是n (n>0)个节点的有限集合T
- 特点:
- 有且仅有一个特定的称为根(Root) 的节点
- 其余的节点可以分为m(m>=0)个人互不相交的有限集合T1、T2、…Tm,其中每一个集合又是一颗树,并称为器根的子树
- 表示方法:树形标识法,目录表示法
- 节点的度数:一个节点的子树的个数称为节点的度数
- 树的度数:一棵树的度数是指该树当中节点的最大度数
- 树叶/终端节点:度数为零的节点称为树叶或终端节点
- 分支节点:度数不为零的节点
- 内部节点:除根节点外的分支节点称为内部节点
- 路径:一个节点系列k1,k2,…ki,ki+1,…kj,并满足ki是ki+1的父节点,就称为一条路径从k1到kj的路径
- 边数:路径的长度为j-1,称为路径的边数
- 路径当中前面的节点是后面的节点的祖先,后面的节点是前面节点的子孙
- 根节点的层数定义为一,节点的层数大于父节点的层数加一,树中节点层数最大值称为该树的高度或深度
- 有序树:树当中每个节点的各个子树的排列从左到右,不能交换,即兄弟之间是有序的,则该树称为有序树
- m(m>0)棵互不相交的树的集合称为森林
- 树去掉根节点就称为森林,森林加上一个新的根节点就称为一颗新树
- 树的逻辑结构:树当中的任何节点都有零个或多个的直接后继(子节点),但是至多只有一个直接前趋节点(父节点),根节点没有前趋节点,叶节点没有后继节点。
二叉树
- 二叉树 是n (n>0)个节点的有限集合
- 或者是空集(n = 0)
- 或者是由一个根节点以及两棵互不相交,分别称为右子树和左子树组成
- 注意需要严格的区分左孩子和右孩子,即使只有一个子节点也是严格区分左右
二叉树的性质
- 二叉树第i(i>=1)层上的节点最多为2(i-1)次方个
- 深度为k(k>=1)的二叉树最多有2(k-1)次方个节点,等比数列求和
- 满二叉树:深度为k(k>=1)时,有2(k-1)次方个节点
- 完全二叉树:只有最下面两层有度数小于2的节点,并且最下面一层的叶节点集中在最左边的若干位置上
-
具有n个节点的完全二叉树的深度为:(log2n)+1或者log2(n+1)
顺序存储结构
完全二叉树的编号方法是从上到下,从左到右,根节点为1号节点。设完全二叉树的节点树为n,某节点的编号为i,
- 当i>1(不是根节点)时,右父节点,其编号为i/2
- 当2i<=n时,有左孩子,其编号为2i,否则没有左孩子,本身就是叶节点
- 当2i+1<=n时,有右孩子,其编号为2i+1,否则没有右孩子,
- 当i为奇数而且不等于1时,有左兄弟,其编号为i-1,否则没有左兄弟
链式存储结构
- 先序遍历:根-左-右
- 中序遍历:左-根-右
- 后序遍历:左-右-根
main.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "bitree.h"
int test();
int main()
{
printf("Main start!\n");
test();
return 0;
}
int test()
{ printf("test start!\n");
bitree *r;
if((r = CreateTree()) == NULL){
return 0;
}
Preorder(r);
puts("");
Inorder(r);
puts("");
Postorder(r);
puts("");
Layerorder(r);
puts("");
return 0;
}
bitree.c
#include <stdio.h>
#include <stdlib.h>
// #include "bitree.h"
#include "linkqueue.h"
bitree * CreateTree(){
data_t ch;
bitree *r;
scanf("%c",&ch);
if(ch == '#'){
// printf("ch == '#'");
return NULL;
}
r = (bitree*)malloc(sizeof(bitree));
if(r == NULL){
printf("r malloc fail!\n");
return NULL;
}
r->data = ch;
r->lchild = CreateTree();
r->rchild = CreateTree();
return r;
}
int Preorder(bitree* r)
{
if(r == NULL){
return 0;
}
printf("%c",r->data);
Preorder(r->lchild);
Preorder(r->rchild);
return 0;
}
int Inorder(bitree* r)
{
if(r == NULL){
return 0;
}
Inorder(r->lchild);
printf("%c",r->data);
Inorder(r->rchild);
return 0;
}
int Postorder(bitree* r)
{
if(r == NULL){
return 0;
}
Postorder(r->lchild);
Postorder(r->rchild);
printf("%c",r->data);
return 0;
}
int Layerorder(bitree* r)
{
linkqueue *lq;
if((lq = queue_create()) == NULL){
printf("lq is NULL\n");
return -1;
}
if(r == NULL){
return 0;
}
printf("%c",r->data);
enqueue(lq,r);
while (!queue_empty(lq))
{
r = dequeue(lq);
if(r->lchild){
printf("%c",r->lchild->data);
enqueue(lq,r->lchild);
}
if(r->rchild){
printf("%c",r->rchild->data);
enqueue(lq,r->rchild);
}
}
return 0;
}
bitree.h
typedef char data_t;
typedef struct node_t
{
data_t data;
struct node_t *lchild,*rchild;
}bitree;
bitree * CreateTree();
int Preorder(bitree* r);
int Inorder(bitree* r);
int Postorder(bitree* r);
int Layerorder(bitree* r);
linkqueue.c
#include <stdio.h>
#include <stdlib.h>
#include "linkqueue.h"
linkqueue* queue_create()
{
linkqueue *lq = (linkqueue *)malloc(sizeof(linkqueue));
if(lq == NULL){
printf("malloc linkqueue fail\n");
return NULL;
}
lq->front = lq->rear = (linklist)malloc(sizeof(listnode));
if(lq->front == NULL){
printf("malloc listnode fail\n");
return NULL;
}
lq->front->data = 0;
lq->front->next = NULL;
return lq;
}
int enqueue(linkqueue *lq, datatype x){
if(lq == NULL){
printf("lq is NULL\n");
return -1;
}
linklist p= (linklist)malloc(sizeof(listnode));
if(p == NULL){
printf("malloc node fail\n");
return -1;
}
p->data = x;
p->next = NULL;
lq->rear->next = p;//连接
lq->rear = p;//移位
return 0;
}
datatype dequeue(linkqueue *lq){
linklist p;
datatype temp;
if (lq == NULL){
printf("lq is NULL\n");
return 0;
}
if (lq->front == lq->rear){
printf("lq is empty\n");
return 0;
}
p = lq->front;
lq->front= p->next;
temp = lq->front->data;
free(p);
p = NULL;
return temp;
}
int queue_empty(linkqueue *lq){
if (lq == NULL){
printf("lq is NULL\n");
return -1;
}
if (lq->front == lq->rear){
// printf("linkqueue is empty\n");
return -1;
}
return 0;
}
int queue_clear(linkqueue *lq){
linklist p;
if (lq == NULL){
printf("lq is NULL\n");
return 0;
}
while (!(lq->front == lq->rear))
{
p = lq->front;
lq->front = p->next;
// printf("clear:%d\n",p->data);
free(p);
p = NULL;
}
return 0;
}
linkqueue* queue_free(linkqueue *lq){
linklist p;
if (lq == NULL){
printf("lq is NULL\n");
return 0;
}
p = lq->front;
while (lq->front)
{
lq->front = p->next;
// printf("free:%d\n",p->data);
free(p);
p = lq->front;
}
free(lq);
lq = NULL;
return lq;
}
linkqueue.h
#include "bitree.h"
typedef bitree* datatype;
typedef struct listnode_t
{
datatype data;
struct listnode_t *next;
}listnode, *linklist;
typedef struct _linkqueue {
linklist front;
linklist rear;
}linkqueue;
linkqueue* queue_create();
int enqueue(linkqueue *lq, datatype x);
datatype dequeue(linkqueue *lq);
int queue_empty(linkqueue *lq);
int queue_clear(linkqueue *lq);
linkqueue* queue_free(linkqueue *lq);
评论(0)
您还未登录,请登录后发表或查看评论