数据结构二叉树与gdb应用

一、gdb

二、树

（1）基本概念

①树的定义

树是n(n≥0)个结点的有限集合。当n=0时称为空树；非空树满足：

有且仅有一个特定的称为根(Root)的结点

其余结点可分为m(m≥0)个互不相交的有限集合，每个集合本身又是一棵树，称为根的子树(SubTree)

②基本术语

结点(Node)：树中的每个元素

根结点(Root)：没有前驱的结点（最顶层的结点）

叶子结点(Leaf)：没有后继的结点（度为0的结点）

分支结点(Branch Node)：度不为0的结点

度(Degree)：一个结点拥有的子树数目

树的度：树中所有结点度的最大值

层次(Level)：根为第一层，其孩子为第二层，以此类推

深度/高度(Depth/Height)：树中结点的最大层次数

森林(Forest)：m(m≥0)棵互不相交的树的集合

③二叉树的性质

第i层最多有2^(i-1)个结点

深度为k的二叉树最多有2^k -1个结点

任意二叉树：n_0 = n_2 + 1（叶子结点比度为2的结点多1）

④二叉树的分类

二叉树：每个结点最多有两个子树的树结构

满二叉树：所有分支结点都有左右子树且所有叶子在同一层

完全二叉树：除最后一层外其他层都达到最大结点数，最后一层结点从左向右连续排列

⑤二叉树的遍历

1. 深度优先遍历(DFS)

(1) 先序遍历(Preorder Traversal)
访问顺序：根结点 → 左子树 → 右子树
算法：

访问根结点

先序遍历左子树

先序遍历右子树

(2) 中序遍历(Inorder Traversal)
访问顺序：左子树 → 根结点 → 右子树
算法：

中序遍历左子树

访问根结点

中序遍历右子树

(3) 后序遍历(Postorder Traversal)
访问顺序：左子树 → 右子树 → 根结点
算法：

后序遍历左子树

后序遍历右子树

访问根结点

2. 广度优先遍历(BFS)

层次遍历(Level Order Traversal)
访问顺序：从上到下、从左到右逐层访问
算法（使用队列）：

将根结点入队

当队列不为空时：

出队一个结点并访问

将其左右孩子依次入队

应用：计算树的高度、查找特定层结点

三、

（2）基本操作

①创建

typedef char Data_type_t;

typedef struct BITnode
{
Data_type_t data;
struct BITnode *lchild;
struct BITnode *rchild;
}Tnode_t;

void CreateTree(Tnode_t **root)
{
char c = data[ind++];
if('#' == c)
{
*root = NULL;
return ;
}
else
{
*root = malloc(sizeof(Tnode_t));
if(NULL == *root)
{
printf("malloc error\\n");
return ;
}
(*root)->data = c;
CreateTree(&(*root)->lchild);
CreateTree(&(*root)->rchild);
}
return ;
}

②深度优先遍历的先序遍历

void PreOrderTraverse(Tnode_t *root)
{
if(NULL == root)
{
return ;
}
else
{
printf("%c ", root->data);
PreOrderTraverse(root->lchild);
PreOrderTraverse(root->rchild);
}
return ;
}

③深度优先遍历的中序遍历

void InOrderTraverse(Tnode_t *root)
{
if(NULL == root)
{
return ;
}
else
{
InOrderTraverse(root->lchild);
printf("%c ", root->data);
InOrderTraverse(root->rchild);
}
return ;
}

④深度优先遍历的后序遍历

void PostOrderTraverse(Tnode_t *root)
{
if (NULL == root)
{
return;
}
PostOrderTraverse(root->lchild);
PostOrderTraverse(root->rchild);
printf("%c", root->data);
return;
}

⑤销毁

void DestroyTree(Tnode_t *root)
{
if (NULL == root)
{
return;
}
DestroyTree(root->lchild);
DestroyTree(root->rchild);
free(root);
root = NULL;
return;
}

⑥广度优先遍历的层次遍历

#include <stdio.h>
#include <stdlib.h>

typedef char Data_type_t;

typedef struct BITnode
{
Data_type_t data;
struct BITnode *lchild;
struct BITnode *rchild;
} Tnode_t;

typedef struct lqnode
{
Tnode_t *tree_node;
struct lqnode *pnext;
} LQNode_t;

typedef struct lqueue
{
LQNode_t *phead;
LQNode_t *ptail;
int clen;
} LQueue_t;

char data[] = "abd#g###ce#h##fi###";
int ind = 0;

LQueue_t *create_linkque()
{
LQueue_t *plq = malloc(sizeof(LQueue_t));
if (NULL == plq)
{
return NULL;
}

plq->clen = 0;
plq->phead = NULL;
plq->ptail = NULL;

return plq;
}

void CreateTree(Tnode_t **root)
{
char c = data[ind++];
if ('#' == c)
{
*root = NULL;
return;
}
else
{
*root = malloc(sizeof(Tnode_t));
if (NULL == *root)
{
printf("malloc error\\n");
return;
}
(*root)->data = c;
CreateTree(&(*root)->lchild);
CreateTree(&(*root)->rchild);
}
return;
}

void enqueue(LQueue_t *pqueue, Tnode_t *ptree)
{
if (NULL == ptree)
{
return ;
}

LQNode_t *pnew = malloc(sizeof(LQNode_t));
if (NULL == pnew)
{
printf("malloc error\\n");
return;
}

pnew->tree_node = ptree;
pnew->pnext = NULL;

if (NULL == pqueue->phead)
{
pqueue->phead = pnew;
pqueue->ptail = pnew;
}
else
{
pqueue->ptail->pnext = pnew;
pqueue->ptail = pnew;
}
pqueue->clen++;
}

Tnode_t *dequeue(LQueue_t *pqueue)
{
if (NULL == pqueue->phead)
{
return NULL;
}
LQNode_t *ptmp = pqueue->phead;
Tnode_t *ptree = ptmp->tree_node;

pqueue->phead = ptmp->pnext;
if (NULL == pqueue->phead)
{
pqueue->ptail = NULL;
}

free(ptmp);
pqueue->clen–;

return ptree;
}

void LevelOrderTraversal(Tnode_t *root)
{
if (NULL == root)
{
return ;
}

LQueue_t *pqueue = create_linkque();
if (NULL == pqueue)
{
printf("Create queue failed\\n");
return ;
}

enqueue(pqueue, root);

while (pqueue->clen > 0)
{
Tnode_t *p = dequeue(pqueue);
printf("%c ", p->data);

if (p->lchild)
{
enqueue(pqueue, p->lchild);
}

if (p->rchild)
{
enqueue(pqueue, p->rchild);
}

}

while (pqueue->clen > 0)
{
dequeue(pqueue);
}
free(pqueue);

printf("\\n");
}

void DestroyTree(Tnode_t *root)
{
if (NULL == root)
{
return ;
}
DestroyTree(root->lchild);
DestroyTree(root->rchild);
free(root);
root = NULL;
return ;
}

int main()
{
Tnode_t *root = NULL;
CreateTree(&root);

LevelOrderTraversal(root);

DestroyTree(root);
return 0;
}