【数据结构】二叉树（下）

二叉树的链式结构

  链式二叉树的增删查改是没有意义的，建立在二叉树底子上的搜刮二叉树才具备增删查改的意义。但是链式二叉树是底子，就像修房子得先打地基一样。
二叉树的遍历

  首先确定一个概念，二叉树分为空树和非空树，只要黑白空树就有根节点、根节点的左子树和根节点的右子树。二叉树的定义是递归式的。
  二叉树遍历是按照某种特定的规则，依次对二叉树中的节点进行相应的操纵，并且每个节点只操纵依次。访问节点所做的操纵依赖于具体的应用问题，遍历是二叉树上最重要的运算之一，也是二叉树上进行别的运算的底子。
  二叉树一共有四种遍历方式，前序遍历（先根遍历）、中序遍历（中根遍历）、后序遍历（后根遍历）和层序遍历。
前序遍历（先根遍历）

  访问根节点的操纵发生在遍历其左右子树之前。在遍历时，会不断向下遍历知道碰到空树才制止。

1. void PrevOrder(BTNode* root)
2. {
3.         if (NULL == root)
4.         {
5.                 printf("NULL ");
6.                 return;
7.         }
9.         printf("%d ", root->data);
10.         PrevOrder(root->left);
11.         PrevOrder(root->right);
12. }

复制代码

  栈帧空间的创建烧毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示烧毁。创建烧毁的顺序是橙色->绿色->深蓝色->粉色->金色->紫色->青色。

中序遍历（中根遍历）

  访问根节点的操纵放生在遍历其左右子树之间。

1. void InOrder(BTNode* root)
2. {
3.         if (NULL == root)
4.         {
5.                 printf("NULL ");
6.                 return;
7.         }
9.         InOrder(root->left);
10.         printf("%d ", root->data);
11.         InOrder(root->right);
12. }

复制代码

  栈帧空间的创建烧毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示烧毁。创建烧毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色->青色->紫色。

后序遍历（后根遍历）

  访问根节点的操纵发生在遍历其左右子树之后。

1. void PostOrder(BTNode* root)
2. {
3.         if (NULL == root)
4.         {
5.                 printf("NULL ");
6.                 return;
7.         }
9.         PostOrder(root->left);
10.         PostOrder(root->right);
11.         printf("%d ", root->data);
12. }

复制代码

  栈帧空间的创建烧毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示烧毁。创建烧毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色->青色->紫色。

层序遍历

  从第一层开始，每层从左到右，一层一层的走。四种遍历中，只有层序遍历黑白递归的，它采用的是队列来实现的。

1. void LevelOrder(BTNode* root)
2. {
3.         Queue q;
4.         QueueInit(&q);
5.         // 先将根节点存入队列
6.         if (root)
7.                 QueuePush(&q, root);
8.         // 判空，如果为空就不执行以下语句
9.         while (!QueueEmpty(&q))
10.         {
11.                 // 获取队头，打印之后，移出队列
12.                 BTNode* front = QueueFront(&q);
13.                 printf("%d ", front->data);
14.                 QueuePop(&q);
16.                 if (front->left)
17.                         QueuePush(&q, front->left);
18.                 if (front->right)
19.                         QueuePush(&q, front->right);
20.         }
21.         printf("\n");
23.         QueueDestroy(&q);
24. }

复制代码

二叉树的构建

  二叉树的构建根据三种递归的遍历方式进行构建，可以进行前序、中序、后序构建，我这里利用的是前序构建。

1. BTNode* CreatBinaryTree(BTDataType* a, int* pi)
2. {
3.         if (-1 == a[*pi])
4.         {
5.                 (*pi)++;
6.                 return NULL;
7.         }
9.         BTNode* root = (BTNode*)malloc(sizeof(BTNode));
10.         if (NULL == root)
11.         {
12.                 perror("malloc fail");
13.                 exit(-1);
14.         }
16.         root->data = a[(*pi)++];
18.         root->left = CreatBinaryTree(a, pi);
19.         root->right = CreatBinaryTree(a, pi);
21.         return root;
22. }

复制代码

二叉树的节点数

1. int TreeSize(BTNode* root)
2. {
3.         if (NULL == root)
4.         {
5.                 return 0;
6.         }
7.         return TreeSize(root->left) + TreeSize(root->right) + 1;
8. }

复制代码

  栈帧空间的创建烧毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示烧毁。创建烧毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色->青色->紫色，末了返回的值是6。

二叉树的叶子数

1. int TreeLeafSize(BTNode* root)
2. {
3.         if (NULL == root)
4.         {
5.                 return 0;
6.         }
8.         if (NULL == root->left && NULL == root->right)
9.         {
10.                 return 1;
11.         }
13.         return TreeLeafSize(root->left) + TreeLeafSize(root->right);
14. }

复制代码

  栈帧空间的创建烧毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示烧毁。创建烧毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色，末了效果为3。

二叉树的高度

1. int TreeHeight(BTNode* root)
2. {
3.         if (NULL == root)
4.         {
5.                 return 0;
6.         }
8.         int left = TreeHeight(root->left);
9.         int right = TreeHeight(root->right);
11.         return  (left > right ? left : right) + 1;
12. }

复制代码

  栈帧空间的创建烧毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示烧毁。创建烧毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色，末了效果为3。

二叉树K层节点数

1. int TreeKLevelSize(BTNode* root, int k)
2. {
3.         if (NULL == root)
4.         {
5.                 return 0;
6.         }
7.         if (1 == k)
8.         {
9.                 return 1;
10.         }
12.         return TreeKLevelSize(root->left, k - 1) + TreeKLevelSize(root->right, k - 1);
13. }

复制代码

  栈帧空间的创建烧毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示烧毁。创建烧毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色，末了效果为3。

查找值为X的节点

1. BTNode* TreeFind(BTNode* root, BTDataType x)
2. {
3.         if (NULL == root)
4.                 return NULL;
5.         if (x == root->data)
6.                 return root;
8.         BTNode* ret1 = TreeFind(root->left, x);
9.         if (ret1)
10.                 return ret1;
11.         BTNode* ret2 = TreeFind(root->right, x);
12.         if (ret2)
13.                 return ret2;
15.         return NULL;
16. }

复制代码

  栈帧空间的创建烧毁顺序按照下图进行的，向右的箭头表示创建，向左的箭头表示烧毁。创建烧毁的顺序是橙色->绿色->蓝色->粉色->深蓝色->金色，末了效果为数字5节点的地点。

判定二叉树是否为完全二叉树

1. bool TreeComplete(BTNode* root)
2. {
3.         Queue q;
4.         QueueInit(&q);
5.         if (root)
6.                 QueuePush(&q, root);
7.         // 若队列为空，则不执行
8.         while (!QueueEmpty(&q))
9.         {
10.                 BTNode* front = QueueFront(&q);
11.                 QueuePop(&q);
12.                 // 判断front是否为空，为空则跳出循环
13.                 if (!front)
14.                 {
15.                         break;
16.                 }
17.                 else
18.                 {
19.                         QueuePush(&q, front->left);
20.                         QueuePush(&q, front->right);
21.                 }
22.         }
23.         // 若队列为空，则不执行
24.         while (!QueueEmpty(&q))
25.         {
26.                 BTNode* front = QueueFront(&q);
27.                 QueuePop(&q);
29.                 if (front)
30.                 {
31.                         QueueDestroy(&q);
32.                         return false;
33.                 }
34.         }
36.         QueueDestroy(&q);
37.         return true;
38. }

复制代码

二叉树的烧毁

1. // 二叉树销毁
2. void TreeDestory(BTNode* root)
3. {
4.         if (NULL == root)
5.         {
6.                 return;
7.         }
9.         TreeDestory(root->left);
10.         TreeDestory(root->right);
11.         free(root);
12. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。