树 Tree

• 考虑结点K。根A到结点K的唯一路径上的任意结点,称为结点K的祖先。如结点B是结点K的祖先,而结点K是结点B的子孙。路径上最接近结点K的结点E称为K的双亲,而K为结点E的孩子。根A是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟,如结点K和结点L有相同的双亲E,即K和L为兄弟。
  

• 树中一个结点的孩子个数称为该结点的度,树中结点的最大度数称为树的度。如结点B的度为2,结点D的度为3,树的度为3。
  

• 度大于0的结点称为分支结点(又称非终端结点);度为0(没有子女结点)的结点称为叶子结点(又称终端结点)。在分支结点中,每个结点的分支数就是该结点的度。
  

• 结点的深度、高度和层次。
  

• 结点的层次从树根开始定义,根结点为第1层,它的子结点为第2层,以此类推。双亲在同一层的结点互为堂兄弟,图中结点G与E,F,H,I,J互为堂兄弟。
  

• 结点的深度是从根结点开始自顶向下逐层累加的。
  

• 结点的高度是从叶结点开始自底向上逐层累加的。
  

• 树的高度(或深度)是树中结点的最大层数。图中树的高度为4。
  

• 有序树和无序树。树中结点的各子树从左到右是有次序的,不能互换,称该树为有序树,否则称为无序树。假设图为有序树,若将子结点位置互换,则变成一棵不同的树。
  

• 路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的,而路径长度是路径上所经过的边的个数。
  

• 注意:由于树中的分支是有向的,即从双亲指向孩子,所以树中的路径是从上向下的,同一双亲的两个孩子之间不存在路径。
  

• 森林。森林是m (m≥0)棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。反之，只要给m棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林就变成了树。
  

    void BST::PreOrder(BstNode* root)
    {
    	if (root == NULL) {
    		return;
    	}
    	cout << root->data<<"\t";
    	PreOrder(root->left);
    	PreOrder(root->right);
    }


    void BST::InOrder(BstNode* root)
    {
    	if (root == NULL) {
    		return;
    	}

    	InOrder(root->left);
    	cout << root->data << "\t";
    	InOrder(root->right);
    }

    void BST::PostOrder(BstNode* root)
    {
    	if (root == NULL) {
    		return;
    	}

    	PostOrder(root->left);
    	PostOrder(root->right);
    	cout << root->data << "\t";
    }

int maxValue(BstNode* root)
{
    int max = root->data;
    if(root->left != NULL)
    {
        int maxLeft = maxValue(root->left);
        max = max > maxLeft ? max : maxLeft;
    }
    if(root->right != NULL)
    {
        int maxRight = maxValue(root->right);
        max = max > maxRight ? max : maxRight;
    }
    return max;
}

int minValue(BstNode* root)
{
    int min = root->data;
    if(root->left != NULL)
    {
        int minLeft = maxValue(root->left);
        min = min < minLeft ? min : minLeft;
    }
    if(root->right != NULL)
    {
        int minRight = maxValue(root->right);
        min = min < minRight ? min : minRight;
    }
    return min;
}

bool isBST(BstNode* root)
{
    if(root == NULL)
        return true;
    if(root->left != NULL && maxValue(root->left) > root->data)
        return false;
    if(root->right != NULL && minValue(root->right) < root->data)
        return false;
    return isBST(root->left) && isBST(root->right);
}

void BST::InOrder(BstNode* root, vector<int>& v)
{
	if (root == NULL) {
		return;
	}

	InOrder(root->left,v);
	v.push_back(root->data);
	InOrder(root->right,v);
}

bool BST::isBST(BstNode* root)
{
    vector<int> inorder;
	InOrder(root,inorder);
	for (int i = 1; i < inorder.size(); ++i)
		if (inorder[i - 1] >= inorder[i])
			return false;
	return true;
}

bool isBST(BstNode* root)
{
    static BstNode* prev;
    if(root != NULL)
    {
        if(!isBST(root->left))
            return false;
        if(prev != NULL && root->data < prev->data)
            return false;
        prev = root;
        if(!isBST(root->right))
            return false;
    }
    return true;
}

   void BST::deleteNode(BstNode*& node, int data)
  {
  	if (node == nullptr) {
  		return; // 如果树为空，直接返回
  	}

  	if (data < node->data) {
  		deleteNode(node->left, data); // 在左子树中寻找要删除的节点
  	}
  	else if (data > node->data) {
  		deleteNode(node->right, data); // 在右子树中寻找要删除的节点
  	}
  	else {
  		// 找到了要删除的节点
  		if (node->left == nullptr && node->right == nullptr) {
  			delete node;
  			node = nullptr; // 删除叶子节点
  		}
  		else if (node->left == nullptr) {
  			BstNode* temp = node;
  			node = node->right;
  			delete temp; // 删除只有右子节点的节点
  		}
  		else if (node->right == nullptr) {
  			BstNode* temp = node;
  			node = node->left;
  			delete temp; // 删除只有左子节点的节点
  		}
  		else {
  			// 删除有两个子节点的节点
  			BstNode* successor = node->right;
  			//找到右子树中最小的值
  			while (successor->left != nullptr) {
  				successor = successor->left;
  			}
  			node->data = successor->data; // 将后继节点的值复制到要删除的节点
  			deleteNode(node->right, successor->data); // 递归删除后继节点
  		}
  	}
  }

BstNode* findSuccessor(BstNode* root, BstNode* node)
{
    if (node->right != nullptr) {
        // 如果节点有右子树，后继节点为右子树中的最小节点
        return findMin(node->right);
    }

    BstNode* successor = nullptr;
    while (root != nullptr) {
        if (node->data < root->data) {
            successor = root;
            root = root->left;
        } else if (node->data > root->data) {
            root = root->right;
        } else {
            break;
        }
    }

    return successor;
}