@Lin--
2020-02-15T10:18:30.000000Z
字数 10813
阅读 235
DataStruct
每个节点至多有两个孩子,且左孩子的值小于自己,右孩子的值大于自己。
struct BST{
int value;
struct BST * right;
struct BST * left;
};
//build a binary tree (root)
struct BST* BuildBSTNode(int v)
{
struct BST* node=(struct BST *)malloc(sizeof(struct BST));
node->value=v;
node->left=NULL;
node->right=NULL;
return node;
}
//insert BSTNode
void InsertBSTNode(struct BST * root,struct BST * node)
{
if(node->value<root->value&&root->left==NULL)
{root->left=node;}
if(node->value>root->value&&root->right==NULL)
{root->right=node;}
if(node->value<root->value&&root->left!=NULL)
{InsertBSTNode(root->left,node);}
if(node->value>root->value&&root->right!=NULL)
{InsertBSTNode(root->right,node);}
}
//Find a Node whether in a tree
bool FindNode(struct BST *root,int v)
{
if(root==NULL){return false;}
if(v==root->value)
{return true;}
else if(v<root->value)
{return FindNode(root->left,v);}
else
{return FindNode(root->right,v);}
}
//Find a node's parent in a tree
struct BST * FindParent(struct BST * root,int v)
{
if(root->value==v){return NULL;}
if(v<root->value)
{
if(v==root->left->value){return root;}
else{return FindParent(root->left,v);}
}
else
{
if(v==root->right->value){return root;}
else{return FindParent(root->right,v);}
}
}
结点有三种情况:
直接删除
//结点为叶子结点,左右子树为空。直接删除
if(pre->left==NULL&&pre->right==NULL)
{
if(parent->left!=NULL&&parent->left->value==v)
{
free(parent->left);parent->left=NULL;
free(pre);
pre=NULL;
}
else
{
free(parent->right);parent->right=NULL;
free(pre);
pre=NULL;
}
}
将其父节点指向待删结点的指针,指向待删结点的单子
//左子树为空,右子树不空。将该节点的父节点连接其右子树
else if(pre->left==NULL&&pre->right!=NULL)
{
//该节点是父亲节点的左子树
if(parent->left->value==v)
{
parent->left=pre->right;
free(pre);pre=NULL;
}
//该节点是父节点的右子树
else
{
parent->right=pre->right;
free(pre);pre=NULL;
}
}
//右子树为空,左子树不空。将该节点的父节点连接其左子树
else if(pre->left!=NULL&&pre->right==NULL)
{
//该节点是父亲节点的左子树
if(parent->left->value==v)
{
parent->left=pre->left;
free(pre);pre=NULL;
}
//该节点是父节点的右子树
else
{
parent->right=pre->left;
free(pre);pre=NULL;
}
}
自己的值替换成右子树中,最小的值(最左边那个结点),然后将那个被替代的结点删除。
//左右子树都不空,取右子树中最左的结点代替后删除
else
{
struct BST * temp=&(*pre->right),* tempparent=&(*pre);
//找到最左的结点
while(temp->left!=NULL)
{tempparent=temp;temp=temp->left;}
//最左结点是叶子结点
if(temp->right==NULL)
{
pre->value=temp->value;//替换到待删结点
free(pre->right);pre->right=NULL;
free(temp);temp=NULL;
}
//若最左结点还有右子树
else
{
pre->value=temp->value;
if(tempparent->value==pre->value)
{pre->right=temp->right;free(temp);temp=NULL;}
else
{
tempparent->left=temp->right;
free(temp);temp=NULL;
}
}
}
//delete a node in a tree
bool DeleteNode(struct BST *parent,struct BST *pre,int v)
{
//找不到被删结点
if(pre==NULL){return false;}
//找得到或还没找到
else
{
//待删结点小于当前节点,树往左走
if(v<pre->value)
{
return DeleteNode(&(*pre),(&*pre)->left,v);
}
//待删结点大于当前节点,树往右走
else if(v>pre->value)
{
return DeleteNode(&(*pre),(&*pre)->right,v);
}
//找到待删结点
else
{
//结点为叶子结点,左右子树为空。直接删除
if(pre->left==NULL&&pre->right==NULL)
{
if(parent->left!=NULL&&parent->left->value==v)
{
free(parent->left);parent->left=NULL;
free(pre);
pre=NULL;
}
else
{
free(parent->right);parent->right=NULL;
free(pre);
pre=NULL;
}
}
//左子树为空,右子树不空。将该节点的父节点连接其右子树
else if(pre->left==NULL&&pre->right!=NULL)
{
//该节点是父亲节点的左子树
if(parent->left->value==v)
{
parent->left=pre->right;
free(pre);pre=NULL;
}
//该节点是父节点的右子树
else
{
parent->right=pre->right;
free(pre);pre=NULL;
}
}
//右子树为空,左子树不空。将该节点的父节点连接其左子树
else if(pre->left!=NULL&&pre->right==NULL)
{
//该节点是父亲节点的左子树
if(parent->left->value==v)
{
parent->left=pre->left;
free(pre);pre=NULL;
}
//该节点是父节点的右子树
else
{
parent->right=pre->left;
free(pre);pre=NULL;
}
}
//左右子树都不空,取右子树中最左的结点代替后删除
else
{
struct BST * temp=&(*pre->right),* tempparent=&(*pre);
//找到最左的结点
while(temp->left!=NULL)
{tempparent=temp;temp=temp->left;}
//最左结点是叶子结点
if(temp->right==NULL)
{
pre->value=temp->value;//替换到待删结点
free(pre->right);pre->right=NULL;
free(temp);temp=NULL;
}
//若最左结点还有右子树
else
{
pre->value=temp->value;
if(tempparent->value==pre->value)
{pre->right=temp->right;free(temp);temp=NULL;}
else
{
tempparent->left=temp->right;
free(temp);temp=NULL;
}
}
}
return true;
}
}
}
//visit a tree LevelOrder
void LevelOrder(struct BST *root)
{
queue<struct BST*> Q;
Q.push(root);
while(Q.empty()!=true)
{
printf("%d ",Q.front()->value);
if(Q.front()->left!=NULL)
{
Q.push(Q.front()->left);
}
if(Q.front()->right!=NULL)
{
Q.push(Q.front()->right);
}
Q.pop();
}
}
先访问(打印),后进入子树
//visit a tree PreOrder
void PreOrderBST(struct BST * root)
{
if(root!=NULL)
{
printf("%d ",root->value);
PreOrderBST(root->left);
PreOrderBST(root->right);
}
}
//visit a tree PreOrder without recursion
void PreOrderBSTStack(struct BST * root)
{
if(root==NULL){return;}
stack<struct BST*> S;
S.push(root);
while(S.empty()!=true)
{
struct BST *temp=&(*S.top());
printf("%d ",temp->value);
S.pop();
if(temp->right!=NULL)
{
S.push(temp->right);
}
if(temp->left!=NULL)
{
S.push(temp->left);
}
free(temp);
}
}
//visit a tree InOrder
void InOrderBST(struct BST * root)
{
if(root!=NULL)
{
InOrderBST(root->left);
printf("%d ",root->value);
InOrderBST(root->right);
}
}
中序遍历的顺序是:左->中/根->右。
具体做法是:用一个栈,将左子树一压到底,直到没有左子树,即遇到最左结点,此时便pop出来同时打印,pop出来时,看看其有没有右子树,有的话再push它的右子树。以此循环,直到栈空。
那么对于栈中的结点有两种情况:一是左子树还没压进来,二是左子树已经pop出去了,而这两种情况栈中都没有左子树,所以需要用字典标记当前节点的左子树是否已经是pop出的。
//visit a tree InOrder without recursion
void InOrderBSTStack(struct BST *root)
{
stack<struct BST*> S;
map<struct BST*,bool> dict;
S.push(root);dict[root]=false;
while(S.empty()!=true)
{
struct BST *temp=&(*S.top());
if(temp->left!=NULL&&dict[temp]!=true)
{
S.push(temp->left);
dict[temp]=true;
continue;
}
printf("%d ",temp->value);
S.pop();
if(temp->right!=NULL)
{
S.push(temp->right);
continue;
}
free(temp);
}
}
//visit a tree PostOrder
void PostOrderBST(struct BST * root)
{
if(root!=NULL)
{
PostOrderBST(root->left);
PostOrderBST(root->right);
printf("%d ",root->value);
}
}
后续遍历的打印顺序是左->右->根。
而且结点要输出会有两种情况:
一是该节点是一个叶子结点,二是该节点的孩子结点都已经输出了。
也就是说,对于一个有子节点的的结点来说,它的子节点要么还没进栈,要么已经输出,而这两种情况栈中都没有它的子节点的存在,所以需要有一个标记来区分一个结点它的子节点是否已经输出。所以,出了一个栈外,还需要有一个字典来存储结点与输出与否之间的映射关系。
//visit a tree PostOrder without recursion
void PostOrderBSTStack(struct BST * root)
{
if(root==NULL){return ;}
map<struct BST *,bool> dict;
stack<struct BST *> S;
S.push(root);dict[root]=false;
while(S.empty()!=true)
{
struct BST *temp=&(*S.top());
if((temp->left==NULL&&temp->right==NULL)||dict[temp]==true)
{
printf("%d ",temp->value);
S.pop();
free(temp);
continue;
}
if(temp->right!=NULL&&dict[temp]!=true)
{
S.push(temp->right);
}
if(temp->left!=NULL&&dict[temp]!=true)
{
S.push(temp->left);
}
dict[temp]=true;
}
}
#include<iostream>
#include<queue>
#include<stack>
#include<map>
using namespace std;
struct BST{
int value;
struct BST * right;
struct BST * left;
};
//build a binary tree (root)
struct BST* BuildBSTNode(int v)
{
struct BST* node=(struct BST *)malloc(sizeof(struct BST));
node->value=v;
node->left=NULL;
node->right=NULL;
return node;
}
//visit a tree PreOrder
void PreOrderBST(struct BST * root)
{
if(root!=NULL)
{
printf("%d ",root->value);
PreOrderBST(root->left);
PreOrderBST(root->right);
}
}
//visit a tree PreOrder without recursion
void PreOrderBSTStack(struct BST * root)
{
if(root==NULL){return;}
stack<struct BST*> S;
S.push(root);
while(S.empty()!=true)
{
struct BST *temp=&(*S.top());
printf("%d ",temp->value);
S.pop();
if(temp->right!=NULL)
{
S.push(temp->right);
}
if(temp->left!=NULL)
{
S.push(temp->left);
}
free(temp);
}
}
//visit a tree InOrder
void InOrderBST(struct BST * root)
{
if(root!=NULL)
{
InOrderBST(root->left);
printf("%d ",root->value);
InOrderBST(root->right);
}
}
//visit a tree InOrder without recursion
void InOrderBSTStack(struct BST *root)
{
stack<struct BST*> S;
map<struct BST*,bool> dict;
S.push(root);dict[root]=false;
while(S.empty()!=true)
{
struct BST *temp=&(*S.top());
if(temp->left!=NULL&&dict[temp]!=true)
{
S.push(temp->left);
dict[temp]=true;
continue;
}
printf("%d ",temp->value);
S.pop();
if(temp->right!=NULL)
{
S.push(temp->right);
continue;
}
free(temp);
}
}
//visit a tree PostOrder
void PostOrderBST(struct BST * root)
{
if(root!=NULL)
{
PostOrderBST(root->left);
PostOrderBST(root->right);
printf("%d ",root->value);
}
}
//visit a tree PostOrder without recursion
void PostOrderBSTStack(struct BST * root)
{
if(root==NULL){return ;}
map<struct BST *,bool> dict;
stack<struct BST *> S;
S.push(root);dict[root]=false;
while(S.empty()!=true)
{
struct BST *temp=&(*S.top());
if((temp->left==NULL&&temp->right==NULL)||dict[temp]==true)
{
printf("%d ",temp->value);
S.pop();
free(temp);
continue;
}
if(temp->right!=NULL&&dict[temp]!=true)
{
S.push(temp->right);
}
if(temp->left!=NULL&&dict[temp]!=true)
{
S.push(temp->left);
}
dict[temp]=true;
}
}
//insert BSTNode
void InsertBSTNode(struct BST * root,struct BST * node)
{
if(node->value<root->value&&root->left==NULL)
{root->left=node;}
if(node->value>root->value&&root->right==NULL)
{root->right=node;}
if(node->value<root->value&&root->left!=NULL)
{InsertBSTNode(root->left,node);}
if(node->value>root->value&&root->right!=NULL)
{InsertBSTNode(root->right,node);}
}
//Find a Node whether in a tree
bool FindNode(struct BST *root,int v)
{
if(root==NULL){return false;}
if(v==root->value)
{return true;}
else if(v<root->value)
{return FindNode(root->left,v);}
else
{return FindNode(root->right,v);}
}
//Find a node's parent in a tree
struct BST * FindParent(struct BST * root,int v)
{
if(root->value==v){return NULL;}
if(v<root->value)
{
if(v==root->left->value){return root;}
else{return FindParent(root->left,v);}
}
else
{
if(v==root->right->value){return root;}
else{return FindParent(root->right,v);}
}
}
//delete a node in a tree
bool DeleteNode(struct BST *parent,struct BST *pre,int v)
{
//找不到被删结点
if(pre==NULL){return false;}
//找得到或还没找到
else
{
//待删结点小于当前节点,树往左走
if(v<pre->value)
{
return DeleteNode(&(*pre),(&*pre)->left,v);
}
//待删结点大于当前节点,树往右走
else if(v>pre->value)
{
return DeleteNode(&(*pre),(&*pre)->right,v);
}
//找到待删结点
else
{
//结点为叶子结点,左右子树为空。直接删除
if(pre->left==NULL&&pre->right==NULL)
{
if(parent->left!=NULL&&parent->left->value==v)
{
free(parent->left);parent->left=NULL;
free(pre);
pre=NULL;
}
else
{
free(parent->right);parent->right=NULL;
free(pre);
pre=NULL;
}
}
//左子树为空,右子树不空。将该节点的父节点连接其右子树
else if(pre->left==NULL&&pre->right!=NULL)
{
//该节点是父亲节点的左子树
if(parent->left->value==v)
{
parent->left=pre->right;
free(pre);pre=NULL;
}
//该节点是父节点的右子树
else
{
parent->right=pre->right;
free(pre);pre=NULL;
}
}
//右子树为空,左子树不空。将该节点的父节点连接其左子树
else if(pre->left!=NULL&&pre->right==NULL)
{
//该节点是父亲节点的左子树
if(parent->left->value==v)
{
parent->left=pre->left;
free(pre);pre=NULL;
}
//该节点是父节点的右子树
else
{
parent->right=pre->left;
free(pre);pre=NULL;
}
}
//左右子树都不空,取右子树中最左的结点代替后删除
else
{
struct BST * temp=&(*pre->right),* tempparent=&(*pre);
//找到最左的结点
while(temp->left!=NULL)
{tempparent=temp;temp=temp->left;}
//最左结点是叶子结点
if(temp->right==NULL)
{
pre->value=temp->value;//替换到待删结点
free(pre->right);pre->right=NULL;
free(temp);temp=NULL;
}
//若最左结点还有右子树
else
{
pre->value=temp->value;
if(tempparent->value==pre->value)
{pre->right=temp->right;free(temp);temp=NULL;}
else
{
tempparent->left=temp->right;
free(temp);temp=NULL;
}
}
}
return true;
}
}
}
//visit a tree LevelOrder
void LevelOrder(struct BST *root)
{
queue<struct BST*> Q;
Q.push(root);
while(Q.empty()!=true)
{
printf("%d ",Q.front()->value);
if(Q.front()->left!=NULL)
{
Q.push(Q.front()->left);
}
if(Q.front()->right!=NULL)
{
Q.push(Q.front()->right);
}
Q.pop();
}
}
int main ()
{
int a[16]={15,8,30,6,9,17,40,4,7,16,35,49,33,38,34,39};
struct BST * root=BuildBSTNode(a[0]);
for(int i=1;i<16;++i)
{
struct BST * node=BuildBSTNode(a[i]);
InsertBSTNode(root,node);
}
PostOrderBST(root);printf("\n");
PostOrderBSTStack(root);
}