二叉树：
是一种常用的数据结构。
定义：二叉树是n个有限元素的集合，由一个根和左子树以及右子树组成，是有序树。当集合为空时，又称为空二叉树。
二叉树的性质：
性质1：二叉树的第i层上最多有2^(i-1)个节点。
每层的节点数都是2^(i-1)，这种树叫满二叉树。
对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
性质2：深度为h的二叉树中至多含有2^h-1个节点。
性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1。
性质4：具有n个节点的完全二叉树深为log2^n+1。
性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：
当i=1时，该节点为根，它无双亲节点。
当i>1时，该节点的双亲节点的编号为i/2(顺序存储)。
如果2i<=n，则编号为2i 则有编号为i的左孩子。
如果2i+1<=n，则编号为 2i+1 为编号为i的右孩子。
二叉树的操作：
构建、销毁、遍历、高度、密度、插入、删除、查询、求左、求右、求根
二叉树的存储：
顺序：必须按照完全二叉树的格式存储，空位置使用特殊数据代替。
数据项：
存储节点的内存
容量
链式：由一个个节点组成，每一个节点就是一棵树。
节点数据项：
数据

二叉树的遍历：
前序：根、左、右
中序：左、根、右
后序：左、右、根
注意：前中后由根节点决定，不存在左、左根的后序，左、右子的次序不变。
注意：根据 前序+中序 或者 中序+后序 还原一棵树，前序+后序无法还原（无法判断出根节点的左右子树）。

关于二叉树的代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "list_stack.h"typedef struct TreeNode	//创建二叉树
{int data;struct TreeNode* left;struct TreeNode* right;
}TreeNode;TreeNode* create_tree_node(int data)//创建节点
{TreeNode* node = malloc(sizeof(TreeNode));node->data = data;node->left = NULL;node->right = NULL;return node;
}
void _insert_tree(TreeNode** root,TreeNode* node)
{if(NULL == *root){*root = node;return;}if(node->data < (*root)->data)_insert_tree(&(*root)->left,node);else_insert_tree(&(*root)->right,node);}void insert_tree(TreeNode** root,int data)//插入
{_insert_tree(root,create_tree_node(data));
}// 前序
void dlr_show(TreeNode* root)
{if(NULL == root) return;printf("%d ",root->data);dlr_show(root->left);dlr_show(root->right);
}// 中序
void ldr_show(TreeNode* root)
{if(NULL == root) return;ldr_show(root->left);printf("%d ",root->data);ldr_show(root->right);
}// 后序
void lrd_show(TreeNode* root)
{if(NULL == root) return;lrd_show(root->left);lrd_show(root->right);printf("%d ",root->data);
}// 查找
bool query_tree(TreeNode* root,int data)
{if(NULL == root) return false;if(data == root->data) return true;if(data < root->data)return query_tree(root->left,data);elsereturn query_tree(root->right,data);}// 密度
int density_tree(TreeNode* root)
{if(NULL == root) return 0;return density_tree(root->left)+density_tree(root->right)+1;
}// 销毁
void destory_tree(TreeNode* root)
{if(NULL == root) return;destory_tree(root->left);destory_tree(root->right);free(root);
}bool _access_tree(TreeNode* root,int* k,size_t index,int* ptr)
{if(NULL == root) return false;bool rflag = _access_tree(root->right,k,index,ptr);if((*k)++ == index){*ptr = root->data;return true;}bool lflag = _access_tree(root->left,k,index,ptr);return lflag || rflag;
}// 访问
bool access_tree(TreeNode* root,size_t index,int* ptr)
{int k = 0;return _access_tree(root,&k,index,ptr);
}// 删除
bool del_tree(TreeNode** root,int data)
{if(NULL == *root) return false;if((*root)->data == data){TreeNode* temp = *root;*root = temp->left;_insert_tree(root,temp->right);free(temp);return true;}if(data < (*root)->data)return del_tree(&(*root)->left,data);elsereturn del_tree(&(*root)->right,data);}int _high_tree(TreeNode* root,bool* flag)
{if(NULL == root) return 0;int lh = _high_tree(root->left,flag);int rh = _high_tree(root->right,flag);if(flag && abs(lh-rh)>1) *flag = false;return lh>rh?lh+1:rh;
}// 高度
int high_tree(TreeNode* root)
{return _high_tree(root,NULL);
}// 判断是否平衡
int isAVL_tree(TreeNode* root)
{bool flag = true;_high_tree(root,&flag);return flag;
}bool treecmp(TreeNode* r1,TreeNode* r2)
{if(NULL == r1 && NULL == r2) return true;if(NULL == r1 && NULL != r2) return false;if(NULL != r1 && NULL == r2) return true;if(r1->data != r2->data) return false;return treecmp(r1->left,r2->left) && treecmp(r1->right,r2->right);}bool is_subtree(TreeNode* root,TreeNode* node)//判断是否是子节点
{if(NULL == root) return false;if(root->data == node->data)return treecmp(root,node);bool lflag = is_subtree(root->left,node);bool rflag = is_subtree(root->right,node);return lflag || rflag;}void _add_tail_list(TreeNode** head,TreeNode* node)
{printf("%d\n",node->data);if(NULL == *head){*head = node;}else{(*head)->left->right = node;node->left = (*head)->left;}(*head)->left = node;
}void _tree_to_list(TreeNode* root,TreeNode** head)
{if(NULL == root) return;_tree_to_list(root->left,head);_add_tail_list(head,root);_tree_to_list(root->right,head);
}TreeNode* tree_to_list(TreeNode* root)
{TreeNode* head = NULL;_tree_to_list(root,&head);return head;
}void z_show(TreeNode* root)//二叉树Z序打印
{ListStack* s1 = create_list_stack();ListStack* s2 = create_list_stack();push_list_stack(s1,root);while(!empty_list_stack(s1) || !empty_list_stack(s2)){while(!empty_list_stack(s1)){TreeNode* node = top_list_stack(s1);pop_list_stack(s1);printf("%d ",node->data);if(node->left) push_list_stack(s2,node->left);if(node->right) push_list_stack(s2,node->right);}printf("\n============\n");while(!empty_list_stack(s2)){TreeNode* node = top_list_stack(s2);pop_list_stack(s2);printf("%d ",node->data);if(node->right) push_list_stack(s1,node->right);if(node->left) push_list_stack(s1,node->left);}printf("\n============\n");}}int main(int argc,const char* argv[])
{TreeNode* root = NULL;for(int i=0; i<10; i++){int data = rand() % 100;printf("%d ",data);insert_tree(&root,data);}printf("\n");z_show(root);/*ddint num = 0;access_tree(root,3,&num) && printf("倒数k个数：%d\n",num);del_tree(&root,100);int num = 0;access_tree(root,6,&num) && printf("access:%d\n",num);printf("%d\n",high_tree(root));printf("%d\n",density_tree(root));printf("%s\n",isAVL_tree(root)?"平衡":"不平衡");ldr_show(root); puts("");density_tree(root);root = NULL;*/}