4.2.2层序遍历
层序遍历：假设二叉树的根节点所在的层数为1，层序遍历便是从二叉树的根节点出发，先访问第一层的根节点，然后依次从左向右访问第二层上的节点，其次是第三层上的节点，以此类推，从上到下，从左到右逐层访问树的节点的过程就是层序遍历。
层序遍历采取队列的思想：先入先出
例如根节点先入队列，然后出队列时，通过左右指针将左右子树的根节点带入队列，重复此操作，直到将二叉树完全遍历。
代码实现
void Levelorder(BTnode* root) { QE q; QEinit(&q, root); if (root) { QEpush(&q, root); } while (!QEempty(&q)) { BTnode* front = QEfront(&q); QEpop(&q); printf("%d ", front->data); //下一层 if (front->left) { QEpush(&q, front->left); } if (front->right) { QEpush(&q, front->right); } } printf("\n"); QEdestory(&q); }
4.3节点个数以及高度
计算第k层叶子节点的总数
//计算第k层节点个数 int Treeksize(BTnode* root,int k) { if (root == NULL) { return 0; } if (k == 1) { return 1; } //转化成计算第(k-1)层节点的个数 return Treeksize(root->left, k - 1) + Treeksize(root->right, k - 1); }
计算总的节点个数
int Treesize(BTnode* root) { if (root == NULL) { return 0; } return Treesize(root->left) + Treesize(root->right) + 1; }
计算叶子节点总数
int Treeleafsize(BTnode* root) { if (root == NULL) { return 0; } if (root->left == NULL && root->right == NULL) { return 1; } return Treeleafsize(root->left) + Treeleafsize(root->right); }
高度
后序思想
计算左子树，右子树高度
父亲高度=较高的子树+1
int Treeheight(BTnode* root) { if (root == NULL) { return 0; } int lret = Treeheight(root->left); int rret = Treeheight(root->right); return lret > rret ? lret + 1 : rret + 1; }
求节点所在位置
//返回x所在的节点 BTnode* Treefind(BTnode* root, int x) { if (root == NULL) { return NULL; } if (root->data == x) { return root; } //找左子树 BTnode*lret = Treefind(root->left, x); if (lret) { return lret; } //左子树没有找到，找右子树 BTnode* rret = Treefind(root->right, x); if (rret) { return rret; } return NULL; }
4.4二叉树的创建和销毁
通过前序遍历数组
“1 2 3 NULL NULL 4 NULL NULL 5 NULL 6 NULL NULL” 构建二叉树
BTnode* Binarytreecreate(BTdatatype* a, int* pi) { if (NULL == a[*pi]) { (*pi)++; return NULL; } BTnode* root = (BTnode*)malloc(sizeof(BTnode)); if (root == NULL) { perror("malloc fail"); return NULL; } root->data = a[*pi]; (*pi)++; root->left = Binarytreecreate(a, pi); root->right = Binarytreecreate(a, pi); return root; }
中序遍历二叉树并打印
二叉树的销毁
void Binarytreedestory(BTnode* root) { if (root == NULL) { return; } Binarytreedestory(root->left); Binarytreedestory(root->right); free(root); }
判断二叉树是否为完全二叉树
int Binarytreecomplete(BTnode* root) { QE q; QEinit(&q); if (root) { QEpush(&q, root); } while (!QEempty(&q)) { BTnode* front = QEfront(&q); QEpop(&q); if (front == NULL) { break; } QEpush(&q, front->left); QEpush(&q, front->right); } //遇到NULL之后，从上面循环跳出 //如果后面全是空，则为完全二叉树 //如果后面存在非空，则不为完全二叉树 while (!QEempty(&q)) { BTnode* front = QEfront(&q); QEpop(&q); if (front != NULL) { return false; } } QEdestory(&q); //如果整个程序走完，则说明是完全二叉树，返回true return true; }
返回结果
