[数据结构]8. 树-Tree

1. 介绍

二叉树（binary tree） 是一种非线性数据结构

/* 二叉树节点结构体 */  
typedef struct TreeNode {  int val;// 节点值int height;// 节点高度struct TreeNode *left; // 左子节点指针  struct TreeNode *right; // 右子节点指针  
} TreeNode;  
/* 构造函数 */  
TreeNode *newTreeNode(int val) {  TreeNode *node;  node = (TreeNode *)malloc(sizeof(TreeNode));  node->val = val;  node->height = 0;  node->left = NULL;  node->right = NULL;  return node;  
}

术语

• 根节点（root node）：位于二叉树顶层的节点，没有父节点。
• 叶节点（leaf node）：没有子节点的节点，其两个指针均指向 None 。
• 边（edge）：连接两个节点的线段，即节点指针。
• 节点所在的层（level）：从顶至底递增，根节点所在层为 1 。
• 节点的度（degree）：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。
• 二叉树的高度（height）：从根节点到最远叶节点所经过的边的数量。
• 节点的深度（depth）：从根节点到该节点所经过的边的数量。
• 节点的高度（height）：从距离该节点最远的叶节点到该节点所经过的边的数量。

插入与删除节点

2. 二叉树分类

完美二叉树(满二叉树)

完美二叉树（perfect binary tree） 所有层的节点都被完全填满。

完全二叉树

完全二叉树（complete binary tree） 只有最底层的节点未被填满，且最底层节点尽量靠左填充。完美二叉树也是一棵完全二叉树。

完满二叉树

完满二叉树（full binary tree） 除了叶节点之外，其余所有节点都有两个子节点。

平衡二叉树

平衡二叉树（balanced binary tree） 中任意节点的左子树和右子树的高度之差的绝对值不超过 1 。

3. 树操作

Struct

typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

BuyNode

BTNode* BuyNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return NULL;}node->data = x;node->left = NULL;node->right = NULL;return node;
}

CreatBinaryTree

BTNode* CreatBinaryTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);BTNode* node7 = BuyNode(7);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;node5->left = node7;return node1;
}

BTreeDestory

void BTreeDestory(BTNode* root) {if (root == NULL) {return;}BTreeDestory(root->left);BTreeDestory(root->right);free(root);
}

PrevOrder

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

InOrder

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

PostOrder

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

BTreeSize

// 求节点个数
int BTreeSize(BTNode* root) {return root == NULL ? 0 : BTreeSize(root->left) + BTreeSize(root->right) + 1;
}

BTreeLeafSize

// 求叶子节点个数
int BTreeLeafSize(BTNode* root) {if (root == NULL) {return 0;}if (root->left == NULL && root->right == NULL) {return 1;}return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}

BTreeHight

// 求树高度
int BTreeHight(BTNode* root) {if (root == NULL) {return 0;}int leftHight = BTreeHight(root->left);int rightHight = BTreeHight(root->right);return leftHight > rightHight ? leftHight + 1 : rightHight + 1;
}

BTreeLevelKSize

// 二叉树第k层节点个数
int BTreeLevelKSize(BTNode* root, int k) {assert(k > 0);if (root == NULL) {return 0;}if (k == 1) {return 1;}return BTreeLevelKSize(root->left, k - 1)+ BTreeLevelKSize(root->right, k - 1);
}

BTreeFind

// 查找值为x的节点
BTNode* BTreeFind(BTNode* root, BTDataType x) {if (root == NULL) {return NULL;}if (root->data == x) {return root;}BTNode* ret1 = BTreeFind(root->left, x);if (ret1) {return ret1;}BTNode* ret2 = BTreeFind(root->right, x);if (ret2) {return ret2;}return NULL;
}

LevelOrder

// 层序遍历
void LevelOrder(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);
}

BTreeComplete

// 判断是否完全二叉树
bool BTreeComplete(BTNode* root) {Queue q;QueueInit(&q);if (root) {QueuePush(&q, root);}// 找到第一个空节点while (!QueueEmpty(&q)) {BTNode* front = QueueFront(&q);QueuePop(&q);// 是空就跳出if (front == NULL) {break;}// 非空就继续push节点进队列QueuePush(&q, front->left);QueuePush(&q, front->right);}// 判断后续是否全空while (!QueueEmpty(&q)) {BTNode* front = QueueFront(&q);QueuePop(&q);// 存在非空就falseif (front) {QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}