二叉树按层次遍历--队列实现

Dear 丶 2022-06-18 13:07 216阅读 0赞

最近数据结构看的还真是恶心额，脑子不好使，算法写不来额![大哭][wail.gif]·····

二叉树一大堆概念性的东西，不过还是写吧。

二叉树(binary tree)  
  
二叉树的基本形态  
　　二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：  
　　(1)空二叉树——(a)；    
      (2)只有一个根结点的二叉树——(b)；  
　　(3)只有左子树——(c)；  
　　(4)只有右子树——(d)；  
　　(5)完全二叉树——(e)  
  
  
度(Degree)：节点孩子的数目。  
叶子(Leaf): 度为0的节点称为叶子。  
深度(Depth):树中最大的层次(从最上0开始数)  
  
  
满二叉树：一棵深度为k且有2^k -1个节点的二叉树。  
完全二叉树：若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层有叶子节点，并且叶子节点都是从左到右依次排布，这就是完全二叉树。  
  
  
性质1:在二叉树的第i层上至多有2^(i-1)个节点(i >= 1)  
性质2:深度为k的二叉树至多有2^k - 1个节点  
性质3:任意一棵二叉树T，若其叶子节点数为n0,度为2的节点数为n2,则n0 = n2 + 1  
  
  
对于完全二叉树:  
  
性质4:具有n个节点的完全二叉树的深度是\[log2n\] + 1  
性质5:有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：  
　　  若I为结点编号则 如果I<>1，则其父结点的编号为I/2；  
　　  如果2\*I<=N，则其左儿子（即左子树的根结点）的编号为2\*I；若2\*I>N，则无左儿子；  
　　  如果2\*I+1<=N，则其右儿子的结点编号为2\*I+1；若2\*I+1>N，则无右儿子。

二叉树按层次遍历----队列实现  
1.创建二叉树，输入\#代表NULL，调用递归创建二叉树。  
2.构建一个队列专门用来储存二叉树节点指针，先把根节点入队，假设是A，对A元素进行访问，然后对A的左右孩子依次入队，假设B,C。A出队列，再是对B进行访问，同样将B的左右孩子入队列，B出对列······重复以上，知道队列为空。

下面是的代码是实现按层次从上到下遍历二叉树：

#include <Windows.h> #include <stdio.h> #define ElemType char typedef struct TreeNode{ //单位节点 struct TreeNode *LChild; struct TreeNode *RChild; ElemType c; }TreeNode,* p_Tree; typedef struct Link{ //单向链表 struct Link *Next; TreeNode *Node; }Link,*P_Link; typedef struct Queue{ //形成队列 P_Link front; P_Link rear; int Q_Len; }Queue,*p_Queue; BOOL PrintElement(ElemType e); //对二叉树节点的操作，自定义，这里我设置为打印出内容 BOOL CreateTree(p_Tree* pBiTree); //创建二叉树 P_Link InitLink(P_Link L); //初始化链表 P_Link InsertLink(P_Link L,TreeNode *Tree_Node,p_Queue *Q); //插入队列 p_Queue GetTopLinkNode(P_Link L, BOOL(*Visit)(ElemType),p_Queue Q); //取出队列第一个元素，并且访问左右孩子 p_Queue InitQueue(p_Queue T,P_Link L); //初始化队列 int main() { p_Tree Tree = NULL; P_Link Link = NULL; p_Queue Queue = NULL; if(!CreateTree(&Tree)) //创建二叉树 { printf("Create Tree Error\n"); return 0; } p_Tree p_Temp_Node = Tree; Link = InitLink(Link); Queue = InitQueue(Queue,Link); Link = InsertLink(Link,p_Temp_Node,&Queue); //根节点入队 BOOL(*Operate)(ElemType); //定义函数指针 Operate = PrintElement; while(Queue->front != Queue->rear) { Queue = GetTopLinkNode(Link,Operate,Queue); //获取队列第一个节点 Link = InsertLink(Link,Queue->front->Node->LChild,&Queue); //左孩子入队 Link = InsertLink(Link,Queue->front->Node->RChild,&Queue); //右孩子入队 } return 0; } BOOL CreateTree(p_Tree* pBiTree) { ElemType ch; ch = getchar(); if (ch == '#') //#代表NULL { (*pBiTree) = NULL; } else { (*pBiTree) = (p_Tree)calloc(1,sizeof(TreeNode)); if (!(*pBiTree)) { printf("Allocate Memory Error\n"); return FALSE; } else { (*pBiTree)->c = ch; CreateTree(&(*pBiTree)->LChild); //调用递归创建二叉树 CreateTree(&(*pBiTree)->RChild); } } return TRUE; } P_Link InitLink(P_Link L) { L = (P_Link)calloc(1,sizeof(Link)); if (!L) { printf("Memory Error\n"); return NULL; } L->Node = NULL; L->Next = NULL; return L; } p_Queue InitQueue(p_Queue T,P_Link L) { T = (p_Queue)calloc(1,sizeof(Queue)); T->Q_Len = 0; T->front = L; T->rear = L; return T; } P_Link InsertLink(P_Link L,TreeNode *Tree_Node,p_Queue *Q) { if (Tree_Node == NULL) { return L; } else { static P_Link p = L; P_Link pNew; pNew = (P_Link)calloc(1,sizeof(Link)); if (!pNew) { printf("Memory Error\n"); return 0; } pNew->Node = Tree_Node; //New Node pNew->Next = NULL; p->Next = pNew; //p to Next p = pNew; (*Q)->rear = p; //Add Queue (*Q)->Q_Len++ ; //Q len ++ return L; } } p_Queue GetTopLinkNode(P_Link L, BOOL(*Visit)(ElemType),p_Queue Q) { Q->front = Q->front->Next; //remove first Node Visit(Q->front->Node->c); Q->Q_Len--; return Q; } BOOL PrintElement(ElemType e) { // 输出元素e的值 printf("%c",e); return TRUE; }

[wail.gif]: /images/20220618/66a9f432f9df487ba048d36e87c7465a.png