[关闭]
@songpfei 2016-05-20T11:15:50.000000Z 字数 6658 阅读 2242

二叉树

数据结构

1.概述

定义：树是一个或多个节点的有效集合，且其中：

2 二叉树

2.1基本概念

  1. 定义：二叉树（binary tree)是有限多个节点的集合，这个集合或者空集，或者 由一个根节点和两颗互不相交的、分别称为左子树和右子树组成。

  2. 二叉树的性质：

    • 在二叉树中，第i层的节点数最多为；
    • 在深度为k的二叉树中，节点总数最多为；
      叶子节点的个数与度为2的节点n_2个数之间的关系为：

  3. 满二叉树（full binary tree):是深度为k的满二叉树是具有个节点的二叉树，除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树

  4. 完全二叉树：若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

2. 2二叉树的存储表示

  1. 数组存储表示：对节点从1到n进行编号，因此可以使用一个一维数组来存储这些点。
    引理：对于一课n个节点的完全二叉树（深度）采用顺序存储 表示，那么对于任意一个下标为i节点有：
    • 若，则其父节点parent(i)的编号为i/2;若i=1,则i是根节点；
    • 若，则其左孩子为2i;
    • 若,则其右孩子为2i+1;
  2. 链式存储:
    树的头结点定义：
  1. typedef int ElementType;
  2. typedef struct BinaryTreeNode BinTree;
  3. struct BinaryTreeNode
  4. {
  5.     ElementType data;
  6.     BinaryTreeNode* left;
  7.     BinaryTreeNode* right;
  8. };

2.3 二叉树的遍历

三种遍历：
- LVR:中序遍历（inoder);
- LRV:后续遍历（postorder);
- VLR:前序遍历（preoeder）;

表达式树：表达式树的树叶是操作数，常数或变量，二其他的节点为操作符(operator)，表达式三种遍历顺序与表达式的中缀(infix)、后缀（postfix)和前缀（prefix)形式之间存在一种自然的对应关系。
代码实现：

  1. #ifndef BINARYTREE_H
  2. #define BINARYTREE_H
  4. typedef int ElementType;
  5. struct BinaryTreeNode
  6. {
  7.     ElementType data;
  8.     BinaryTreeNode* left;
  9.     BinaryTreeNode* right;
  10. };
  12. void PreOrder(BinaryTreeNode* pRoot);//前序遍历
  13. void PostOrder(BinaryTreeNode* pRoot);//后续遍历
  14. void InOrder(BinaryTreeNode* pRoot);//中序遍历
  15. void LevelOrder(BinaryTreeNode* pRoot);//层序遍历
  16. #endif
  1. #include"BinaryTree.h"
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<queue>
  5. /*1.递归的实现二叉树的遍历*/
  6. //前序遍历
  7. void PreOrder(BinaryTreeNode* pRoot)
  8. {
  9.     if (pRoot == NULL)
  10.         return;
  11.     printf("%d ", pRoot->data);
  12.     PreOrder(pRoot->left);
  13.     PreOrder(pRoot->right);
  14. }
  16. //后续遍历
  17. void PostOrder(BinaryTreeNode* pRoot)
  18. {
  19.     if (pRoot == NULL)
  20.         return;
  21.     PreOrder(pRoot->left);
  22.     PreOrder(pRoot->right);
  23.     printf("%d ", pRoot->data);
  25. }
  28. //中序遍历
  29. void InOrder(BinaryTreeNode* pRoot)
  30. {
  31.     if (pRoot == NULL)
  32.         return;
  33.     PreOrder(pRoot->left);
  34.     printf("%d ", pRoot->data);
  35.     PreOrder(pRoot->right);
  36. }
  38. //层序遍历
  39. void LevelOrder(BinaryTreeNode* pRoot)
  40. {
  41.     if (pRoot == NULL)
  42.         return;
  43.     std::queue<BinaryTreeNode*> tree_node_queue;
  44.     tree_node_queue.push(pRoot);
  45.     while (tree_node_queue.size()>0)
  46.     {
  47.         pRoot = tree_node_queue.front();
  48.         tree_node_queue.pop();
  49.         printf("%d ", pRoot->data);
  50.         if (pRoot->left != NULL)
  51.             tree_node_queue.push(pRoot->left);
  52.         if (pRoot->right != NULL)
  53.             tree_node_queue.push(pRoot->right);
  54.     }
  55. }

3. 二叉搜索树

3.1 概述

3.2 二叉搜索树的各种操作

  1. #ifndef BINARYTREE_H
  2. #define BINARYTREE_H
  4. typedef int ElementType;
  5. struct BinaryTreeNode
  6. {
  7.     ElementType data;
  8.     BinaryTreeNode* left;
  9.     BinaryTreeNode* right;
  10. };
  12. void PreOrder(BinaryTreeNode* pRoot);//前序遍历
  13. void PostOrder(BinaryTreeNode* pRoot);//后续遍历
  14. void InOrder(BinaryTreeNode* pRoot);//中序遍历
  15. void LevelOrder(BinaryTreeNode* pRoot);//层序遍历
  16. BinaryTreeNode* BinaryTreeSearchRecursive(BinaryTreeNode* pRoot, ElementType key);//二叉搜索树查找（递归）
  17. BinaryTreeNode* BinaryTreeSearch(BinaryTreeNode* pRoot, ElementType key);//二叉搜索树查找（迭代）
  18. bool BinaryTreeInsert(BinaryTreeNode* &pRoot, ElementType key);//二叉树节点插入
  19. bool BinaryTreeDelete(BinaryTreeNode* &pRoot, ElementType key);//二叉树节点删除
  21. #endif
  1. #include"BinaryTree.h"
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<queue>
  5. /*1.递归的实现二叉树的遍历*/
  6. //前序遍历
  7. void PreOrder(BinaryTreeNode* pRoot)
  8. {
  9.     if (pRoot == NULL)
  10.         return;
  11.     printf("%d ", pRoot->data);
  12.     PreOrder(pRoot->left);
  13.     PreOrder(pRoot->right);
  14. }
  16. //后续遍历
  17. void PostOrder(BinaryTreeNode* pRoot)
  18. {
  19.     if (pRoot == NULL)
  20.         return;
  21.     PreOrder(pRoot->left);
  22.     PreOrder(pRoot->right);
  23.     printf("%d ", pRoot->data);
  25. }
  28. //中序遍历
  29. void InOrder(BinaryTreeNode* pRoot)
  30. {
  31.     if (pRoot == NULL)
  32.         return;
  33.     PreOrder(pRoot->left);
  34.     printf("%d ", pRoot->data);
  35.     PreOrder(pRoot->right);
  36. }
  38. //层序遍历
  39. void LevelOrder(BinaryTreeNode* pRoot)
  40. {
  41.     if (pRoot == NULL)
  42.         return;
  43.     std::queue<BinaryTreeNode*> tree_node_queue;
  44.     tree_node_queue.push(pRoot);
  45.     while (tree_node_queue.size() > 0)
  46.     {
  47.         pRoot = tree_node_queue.front();
  48.         tree_node_queue.pop();
  49.         printf("%d ", pRoot->data);
  50.         if (pRoot->left != NULL)
  51.             tree_node_queue.push(pRoot->left);
  52.         if (pRoot->right != NULL)
  53.             tree_node_queue.push(pRoot->right);
  54.     }
  55. }
  57. //二叉搜索树查找(递归）
  58. BinaryTreeNode* BinaryTreeSearchRecursive(BinaryTreeNode* pRoot, ElementType key)
  59. {
  60.     if (pRoot == NULL || key == pRoot->data)
  61.         return pRoot;
  62.     if (key < pRoot->data)
  63.         return BinaryTreeSearchRecursive(pRoot->left, key);
  64.     else
  65.         return BinaryTreeSearchRecursive(pRoot->right, key);
  66. }
  68. //二叉搜索树查找（迭代）时间复杂度：o(h)
  69. BinaryTreeNode* BinaryTreeSearch(BinaryTreeNode* pRoot, ElementType key)
  70. {
  71.     while (pRoot != NULL && key != pRoot->data)
  72.     {
  73.         if (key < pRoot->data)
  74.             pRoot = pRoot->left;
  75.         else
  76.             pRoot = pRoot->right;
  77.     }
  78.     return pRoot;
  79. }
  80. //二叉树插入
  81. bool BinaryTreeInsert(BinaryTreeNode* &pRoot, ElementType key)
  82. {
  83.     BinaryTreeNode* pParent = NULL;
  84.     BinaryTreeNode* pNode = pRoot;
  85.     while (pNode != NULL&&pNode->data != key)
  86.     {
  87.         pParent = pNode;
  88.         if (key < pNode->data)
  89.             pNode = pNode->left;
  90.         else
  91.             pNode = pNode->right;
  92.     }
  93.     if (pNode != NULL)//key已经存在
  94.         return false;
  95.     BinaryTreeNode* pNodeInsert = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
  96.     if (pNodeInsert == NULL)//内存申请失败
  97.         return false;
  98.     pNodeInsert->data = key;
  99.     pNodeInsert->left = pNodeInsert->right = NULL;
  101.     if (pParent == NULL)//树为空，新插入的节点为根节点
  102.         pRoot = pNodeInsert;
  103.     else if (key < pParent->data)
  104.         pParent->left = pNodeInsert;
  105.     else
  106.         pParent->right = pNodeInsert;
  107.     return true;
  108. }
  110. //二叉树节点删除
  111. bool BinaryTreeDelete(BinaryTreeNode* &pRoot, ElementType key)
  112. {
  113.     BinaryTreeNode *pNext, *pFather = NULL;
  114.     BinaryTreeNode* pNode = pRoot;
  115.     int pos = 0;//待删除节点的位置，0代表根节点，-1代表左节点，1代表右节点
  116.     while (pNode != NULL&&pNode->data != key)
  117.     {
  118.         pFather = pNode;
  119.         if (key < pNode->data)
  121.         {
  122.             pos = -1;
  123.             pNode = pNode->left;
  124.         }
  125.         else
  126.         {
  127.             pos = 1;
  128.             pNode = pNode->right;
  129.         }
  130.     }
  131.     if (pNode == NULL)//节点不存在
  132.         return false;
  133.     if (pNode->left != NULL&&pNode->right != NULL)//待删除的节点有两个孩子
  134.     {
  135.         pFather = pNode;
  136.         pos = -1;
  137.         pNext = pNode->left;//用其左树中的最大元素替代删除元素
  138.         while (pNext->right != NULL)
  139.         {
  140.             pos = 1;
  141.             pFather = pNext;
  142.             pNext = pNext->right;
  143.         }
  144.         pNode->data = pNext->data;//替换
  145.         pNode = pNext;//更新需要删除的元素
  146.     }
  148.     if (pNode->left != NULL)//待删除节点只有左孩子
  149.         pNext = pNode->left;
  150.     else if (pNode->right != NULL)//只有右节点
  151.         pNext = pNode->right;
  152.     else                //待删除节点没有孩子
  153.         pNext = NULL;
  154.     if (pos == 0)//待删除节点为根节点
  155.         pRoot = pNext;
  156.     else if (pos == -1)//待删除节点为左孩子
  157.         pFather->left = pNext;
  158.     else                         //待删除节点为右孩子
  159.         pFather->right = pNext;
  161.     delete pNode;//删除节点
  162.     pNode = NULL;
  163.     return true;
  164. }
  1. #include"BinaryTree.h"
  2. #include<stdlib.h>
  3. #include<stdio.h>
  5. int main()
  6. {
  7.     BinaryTreeNode* pRootNode = NULL;
  8.     BinaryTreeNode* pFind;
  9.     BinaryTreeInsert(pRootNode, 30);
  10.     BinaryTreeInsert(pRootNode, 5);
  11.     BinaryTreeInsert(pRootNode, 2);
  12.     BinaryTreeInsert(pRootNode, 40);
  13.     BinaryTreeInsert(pRootNode, 35);
  14.     BinaryTreeInsert(pRootNode, 80);
  15.     BinaryTreeInsert(pRootNode, 32);
  16.     BinaryTreeInsert(pRootNode, 38);
  18.     PreOrder(pRootNode);
  19.     printf("1.前序遍历\n");
  21.     InOrder(pRootNode);
  22.     printf("2.中序遍历\n");
  24.     PostOrder(pRootNode);
  25.     printf("3.后序遍历\n");
  27.     LevelOrder(pRootNode);
  28.     printf("4.层序遍历\n");
  30.     pFind = BinaryTreeSearch(pRootNode, 35);
  31.     if (pFind)
  32.         printf("5.找到的节点为：%d\n", pFind->data);
  33.     else
  34.         printf("5.未找到节点");
  36.     pFind = BinaryTreeSearchRecursive(pRootNode, 33);
  37.     if (pFind)
  38.         printf("6.找到的节点为：%d\n", pFind->data);
  39.     else
  40.         printf("6.未找到节点\n");
  41.     if (BinaryTreeInsert(pRootNode, 33))
  42.     {
  43.         printf("7.插入成功\n");
  44.         LevelOrder(pRootNode);
  45.     }
  46.     if (BinaryTreeDelete(pRootNode, 33))
  47.     {
  48.         printf("8.删除成功\n");
  49.         LevelOrder(pRootNode);
  50.     }
  51.     if (BinaryTreeDelete(pRootNode, 35))
  52.     {
  53.         printf("8.删除成功\n");
  54.         LevelOrder(pRootNode);
  55.     }
  56.     return 0;
  57. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注