数据结构—二叉树及gdb的应用
1.gdb
2.树
（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;
}