树的定义

树是由n（n大于等于0）个节点构成的集合，当n是0时则是空集，若是非空，则树是由一个称为根（root）的节点r以及0个或者多个非空的子树树 - 图1组成。这些子树中每一颗的根都被来自根r的一条有向边(edge)连接。

每一颗子树的根叫做根r的儿子(child),而r是每一颗子树的根的父亲(parent)

树 - 图2
没有儿子的节点为叶节点
具有相同父亲的位兄弟节点

对于任意节点，节点的深度为从根节点到该节点的唯一路径的长

二叉树（Binary Tree）

二叉树是一颗树，是一个有穷的节点的集合，或者为空，或者包含一个树根与两个不相交的二叉树称为左、右子树。

树节点 struct定义

  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. typedef struct TreeNode BinaryTreeNode;
  6. typedef BinaryTreeNode *PtrNode;
  7. struct TreeNode
  8. {
  9.     /* data */
  10.     int data;
  11.     PtrNode left;
  12.     PtrNode right;
  13. };
  14. PtrNode createTreeNode(const int data)
  15. {
  16.     PtrNode node;
  17.     node = (PtrNode)malloc(sizeof(node));
  18.     if (node == NULL)
  19.     {
  20.         printf("内存分配失败\n");
  21.         exit(EXIT_FAILURE);
  22.     }
  23.     node->left = node->right = NULL;
  24.     node->data = data;
  25.     return node;
  26. };

插入

  1. PtrNode insert(PtrNode node, const int data)
  2. {
  4.     if (node == NULL)
  5.     {
  6.         node = createTreeNode(data);
  7.     }
  8.     else if (node->data < data)
  9.     {
  10.         node->right = insert(node->right, data);
  11.     }
  12.     else if (node->data > data)
  13.     {
  14.         node->left = insert(node->left, data);
  15.     }
  16.     return node;
  17. }

遍历

先序遍历（preorder traversal）

  1. // 先序遍历
  2. void preOrder(PtrNode node){
  3.       if (node != NULL)
  4.     {
  5.         printf(" node data = %d\n", node->data);
  6.         preOrder(node->left);
  7.         preOrder(node->right);
  8.     }
  9. }

中序遍历（inorder traversal）

  1. void inOrder(PtrNode node)
  2. {
  3.     if (node != NULL)
  4.     {
  5.         inOrder(node->left);
  6.         printf(" node data = %d\n", node->data);
  7.         inOrder(node->right);
  8.     }
  9. }

后序遍历 (postorder traversal)

  1. // 后续遍历
  2. void postOrder(PtrNode node)
  3. {
  4.     if (node != NULL)
  5.     {
  6.         postOrder(node->left);
  7.         postOrder(node->right);
  8.         printf(" node data = %d\n", node->data);
  9.     }
  10. };

层序遍历(levelorder traversal) 也是树的深度优先搜索（Breadth-first search）

  1. 使用函数打印层级 ```c // 层序遍历 也是 BFS void levelorder(PtrNode node); // 打印当前层级 void currentLevel(PtrNode node, int level);

// 获取高度 int height(PtrNode node);

// 层序遍历 void levelorder(PtrNode node) { int h = height(node); int i; for (i = 0; i < h; i++) { / code / currentLevel(node, i); } }

void currentLevel(PtrNode node, int level) { if (node != NULL) { if (level == 1) { printf(“level order data = %d\n”, node->data); } else if (level > 1) {

  1.         currentLevel(node->left, level - 1);
  2.         currentLevel(node->right, level - 1);
  3.     }
  4. }

};

int height(PtrNode node) { if (node == NULL) { return 0; }; int leftHeight = height(node->left); int rightHeight = height(node->right); // 获取较大的值 if (leftHeight > rightHeight) { return leftHeight + 1; } return rightHeight + 1; }

  2. 2. 使用队列辅助
  3. ```java
  4.    private void levelOrder(BinaryTreeNode root) {
  5.         Queue<BinaryTreeNode> dQueue = new LinkedList<>();
  6.         dQueue.add(root);
  7.         while (!dQueue.isEmpty()) {
  8.             BinaryTreeNode node = dQueue.poll();
  9.             System.out.println("data  = " + node.data);
  10.             if (node.left != null) {
  11.                 dQueue.add(node.left);
  12.             }
  13.             if (node.right != null) {
  14.                 dQueue.add(node.right);
  15.             }
  16.         }
  17.     }

二叉搜索树（Binary Search Tree）

一颗二叉搜索树是一颗二叉树，他可以为空，如果他不为空那么它满足下述的条件：
1.每个元素都有一个键值，并且所有的键值不相同
2.左子树（如果有）的键值都小于树根的键值
3.右子树（如果有）的键值都大于树根的键值
4.左右子树也都是二叉搜索树
一种对已排序数据进行快速搜索、插入、删除的树

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. typedef struct TreeNode BinaryTreeNode;
  4. typedef BinaryTreeNode *PtrNode;
  5. typedef BinaryTreeNode *Position;
  6. typedef BinaryTreeNode *SearchTree;
  8. struct TreeNode
  9. {
  10.     /* data */
  11.     int data;
  12.     PtrNode left;
  13.     PtrNode right;
  14. };
  15. PtrNode createTreeNode(const int data)
  16. {
  17.     PtrNode node;
  18.     node = (PtrNode)malloc(sizeof(node));
  19.     if (node == NULL)
  20.     {
  21.         printf("内存分配失败\n");
  22.         exit(EXIT_FAILURE);
  23.     }
  24.     node->left = node->right = NULL;
  25.     node->data = data;
  26.     return node;
  27. };
  29. // 查找指定数据的节点
  30. Position find(int x,SearchTree tree);
  31. // 获取最小节点
  32. Position findMin(SearchTree tree);
  33. // 获取最大节点
  34. Position findMax(SearchTree tree);
  35. // 插入
  36. SearchTree insert(int x,SearchTree tree);
  37. // 删除指定元素
  38. SearchTree deleteEl(int x,SearchTree tree);

查找

  1. //利用递归查找指定元素
  2. Position find(int x, SearchTree tree)
  3. {
  4.     if (tree == NULL)
  5.     {
  6.         return NULL;
  7.     }
  8.     if (x < tree->data)
  9.     {
  10.         return find(x, tree->left);
  11.     }
  12.     else if (x > tree->data)
  13.     {
  14.         return find(x, tree->right);
  15.     }
  16.     return tree;
  17. }

查找最小

  1. // 递归查找左节点 为最小
  2. Position findMin(SearchTree tree)
  3. {
  4.     if (tree == NULL)
  5.         return NULL;
  6.     if (tree->left == NULL)
  7.         return tree;
  8.     return findMin(tree->left);
  9. }

查找最大

  1. // 循环查找右节点 为最大
  2. Position findMax(SearchTree tree)
  3. {
  4.     if (tree != NULL)
  5.     {
  6.         while (tree->right != NULL)
  7.         {
  8.             tree = tree->right;
  9.         }
  10.     }
  11.     return tree;
  12. }

插入

  1. // 插入数据
  2. SearchTree insert(int data, SearchTree tree)
  3. {
  4.     if (tree == NULL)
  5.     {
  6.         tree = createTreeNode(data);
  7.     }
  8.     else if (tree->data < data)
  9.     {
  10.         tree->right = insert(data, tree->right);
  11.     }
  12.     else if (tree->data > data)
  13.     {
  14.         tree->left = insert(data, tree->left);
  15.     }
  16.     return tree;
  17. }

删除

  1. SearchTree deleteEl(int x, SearchTree tree)
  2. {
  3.     Position temp;
  4.     if (tree != NULL)
  5.     {
  6.         // 二分查找
  7.         if (tree->data > x)
  8.         {
  9.             tree->left = deleteEl(x, tree->left);
  10.         }
  11.         else if (tree->data < x)
  12.         {
  13.             tree->right = deleteEl(x, tree->right);
  14.         }
  15.         // 要删除的节点 两个子节点都不为空
  16.         else if (tree->left && tree->right)
  17.         {
  18.             /* 找到最小的右侧子节点 替换到当前位置 */
  19.             temp = findMin(tree->right);
  20.             tree->data = temp->data;
  21.             // 再将最小节点的删除
  22.             tree->right = deleteEl(tree->data, tree->right);
  23.         }
  24.         else
  25.         {
  26.             // 这里可能是只有一个节点或者0个节点
  27.             temp = tree;
  28.             if (tree->left == NULL)
  29.             {
  30.                 tree = tree->right;
  31.             }
  32.             else if (tree->right == NULL)
  33.             {
  34.                 tree = tree->left;
  35.             }
  36.             free(temp);
  37.         }
  38.     }
  39.     return tree;
  40. }