1.树的概念
(1)：节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6。
(2)：叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I...等节点为叶节点。
(3)：非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G...等节点为分支节点。
(4)：双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点。
(5)：孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点。
(6)：兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点。
(7)：树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6 。
(8)：节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。
(9)：树的高度或深度：树中节点的最大层次； 如上图：树的高度为4 。
(10)：堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点。
(11)：节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先 。
(12)：子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙。
(13)：森林：由m（m>0）棵互不相交的树的集合称为森林。
2.二叉树的概念
(1)：二叉树分别由：根+左子树+右子树组成。
(2)： 二叉树不存在度大于2的结点
(3)： 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
(4)：满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是 说，如果一个二叉树的层数为K，且结点总数是2^k-1 ，则它就是满二叉树。
(5)：完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
3.二叉树的性质
(1)： 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点。
(2)： 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1 。
(3)： 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为n2 ,则有n0 ＝ n2＋1。
(4)：若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= .log2(n+1) (ps： 是log以2 为底，n+1为对数)。
(5)： 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对 于序号为i的结点有。
若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点。
若2i+1=n否则无左孩子。
若2i+2=n否则无右孩子。
4.二叉树的遍历
1. 前序遍历：访问根结点的操作发生在遍历其左右子树之前——（根---左子树---右子树）。
2. 中序遍历：访问根结点的操作发生在遍历其左右子树之中（间）——（左子树---根---右子树）。
3. 后序遍历：访问根结点的操作发生在遍历其左右子树之后——（左子树---右子树---根）。
4.层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在 层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层 上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
5.二叉树的实现
#include#include #include #include typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; typedef struct Queue { QNode* head; QNode* tail; }Queue; // 初始化队列 void QueueInit(Queue* q) { assert(q); q->head = q->tail = NULL; } // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* q) { assert(q); return q->head == NULL; } // 队尾入队列 void QueuePush(Queue* q, QDataType x) { assert(q); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { printf("malloc:n"); exit(-1); } newnode->data = x; newnode->next = NULL; if (q->tail == NULL) { q->head = q->tail = newnode; } else { q->tail->next = newnode; q->tail = newnode; } } // 队头出队列 void QueuePop(Queue* q) { assert(q); assert(!QueueEmpty(q)); if (q->head->next == NULL) { free(q->head); q->head = q->tail = NULL; } else { QNode* next = q->head->next; free(q->head); q->head = next; } } // 获取队列头部元素 QDataType QueueFront(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q->head->data; } // 获取队列队尾元素 QDataType QueueBack(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q->tail->data; } // 获取队列中有效元素个数 int QueueSize(Queue* q) { assert(q); int size = 0; QNode* cur = q->head; while (cur) { size++; cur = cur->next; } return size; } // 销毁队列 void QueueDestroy(Queue* q) { assert(q); QNode* cur = q->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } q->head = q->tail = NULL; typedef char BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; BTNode* BuyNode(BTDataType x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); assert(node); node->data = x; node->left = NULL; node->right = NULL; return node; } // 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树 BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi) { if (a[*pi]=='#'||*pi>=n) { printf("NULL "); (*pi)++; return NULL; } //创建新的二叉树结点 BTNode* dst = BuyNode(a[*pi]); printf("%c ", dst->data); (*pi)++; dst->left = BinaryTreeCreate(a, n, pi); dst->right = BinaryTreeCreate(a, n, pi); return dst; } // 二叉树销毁 void BinaryTreeDestory(BTNode** root) { if (*root == NULL) { return; } //先找到二叉树左右子树中的底层结点，然后将叶子结点分别释放空间，再一层层返回调用，自下而逐渐销毁 BinaryTreeDestory(&((*root)->left)); BinaryTreeDestory(&((*root)->right)); free(*root); *root = NULL; return; } int count = 0; // 二叉树节点个数(每次使用需要手动置空count) //int BinaryTreeSize(BTNode* root) //{ // if (root == NULL) // { // return; // } // count++; // BinaryTreeSize(root->left); // BinaryTreeSize(root->right); //} // 二叉树节点个数(左子数+右子数+根) int BinaryTreeSize(BTNode* root) { return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1; } // 二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root) { if (root == NULL) { return 0; } if (root->left == NULL&&root->right==NULL) { return 1; } return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right); } // 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k) { assert(k >= 1); if (root == NULL) { return 0; } if (k == 1) { return 1; } //遍历至层数之后判断其元素是否为空 return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1); } // 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) { return NULL; } if (root->data == x) { return root; } //遍历左子树 BTNode* ret1 = BinaryTreeFind(root->left, x); if (ret1) { return ret1; } //遍历右子树 BTNode* ret2 = BinaryTreeFind(root->right, x); if (ret2) { return ret2; } //查找元素不存在 return NULL; } // 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root) { if (root == NULL) { printf("# "); return; } printf("%c ", root->data); BinaryTreePrevOrder(root->left); BinaryTreePrevOrder(root->right); } // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root) { if (root == NULL) { printf("# "); return; } BinaryTreePrevOrder(root->left); printf("%c ", root->data); BinaryTreePrevOrder(root->right); } // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root) { if (root == NULL) { printf("# "); return; } BinaryTreePrevOrder(root->left); BinaryTreePrevOrder(root->right); printf("%c ", root->data); } // 层序遍历 void BinaryTreeLevelOrder(BTNode* root) { //创建队列 QNode q; //初始化队列 QueueInit(&q); assert(root); //将根节点入队列 QueuePush(&q, root); while (!QueueEmpty(&q)) { //头节点 BTNode* temp = QueueFront(&q); printf("%c ", temp->data); //将左右指针所对应的结点入队列 if(temp->left) { QueuePush(&q, temp->left); } if(temp->right) { QueuePush(&q, temp->right); } //头节点出队 QueuePop(&q); } //销毁队列 QueueDestroy(&q); } // 二叉树深度 int TreeDepth(BTNode* root) { if (root == NULL) { return 0; } int leftDepth = BinaryTreeComplete(root->left)+1; int rightDepth = BinaryTreeComplete(root->right)+1; return leftDepth > rightDepth ? leftDepth : rightDepth; } // 判断二叉树是否是完全二叉树 int BinaryTreeComplete(BTNode* root) { //返回1表示为完全二叉树 if (root == NULL) { return 1; } //创建队列 Queue q; //初始化队列 QueueInit(&q); //根节点入队 QueuePush(&q, root); //如果为完全二叉树，叶子节点的下一层应该都为NULL； while (!QueueEmpty(&q)) { BTNode* temp = QueueFront(&q); QueuePop(&q); if (temp == NULL) { break; } QueuePush(&q, temp->left); QueuePush(&q, temp->right); } //返回1为完全二叉树，0则不是 while (!QueueEmpty(&q)) { BTNode* temp = QueueFront(&q); QueuePop(&q); if (temp != NULL) { return 0; } } return 1; } int main() { char a[17] = { 'A','B','D','#','#','E','#','H','#','#','C','F','#','#','G','#','#' }; int b = 0; int* pi = &b; BTNode* lin = BinaryTreeCreate(a, 16, pi); printf("n"); //前序遍历 BinaryTreePrevOrder(lin); printf("n"); //中序遍历 BinaryTreeInOrder(lin); printf("n"); //后续遍历 BinaryTreePostOrder(lin); printf("n"); //层次遍历 BinaryTreeLevelOrder(lin); printf("n"); //节点个数 int sun= BinaryTreeSize(lin); printf("节点个数=%dn", sun); // 二叉树查找值为x的节点 BTNode* str= BinaryTreeFind(lin, 'A'); printf("查找值为x的节点=%cn", str->data); //二叉树第k层节点个数 int x = BinaryTreeLevelKSize(lin, 3); printf("第k层节点个数=%dn", x); // 二叉树叶子节点个数 int count = BinaryTreeLeafSize(lin); printf("叶子节点个数=%dn", count); int p = BinaryTreeComplete(lin); if (p) { printf("是完全二叉树n"); } else { printf("不是完全二叉树n"); } //销毁二叉树 BinaryTreeDestory(&lin); return 0; }
