二叉树是每个节点最多有两个子节点的有序树。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。
二叉树的第i层至多有2^(i -1)个节点；
深度为k的二叉树至多有2^k - 1个节点；
对任何一颗二叉树，若其终端节点数为n0,度为2的节点数为n2,则 n0 = n2 + 1;
------------------------------------------------------------------------------------------------------------------------------------------------------------
二叉树的层序遍历：顾名思义，按照从上到下，从左到右的顺序来逐层访问每个节点。层次遍历的特点需要使用到队列这种先进先出的数据结构。
首先还是定义二叉树这种链式存储结构的结构体：
typedef struct BiTNode{ char data; struct BiTNode* lchild, *rchild; }BiTNode, *BiTree;
创建二叉树的过程：
void CreateBiTree(BiTree &T) // 创建二叉树 { char data; scanf("%c", &data); if(data == '#'){ // '#'表示空节点 T = NULL; } else { T = (BiTree)malloc(sizeof(BiTNode)); T->data = data; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } }
层序遍历的步骤：
1.根节点入队列，然后出列；分别判断其是否有左右孩子节点，如果有，则左右孩子节点就相对应的作为根节点；
2.再让根节点入队列，然后出列，按照步骤1进行，直到队列为空为止。
void BFS(BiTree T) //层序遍历 { queue<BiTree> Q; BiTree B; Q.push(T); //先压入整棵树的根节点 while(!Q.empty()) { B = Q.front(); // 访问队列第一个元素 cout<<B->data<<" "; if(B->lchild != NULL) { Q.push(B->lchild); // 左节点 } if(B->rchild != NULL) { Q.push(B->rchild); // 右节点 } Q.pop(); // 弹出当前节点 } cout<<endl; } void BFS(BiTree T) //层序遍历 { queue<BiTree> Q; BiTree B; Q.push(T); //先压入整棵树的根节点 while(!Q.empty()) { B = Q.front(); // 访问队列第一个元素 cout<<B->data<<" "; if(B->lchild != NULL) { Q.push(B->lchild); // 左节点 } if(B->rchild != NULL) { Q.push(B->rchild); // 右节点 } Q.pop(); // 弹出当前节点 } cout<<endl; }
整个程序的代码：
#include<iostream> #include<queue> #include<malloc.h> #include<stdio.h> using namespace std;
typedef struct BiTNode{ char data; struct BiTNode* lchild, *rchild; }BiTNode, *BiTree;
void CreateBiTree(BiTree &T) // 创建二叉树 { char data; scanf("%c", &data); if(data == '#'){ // '#'表示空节点 T = NULL; } else { T = (BiTree)malloc(sizeof(BiTNode)); T->data = data; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } }
void BFS(BiTree T) //层序遍历 { queue<BiTree> Q; BiTree B; Q.push(T); //先压入整棵树的根节点 while(!Q.empty()) { B = Q.front(); // 访问队列第一个元素 cout<<B->data<<" "; if(B->lchild != NULL) { Q.push(B->lchild); // 左节点 } if(B->rchild != NULL) { Q.push(B->rchild); // 右节点 } Q.pop(); // 弹出当前节点 } cout<<endl; }
int main() { BiTree Bi; CreateBiTree(Bi); BFS(Bi); system("pause"); return 0; }
