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

文章目录

• • • 二叉树的链式结构
    • • 二叉树的遍历
      • • 前序遍历（先根遍历）
        • 中序遍历（中根遍历）
        • 后序遍历（后根遍历）
        • 层序遍历
      • 二叉树的构建
      • 二叉树的节点数
      • 二叉树的叶子数
      • 二叉树的高度
      • 二叉树K层节点数
      • 查找值为X的节点
      • 判断二叉树是否为完全二叉树
      • 二叉树的销毁

二叉树的链式结构

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

二叉树的遍历

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

前序遍历（先根遍历）

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

void PrevOrder(BTNode* root){if (NULL == root){printf("NULL ");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);}

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

中序遍历（中根遍历）

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

void InOrder(BTNode* root){if (NULL == root){printf("NULL ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);}

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

后序遍历（后根遍历）

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

void PostOrder(BTNode* root){if (NULL == root){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);}

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

层序遍历

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

void LevelOrder(BTNode* root){Queue q;QueueInit(&q);// 先将根节点存入队列if (root)QueuePush(&q, root);// 判空，如果为空就不执行以下语句while (!QueueEmpty(&q)){// 获取队头，打印之后，移出队列BTNode* front = QueueFront(&q);printf("%d ", front->data);QueuePop(&q);if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}printf("\n");QueueDestroy(&q);}

二叉树的构建

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

BTNode* CreatBinaryTree(BTDataType* a, int* pi){if (-1 == a[*pi]){(*pi)++;return NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (NULL == root){perror("malloc fail");exit(-1);}root->data = a[(*pi)++];root->left = CreatBinaryTree(a, pi);root->right = CreatBinaryTree(a, pi);return root;}

二叉树的节点数

int TreeSize(BTNode* root){if (NULL == root){return 0;}return TreeSize(root->left) + TreeSize(root->right) + 1;}

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

二叉树的叶子数

int TreeLeafSize(BTNode* root){if (NULL == root){return 0;}if (NULL == root->left && NULL == root->right){return 1;}return TreeLeafSize(root->left) + TreeLeafSize(root->right);}

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

二叉树的高度

int TreeHeight(BTNode* root){if (NULL == root){return 0;}int left = TreeHeight(root->left);int right = TreeHeight(root->right);return(left > right " />: right) + 1;}

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

二叉树K层节点数

int TreeKLevelSize(BTNode* root, int k){if (NULL == root){return 0;}if (1 == k){return 1;}return TreeKLevelSize(root->left, k - 1) + TreeKLevelSize(root->right, k - 1);}

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

查找值为X的节点

BTNode* TreeFind(BTNode* root, BTDataType x){if (NULL == root)return NULL;if (x == root->data)return root;BTNode* ret1 = TreeFind(root->left, x);if (ret1)return ret1;BTNode* ret2 = TreeFind(root->right, x);if (ret2)return ret2;return NULL;}

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

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

bool TreeComplete(BTNode* root){Queue q;QueueInit(&q);if (root)QueuePush(&q, root);// 若队列为空，则不执行while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);// 判断front是否为空，为空则跳出循环if (!front){break;}else{QueuePush(&q, front->left);QueuePush(&q, front->right);}}// 若队列为空，则不执行while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;}

二叉树的销毁

// 二叉树销毁void TreeDestory(BTNode* root){if (NULL == root){return;}TreeDestory(root->left);TreeDestory(root->right);free(root);}