二叉排序树的构建、遍历及结点删除

2024-07-04 02:10| 来源: 网络整理| 查看: 265

本文主要来讲解二叉排序树的构建、遍历（非递归实现）以及结点删除的算法。

1、构建二叉排序树 1.1引言

对于一个已经排序好的顺序表来说，进行查找其中的某个元素，采用二分查找的效率非常高，但是如果要插入或者删除元素的话，就可能要移动大量的元素。对链表进行插入和删除不需要移动元素，效率很高，但是链表不能进行二分查找。因此，如何来解决这个问题呢，这时就需要构建二叉排序树了。

1.2什么是二叉排序树

二叉排序树是一棵空树或者是满足下列条件的的二叉树： 1）若左子树不空，则左子树上所有节点的值均小于或等于它的根节点的值； 2）若右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值； 3）左、右子树也分别为二叉排序树。

1.3如何构建二叉排序树

以数据集第一个元素为根节点，之后将比根节点小的元素放在左子树中，将比根节点大的元素放在右子树中，在左右子树中同样采取此规则。那么在查找x时，若 x比根节点小可以排除右子树所有元素，去左子树中查找（类似二分查找），这样查找的效率非常好，而且插入的时间复杂度为O（h），h为树的高度，较O（n）来说效率提高不少。故二叉搜索树用作一些查找和插入使用频率比较高的场景。如下列数据：在这里插入图片描述构建的二叉排序树：

2、二叉树的遍历

以下将会讲解二叉树的前序遍历、中序遍历、后序遍历以及层序遍历，采用非递归的方式（由于递归实现较为容易，而且递归的效率很低，在此就不做讲解）。

2.1前序遍历

前序遍历 - 先访问根节点，然后前序遍历左子树，再前序遍历右子树在这里插入图片描述非递归方法需要用到一个栈来辅助遍历。代码如下：

void preVisit(BTree *root) { if (root == NULL) return; stack nodeStack; nodeStack.push(root); //先将根节点压入栈 const BTreeNode *tmp; while (!nodeStack.empty()) { tmp = nodeStack.top(); //弹出栈中结点，先访问 nodeStack.pop(); cout nodeStack.push(tmp->LChild); } } cout while (tmp != NULL) { nodeStack.push(tmp); tmp = tmp->LChild; } if (!nodeStack.empty()) { tmp = nodeStack.top(); nodeStack.pop(); cout root = nodeStack.top(); nodeStack.pop(); count = nodeNum.top(); nodeNum.pop(); if (count == 0) { nodeStack.push(root); nodeNum.push(1); if (root->LChild != NULL) { nodeStack.push(root->LChild); nodeNum.push(0); } } else if (count == 1) { nodeStack.push(root); nodeNum.push(2); if (root->RChild != NULL) { nodeStack.push(root->RChild); nodeNum.push(0); } } else if (count == 2) { cout root = queNode.front(); queNode.pop(); cout RChild != NULL) queNode.push(root->RChild); } cout parent = temp; if (temp->data > data) { temp = temp->LChild; RorL = LEFT; } else if (temp->data cout if (RorL == LEFT) parent->LChild = temp->RChild; else parent->RChild = temp->RChild; delete temp; } else if (temp->RChild == NULL) //要删除的结点只有左儿子 { if (RorL == LEFT) parent->LChild = temp->LChild; else parent->RChild = temp->LChild; delete temp; } else { BTreeNode *maxDataNode = temp->LChild; parent = temp; while (maxDataNode->RChild != NULL) { parent = maxDataNode; maxDataNode = maxDataNode->RChild; } temp->data = maxDataNode->data; if (parent->LChild == maxDataNode) { parent->LChild = maxDataNode->LChild; } else if (maxDataNode->LChild != NULL) { parent->RChild = maxDataNode->LChild; } else parent->RChild = NULL; delete maxDataNode; } return true; }

完整代码实现：

#include #include #include using namespace std; #define isLess(BTree1,BTree2) (BTree1->data < BTree2->data) typedef int DataType; enum isRorL { RIGHT, LEFT }; typedef struct BSTree { DataType data; BSTree *LChild; BSTree *RChild; }BTree,BTreeNode; bool insertBTree(BTree **root, BTreeNode *treeNode) { if (!treeNode) { return false; } else { treeNode->LChild = NULL; treeNode->RChild = NULL; } BTreeNode *parent = NULL; BTreeNode *temp = NULL; //bool LorR = true; //true 为左，false 为右 isRorL RorL = LEFT; if (!(*root)) { *root = treeNode; return true; } else { temp = *root; } while (temp) { parent = temp; if (isLess(treeNode, temp)) { RorL = LEFT; temp = temp->LChild; } else { temp = temp->RChild; RorL = RIGHT; } } if (RorL==LEFT) { parent->LChild = treeNode; } else { parent->RChild = treeNode; } return true; } bool deleteNode(BTree *root, DataType data) { if (root == NULL) return false; BTreeNode *parent; BTreeNode *temp = root; isRorL RorL = LEFT; //记录要删除的结点是左儿子还是右儿子 parent = temp; while (temp->data != data) { parent = temp; if (temp->data > data) { temp = temp->LChild; RorL = LEFT; } else if (temp->data cout if (RorL == LEFT) parent->LChild = temp->RChild; else parent->RChild = temp->RChild; delete temp; } else if (temp->RChild == NULL) //要删除的结点只有左儿子 { if (RorL == LEFT) parent->LChild = temp->LChild; else parent->RChild = temp->LChild; delete temp; } else { BTreeNode *maxDataNode = temp->LChild; parent = temp; while (maxDataNode->RChild != NULL) { parent = maxDataNode; maxDataNode = maxDataNode->RChild; } temp->data = maxDataNode->data; if (parent->LChild == maxDataNode) { parent->LChild = maxDataNode->LChild; } else if (maxDataNode->LChild != NULL) { parent->RChild = maxDataNode->LChild; } else parent->RChild = NULL; delete maxDataNode; } return true; } //前序遍历 void preVisit(BTree *root) { if (root == NULL) return; stack nodeStack; nodeStack.push(root); const BTreeNode *tmp; while (!nodeStack.empty()) { tmp = nodeStack.top(); nodeStack.pop(); cout nodeStack.push(tmp->LChild); } } cout while (tmp != NULL) { nodeStack.push(tmp); tmp = tmp->LChild; } if (!nodeStack.empty()) { tmp = nodeStack.top(); nodeStack.pop(); cout root = nodeStack.top(); nodeStack.pop(); count = nodeNum.top(); nodeNum.pop(); if (count == 0) { nodeStack.push(root); nodeNum.push(1); if (root->LChild != NULL) { nodeStack.push(root->LChild); nodeNum.push(0); } } else if (count == 1) { nodeStack.push(root); nodeNum.push(2); if (root->RChild != NULL) { nodeStack.push(root->RChild); nodeNum.push(0); } } else if (count == 2) { cout root = queNode.front(); queNode.pop(); cout RChild != NULL) queNode.push(root->RChild); } cout 19,7,25,5,11,15,21,61 }; for (int i = 0; i

【本文地址】

公司简介

联系我们