二叉树的遍历
前序、中序以及后序遍历
1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
二叉树遍历的实现
结构体的创建
typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode;
节点的初始化
BTNode* CreateTree() { BTNode* n1 = (BTNode*)malloc(sizeof(BTNode)); assert(n1); BTNode* n2 = (BTNode*)malloc(sizeof(BTNode)); assert(n2); BTNode* n3 = (BTNode*)malloc(sizeof(BTNode)); assert(n3); BTNode* n4 = (BTNode*)malloc(sizeof(BTNode)); assert(n4); BTNode* n5 = (BTNode*)malloc(sizeof(BTNode)); assert(n5); BTNode* n6 = (BTNode*)malloc(sizeof(BTNode)); assert(n6); BTNode* n7 = (BTNode*)malloc(sizeof(BTNode)); assert(n7); n1->data = 1; n2->data = 2; n3->data = 3; n4->data = 4; n5->data = 5; n6->data = 6; n1->left = n2; n1->right = n4; n2->left = n3; n2->right = NULL; n4->left = n5; n4->right = n6; n3->left = NULL; n3->right = NULL; n5->left = NULL; n5->right = NULL; n6->left = NULL; n6->right = NULL; n3->right = NULL; return n1; }
前序遍历
void PreOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%d ", root->data); PreOrder(root->left); PreOrder(root->right); }
中序遍历
void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); }
后序遍历
void PostOrder(BTNode* root) { if (root == NULL) return; PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); }
节点个数的计算
int TreeSize(BTNode* root) { return root == NULL ? 0 : 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; //如果为叶子节点，返回1.否则继续遍历 return TreeLeafSize(root->left)+ TreeLeafSize(root->right); }
高度的计算
int TreeHeight(BTNode* root) { if (root == NULL); return 0; int lh = TreeHeight(root->left); int rh = TreeHeight(root->right); return lh > rh ? lh + 1 : rh + 1; }
某层总节点个数
int TreeLevel(BTNode* root, BTDataType x) { if (root == NULL) return 0; if (x == 1) return 1; //如果是第一层，返回1，否则继续往下 return TreeLevel(root->left, x - 1) + TreeLevel(root->right, x - 1); }
节点查找
BTNode* TreeFind(BTNode* root, BTDataType 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->left, x); if (rret) return rret; return NULL; }
节点销毁
void BinaryTreeDestory(BTNode* root) //这里用一级或二级指针都可以 { if (root == NULL) return; BinaryTreeDestory(root->left); BinaryTreeDestory(root->right); free(root); }
二叉树层的遍历
用队列实现层的遍历
先把二叉树的根放进去，然后打印这个值，之后再把根弹出，弹出的时候把左节点和右节点压进去
typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; typedef BTNode* QDataType;//里面放的是二叉树 typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; typedef struct Queue { //int size; QNode* head; QNode* tail; }Queue; //结构体的定义 void TreeLevelOrder(BTNode* root) //层遍历函数 { Queue q; QueueInit(&q); if (root) QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); printf("%d ", front->data); // 下一层，入队列 if (front->left) QueuePush(&q, front->left); if (front->right) QueuePush(&q, front->right); } printf("\n"); QueueDestroy(&q); } int main() { BTNode *BT= CreateTree(); TreeLevelOrder(BT); return 0; }
是否为完全二叉树
思路：1.采用层序遍历，若遇到NULL，跳出循环，再判断NULL后面的是否有不为空的节点，若有则不是完全二叉树，若后面的全是空，则是完全二叉树
bool TreeLevelOrderComplete(BTNode* root) //遍历 { Queue q; QueueInit(&q); if (root) QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); if (front == NULL) break; QueuePush(&q, front->left); QueuePush(&q, front->right); } //找到第一个空节点 while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); if (front != NULL) { QueueDestroy(&q); return false; } } QueueDestroy(&q); return true; }
