- 浏览: 115486 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
lehehe:
恩恩,不过我觉得用接口比较方便,http://www.haos ...
android WIFI定位 -
sunlok:
不错的功能,学习了!
android ListView根据字母排序和定位
六、二叉树的基本操作(非递归遍历)&二叉排序树的操作
接上一节第五部分,主要分析二叉树的非递归遍历和二叉排序树的操作。
1. 非递归中序遍历
//1.依次将根节点root的左子树入栈,直到lchild=NULL,执行2
//2.将栈的元素出栈、访问;将当前指针指向节点的rchild,循环遍历。直到栈空为止!
Cpp代码
template<typenameelemType>
voidbinaryTreeType<elemType>::noRecursionInorderTraversal() //非递归中序遍历
{
cout<< "noRecursionInorderTraversal--------------------------->"<< endl;
linkedStackType<nodeType<elemType>* > stack;
nodeType<elemType>*current = root;
while(current!= NULL || !stack.isEmptyStack()) //或者||
{
if(current!= NULL)
{
stack.push(current);
current= current->llink;
}
else
{
stack.pop(current);
cout<< current->info << "\t"; //出栈的时候访问节点
current= current->rlink;
}
}
cout<< endl;
cout<< "<------------------------noRecursionInorderTraversal"<< endl;
}
template<typenameelemType>
voidbinaryTreeType<elemType>::noRecursionInorderTraversal() //非递归中序遍历
{
cout<< "noRecursionInorderTraversal--------------------------->"<< endl;
linkedStackType<nodeType<elemType>* > stack;
nodeType<elemType>*current = root;
while(current!= NULL || !stack.isEmptyStack()) //或者||
{
if(current!= NULL)
{
stack.push(current);
current= current->llink;
}
else
{
stack.pop(current);
cout<< current->info << "\t"; //出栈的时候访问节点
current= current->rlink;
}
}
cout<< endl;
cout<< "<------------------------noRecursionInorderTraversal"<< endl;
}
2. 非递归先序遍历
//在中序遍历的基础上,访问次序发生变化;
//先序遍历,需要先逐个遍历根节点,然后依次处理其左、右孩子节点。
Cpp代码
template<typenameelemType>
voidbinaryTreeType<elemType>::noRecursionPreorderTraversal() //非递归前序遍历
{
cout<<"noRecursionPreorderTraversal--------------------------->"<< endl;
linkedStackType<nodeType<elemType>* > stack;
nodeType<elemType>*current = root;
while(current!= NULL || !stack.isEmptyStack()) //或者||
{
if(current!= NULL)
{
cout<< current->info << "\t"; //先访问节点后入栈
stack.push(current);
current= current->llink;
}
else
{
stack.pop(current);
current= current->rlink;
}
}
cout<< endl;
cout<< "<------------------------noRecursionPreorderTraversal"<< endl;
}
template<typenameelemType>
voidbinaryTreeType<elemType>::noRecursionPreorderTraversal() //非递归前序遍历
{
cout<<"noRecursionPreorderTraversal--------------------------->"<< endl;
linkedStackType<nodeType<elemType>* > stack;
nodeType<elemType>*current = root;
while(current!= NULL || !stack.isEmptyStack()) //或者||
{
if(current!= NULL)
{
cout<< current->info << "\t"; //先访问节点后入栈
stack.push(current);
current= current->llink;
}
else
{
stack.pop(current);
current= current->rlink;
}
}
cout<< endl;
cout<< "<------------------------noRecursionPreorderTraversal"<< endl;
}
3. 非递归后序遍历
由于访问的顺序为先左子树、然后右子树,最后根节点。并且对于每一个节点都是上述操作,所以,对于遍历来讲,需要识别当前节点类型是根(相对)、左孩子节点 、右孩子节点。故,我们设定了flag标记变量,flag=0初始标记,节点尚未入栈;在访问左孩子之前将flag置为1;在访问右孩子之前将flag置为2;并且在访问右孩子之后,将flag置为0。
//后序非递归遍历比较复杂..
Cpp代码
template<typenameelemType>
idbinaryTreeType<elemType>::noRecursionPostorderTraversal() //非递归后序遍历
{
cout<<"noRecursionPostorderTraversal--------------------------->"<< endl;
linkedStackType<nodeType<elemType>* > stack;
linkedStackType<int>intStack; //标记位同步栈.
nodeType<elemType>*current = root;
intnflag = 0; //初始标记为0.
if(current== NULL)
{
cout<< "The Stack is Empty!" << endl;
}
else
{
//1.将头节点先入栈,
stack.push(current);
intStack.push(1);
current = current->llink; //注意此处需要调整指向******
while(!stack.isEmptyStack()&& !intStack.isEmptyStack())
{
if(current!= NULL && nflag == 0)
{
stack.push(current);
intStack.push(1); //标记位为1,[在访问左孩子之前,将其值置为1]。
current = current->llink;
}
else
{
stack.pop(current);
intStack.pop(nflag); //此时的标记位为返回值,需要根据其做判断
if(nflag== 1) //说明下一步需要入栈的为右孩子.
{
stack.push(current); //继续将该节点入栈,
intStack.push(2); //但[在访问右孩子之前,将其置为2]。
current= current->rlink; //访问右节点,
nflag= 0; //置标记位为0
}
else
{
cout<< current->info << " "; //待左右子树都为空再访问节点。
}
}
}
cout<< endl;
cout<< "<------------------------noRecursionPostorderTraversal"<< endl;
}
}
template<typenameelemType>
voidbinaryTreeType<elemType>::noRecursionPostorderTraversal() //非递归后序遍历
{
cout<<"noRecursionPostorderTraversal--------------------------->"<< endl;
linkedStackType<nodeType<elemType>* > stack;
linkedStackType<int>intStack; //标记位同步栈.
nodeType<elemType>*current = root;
intnflag = 0; //初始标记为0.
if(current== NULL)
{
cout<< "The Stack is Empty!" << endl;
}
else
{
//1.将头节点先入栈,
stack.push(current);
intStack.push(1);
current = current->llink; //注意此处需要调整指向******
while(!stack.isEmptyStack()&& !intStack.isEmptyStack())
{
if(current!= NULL && nflag == 0)
{
stack.push(current);
intStack.push(1); //标记位为1,[在访问左孩子之前,将其值置为1]。
current = current->llink;
}
else
{
stack.pop(current);
intStack.pop(nflag); //此时的标记位为返回值,需要根据其做判断
if(nflag== 1) //说明下一步需要入栈的为右孩子.
{
stack.push(current); //继续将该节点入栈,
intStack.push(2); //但[在访问右孩子之前,将其置为2]。
current= current->rlink; //访问右节点,
nflag= 0; //置标记位为0
}
else
{
cout<< current->info << " "; //待左右子树都为空再访问节点。
}
}
}
cout<< endl;
cout<< "<------------------------noRecursionPostorderTraversal"<< endl;
}
}
4. 二叉排序树的搜索操作
明确概念,国内、国外的著作里提及的下三个概念等价,二叉搜索树=二叉查找树=二叉排序树。
//二叉排序树的查找存在以下几种情况:
//1.链表为空,提示并返回;
//2.链表非空,需要循环查找直到指针为空,若存在,则bfound=true;否则查找至最后bfound=缺省false。
Cpp代码
template <class elemType>
boolbSearchTreeType<elemType>::search(const elemType& searchItem)
{
nodeType<elemType>*current = new nodeType<elemType>;
boolbFound = false;
if(root== NULL)
{
cout<< "The bSearchTree is NULL\n"; //case1: 链表为空!
returnfalse;
}
else
{
current= root;
while(current!= NULL && !bFound) //case2:在链表中查找,根据大小锁定左、右子树.
{
if(current->info== searchItem)
{
bFound= true;
}
elseif(current->info > searchItem)
{
current= current->llink; //左子树
}
elseif(current->info < searchItem)
{
current= current->rlink; //右子树
}
}
}
returnbFound;
}
template <class elemType>
boolbSearchTreeType<elemType>::search(const elemType& searchItem)
{
nodeType<elemType>*current = new nodeType<elemType>;
boolbFound = false;
if(root== NULL)
{
cout<< "The bSearchTree is NULL\n"; //case1: 链表为空!
returnfalse;
}
else
{
current= root;
while(current!= NULL && !bFound) //case2:在链表中查找,根据大小锁定左、右子树.
{
if(current->info== searchItem)
{
bFound= true;
}
elseif(current->info > searchItem)
{
current= current->llink; //左子树
}
elseif(current->info < searchItem)
{
current= current->rlink; //右子树
}
}
}
returnbFound;
}
5. 二叉排序树的插入存在以下几种情况:
//1.链表为空,插入元素即为根节点;
//2.链表非空,需要寻找插入位置后插入。
//2.1插入元素已经存在,则提示出错。
//2.2总能找到大于或小于某节点的位置,记录trailcurrent完成插入操作。
Cpp代码
template <class elemType>
voidbSearchTreeType<elemType>::insert(const elemType& insertItem)
{
nodeType<elemType>*newNode = new nodeType<elemType>;
nodeType<elemType>*current;
nodeType<elemType>*trailCurrent;
newNode->info= insertItem;
newNode->llink= NULL;
newNode->rlink= NULL;
if(root== NULL)
{
root= newNode; //case1:树为空.
}
else
{
current= root;
while(current!= NULL) //case2,3,4搜索才知道!
{
trailCurrent= current;
if(current->info== insertItem)
{
cout<< "the elem is already exist!\n"; //case2:元素已经存在
return;
}
else
{
if(current->info> insertItem)
{
current= current->llink; //case3:锁定左侧位置...
}
else
{
current= current->rlink; //case4:锁定右侧位置...
}
}
}//endwhile
//case3,4根据大小进行链接
if(trailCurrent->info< insertItem)
{
trailCurrent->rlink= newNode;
}
else
{
trailCurrent->llink= newNode;
}
}//end else
}
template <class elemType>
voidbSearchTreeType<elemType>::insert(const elemType& insertItem)
{
nodeType<elemType>*newNode = new nodeType<elemType>;
nodeType<elemType>*current;
nodeType<elemType>*trailCurrent;
newNode->info= insertItem;
newNode->llink= NULL;
newNode->rlink= NULL;
if(root== NULL)
{
root= newNode; //case1:树为空.
}
else
{
current= root;
while(current!= NULL) //case2,3,4搜索才知道!
{
trailCurrent= current;
if(current->info== insertItem)
{
cout<< "the elem is already exist!\n"; //case2:元素已经存在
return;
}
else
{
if(current->info> insertItem)
{
current= current->llink; //case3:锁定左侧位置...
}
else
{
current= current->rlink; //case4:锁定右侧位置...
}
}
}//endwhile
//case3,4根据大小进行链接
if(trailCurrent->info< insertItem)
{
trailCurrent->rlink= newNode;
}
else
{
trailCurrent->llink= newNode;
}
}//end else
}
6. 二叉排序树的删除存在以下几种情况【此处可能复杂些】:
//删除一个节点,要首先判断元素值在二叉排序树中是否存在,
//若不存在则返回;
//若存在则需要锁定其对应位置为1根节点;2叶节点;3其余节点。
//根据要删除的节点是否含有左右子树的不同,分为4种情况考虑,
//见deleteFromTree()函数。
Cpp代码
template <class elemType>
voidbSearchTreeType<elemType>::deleteNode(const elemType& deleteItem)
{
//1.查找节点
//2.1找不到,不存在;
//2.2找到,删除,调用函数
nodeType<elemType>*current;
nodeType<elemType>*trailCurrent;
boolbFound = false;
if(root== NULL)
{
cout<< "Can't delete an Empty BST" << endl;
return;
}
else
{
current= root;
trailCurrent= root;
while(current != NULL && !bFound)
{
if(current->info== deleteItem)
{
bFound= true;
}
elseif(current->info > deleteItem)
{
trailCurrent= current;
current= current->llink; //左
}
else
{
trailCurrent= current;
current= current->rlink; //右
}
}//endwhile
if(current== NULL)
{
cout<< deleteItem << " is not Exist in the BST!\n" <<endl;
}
elseif(bFound)
{
if(current== root)
{
deleteFromTree(root); //可能是根节点
}
elseif(trailCurrent->info > deleteItem)
{
deleteFromTree(trailCurrent->llink);//左半分支,调整trailCurrent的指向
}
elseif(trailCurrent->info < deleteItem)
{
deleteFromTree(trailCurrent->rlink); //右半分支,调整trailCurrent的指向
}
}//endif bFound
}//end else
}
template <class elemType>
voidbSearchTreeType<elemType>::deleteNode(const elemType& deleteItem)
{
//1.查找节点
//2.1找不到,不存在;
//2.2找到,删除,调用函数
nodeType<elemType>*current;
nodeType<elemType>*trailCurrent;
boolbFound = false;
if(root== NULL)
{
cout<< "Can't delete an Empty BST" << endl;
return;
}
else
{
current= root;
trailCurrent= root;
while(current != NULL && !bFound)
{
if(current->info== deleteItem)
{
bFound= true;
}
elseif(current->info > deleteItem)
{
trailCurrent= current;
current= current->llink; //左
}
else
{
trailCurrent= current;
current= current->rlink; //右
}
}//endwhile
if(current== NULL)
{
cout<< deleteItem << " is not Exist in the BST!\n" <<endl;
}
elseif(bFound)
{
if(current== root)
{
deleteFromTree(root); //可能是根节点
}
elseif(trailCurrent->info > deleteItem)
{
deleteFromTree(trailCurrent->llink);//左半分支,调整trailCurrent的指向
}
elseif(trailCurrent->info < deleteItem)
{
deleteFromTree(trailCurrent->rlink); //右半分支,调整trailCurrent的指向
}
}//endif bFound
}//end else
}
//[原理]:某节点的前驱是该节点左子树的最右端的节点(中序遍历的结果)
Cpp代码
template <class elemType>
voidbSearchTreeType<elemType>::deleteFromTree(nodeType<elemType>*&p)
{
nodeType<elemType>*temp;
nodeType<elemType>*current;
nodeType<elemType>*trailCurrent;
if(p== NULL)
{
cout<< "The BST is NULL!" << endl;
return;
}
if(p->llink== NULL && p->rlink == NULL) //情况1,左右节点都为空(叶节点)
{
temp= p;
p= NULL;
deletetemp;
}
elseif( p->rlink == NULL) //情况2,右子树为空,左非空
{
temp= p;
p= temp->llink;
deletetemp;
}
elseif(p->llink == NULL) //情况3,左子树为空,右非空
{
temp= p;
p= temp->rlink;
deletetemp;
}
else //情况4,左右都非空[用中序遍历的前一个节点替换]
{
current= p->llink;
trailCurrent= NULL;
while(current->rlink!= NULL)
{
trailCurrent= current; //trailCurrent最终指向准备删除节点的前一个节点
current= current->rlink;
}
p->info= current->info; //信息赋值
if(trailCurrent== NULL) //仅一个左孩子节点
{
p->rlink = current->llink;
}
else
{
trailCurrent->rlink= current->llink; //给删除前点的前面一个节点调整指针指向
}
deletecurrent;
}
}
接上一节第五部分,主要分析二叉树的非递归遍历和二叉排序树的操作。
1. 非递归中序遍历
//1.依次将根节点root的左子树入栈,直到lchild=NULL,执行2
//2.将栈的元素出栈、访问;将当前指针指向节点的rchild,循环遍历。直到栈空为止!
Cpp代码
template<typenameelemType>
voidbinaryTreeType<elemType>::noRecursionInorderTraversal() //非递归中序遍历
{
cout<< "noRecursionInorderTraversal--------------------------->"<< endl;
linkedStackType<nodeType<elemType>* > stack;
nodeType<elemType>*current = root;
while(current!= NULL || !stack.isEmptyStack()) //或者||
{
if(current!= NULL)
{
stack.push(current);
current= current->llink;
}
else
{
stack.pop(current);
cout<< current->info << "\t"; //出栈的时候访问节点
current= current->rlink;
}
}
cout<< endl;
cout<< "<------------------------noRecursionInorderTraversal"<< endl;
}
template<typenameelemType>
voidbinaryTreeType<elemType>::noRecursionInorderTraversal() //非递归中序遍历
{
cout<< "noRecursionInorderTraversal--------------------------->"<< endl;
linkedStackType<nodeType<elemType>* > stack;
nodeType<elemType>*current = root;
while(current!= NULL || !stack.isEmptyStack()) //或者||
{
if(current!= NULL)
{
stack.push(current);
current= current->llink;
}
else
{
stack.pop(current);
cout<< current->info << "\t"; //出栈的时候访问节点
current= current->rlink;
}
}
cout<< endl;
cout<< "<------------------------noRecursionInorderTraversal"<< endl;
}
2. 非递归先序遍历
//在中序遍历的基础上,访问次序发生变化;
//先序遍历,需要先逐个遍历根节点,然后依次处理其左、右孩子节点。
Cpp代码
template<typenameelemType>
voidbinaryTreeType<elemType>::noRecursionPreorderTraversal() //非递归前序遍历
{
cout<<"noRecursionPreorderTraversal--------------------------->"<< endl;
linkedStackType<nodeType<elemType>* > stack;
nodeType<elemType>*current = root;
while(current!= NULL || !stack.isEmptyStack()) //或者||
{
if(current!= NULL)
{
cout<< current->info << "\t"; //先访问节点后入栈
stack.push(current);
current= current->llink;
}
else
{
stack.pop(current);
current= current->rlink;
}
}
cout<< endl;
cout<< "<------------------------noRecursionPreorderTraversal"<< endl;
}
template<typenameelemType>
voidbinaryTreeType<elemType>::noRecursionPreorderTraversal() //非递归前序遍历
{
cout<<"noRecursionPreorderTraversal--------------------------->"<< endl;
linkedStackType<nodeType<elemType>* > stack;
nodeType<elemType>*current = root;
while(current!= NULL || !stack.isEmptyStack()) //或者||
{
if(current!= NULL)
{
cout<< current->info << "\t"; //先访问节点后入栈
stack.push(current);
current= current->llink;
}
else
{
stack.pop(current);
current= current->rlink;
}
}
cout<< endl;
cout<< "<------------------------noRecursionPreorderTraversal"<< endl;
}
3. 非递归后序遍历
由于访问的顺序为先左子树、然后右子树,最后根节点。并且对于每一个节点都是上述操作,所以,对于遍历来讲,需要识别当前节点类型是根(相对)、左孩子节点 、右孩子节点。故,我们设定了flag标记变量,flag=0初始标记,节点尚未入栈;在访问左孩子之前将flag置为1;在访问右孩子之前将flag置为2;并且在访问右孩子之后,将flag置为0。
//后序非递归遍历比较复杂..
Cpp代码
template<typenameelemType>
idbinaryTreeType<elemType>::noRecursionPostorderTraversal() //非递归后序遍历
{
cout<<"noRecursionPostorderTraversal--------------------------->"<< endl;
linkedStackType<nodeType<elemType>* > stack;
linkedStackType<int>intStack; //标记位同步栈.
nodeType<elemType>*current = root;
intnflag = 0; //初始标记为0.
if(current== NULL)
{
cout<< "The Stack is Empty!" << endl;
}
else
{
//1.将头节点先入栈,
stack.push(current);
intStack.push(1);
current = current->llink; //注意此处需要调整指向******
while(!stack.isEmptyStack()&& !intStack.isEmptyStack())
{
if(current!= NULL && nflag == 0)
{
stack.push(current);
intStack.push(1); //标记位为1,[在访问左孩子之前,将其值置为1]。
current = current->llink;
}
else
{
stack.pop(current);
intStack.pop(nflag); //此时的标记位为返回值,需要根据其做判断
if(nflag== 1) //说明下一步需要入栈的为右孩子.
{
stack.push(current); //继续将该节点入栈,
intStack.push(2); //但[在访问右孩子之前,将其置为2]。
current= current->rlink; //访问右节点,
nflag= 0; //置标记位为0
}
else
{
cout<< current->info << " "; //待左右子树都为空再访问节点。
}
}
}
cout<< endl;
cout<< "<------------------------noRecursionPostorderTraversal"<< endl;
}
}
template<typenameelemType>
voidbinaryTreeType<elemType>::noRecursionPostorderTraversal() //非递归后序遍历
{
cout<<"noRecursionPostorderTraversal--------------------------->"<< endl;
linkedStackType<nodeType<elemType>* > stack;
linkedStackType<int>intStack; //标记位同步栈.
nodeType<elemType>*current = root;
intnflag = 0; //初始标记为0.
if(current== NULL)
{
cout<< "The Stack is Empty!" << endl;
}
else
{
//1.将头节点先入栈,
stack.push(current);
intStack.push(1);
current = current->llink; //注意此处需要调整指向******
while(!stack.isEmptyStack()&& !intStack.isEmptyStack())
{
if(current!= NULL && nflag == 0)
{
stack.push(current);
intStack.push(1); //标记位为1,[在访问左孩子之前,将其值置为1]。
current = current->llink;
}
else
{
stack.pop(current);
intStack.pop(nflag); //此时的标记位为返回值,需要根据其做判断
if(nflag== 1) //说明下一步需要入栈的为右孩子.
{
stack.push(current); //继续将该节点入栈,
intStack.push(2); //但[在访问右孩子之前,将其置为2]。
current= current->rlink; //访问右节点,
nflag= 0; //置标记位为0
}
else
{
cout<< current->info << " "; //待左右子树都为空再访问节点。
}
}
}
cout<< endl;
cout<< "<------------------------noRecursionPostorderTraversal"<< endl;
}
}
4. 二叉排序树的搜索操作
明确概念,国内、国外的著作里提及的下三个概念等价,二叉搜索树=二叉查找树=二叉排序树。
//二叉排序树的查找存在以下几种情况:
//1.链表为空,提示并返回;
//2.链表非空,需要循环查找直到指针为空,若存在,则bfound=true;否则查找至最后bfound=缺省false。
Cpp代码
template <class elemType>
boolbSearchTreeType<elemType>::search(const elemType& searchItem)
{
nodeType<elemType>*current = new nodeType<elemType>;
boolbFound = false;
if(root== NULL)
{
cout<< "The bSearchTree is NULL\n"; //case1: 链表为空!
returnfalse;
}
else
{
current= root;
while(current!= NULL && !bFound) //case2:在链表中查找,根据大小锁定左、右子树.
{
if(current->info== searchItem)
{
bFound= true;
}
elseif(current->info > searchItem)
{
current= current->llink; //左子树
}
elseif(current->info < searchItem)
{
current= current->rlink; //右子树
}
}
}
returnbFound;
}
template <class elemType>
boolbSearchTreeType<elemType>::search(const elemType& searchItem)
{
nodeType<elemType>*current = new nodeType<elemType>;
boolbFound = false;
if(root== NULL)
{
cout<< "The bSearchTree is NULL\n"; //case1: 链表为空!
returnfalse;
}
else
{
current= root;
while(current!= NULL && !bFound) //case2:在链表中查找,根据大小锁定左、右子树.
{
if(current->info== searchItem)
{
bFound= true;
}
elseif(current->info > searchItem)
{
current= current->llink; //左子树
}
elseif(current->info < searchItem)
{
current= current->rlink; //右子树
}
}
}
returnbFound;
}
5. 二叉排序树的插入存在以下几种情况:
//1.链表为空,插入元素即为根节点;
//2.链表非空,需要寻找插入位置后插入。
//2.1插入元素已经存在,则提示出错。
//2.2总能找到大于或小于某节点的位置,记录trailcurrent完成插入操作。
Cpp代码
template <class elemType>
voidbSearchTreeType<elemType>::insert(const elemType& insertItem)
{
nodeType<elemType>*newNode = new nodeType<elemType>;
nodeType<elemType>*current;
nodeType<elemType>*trailCurrent;
newNode->info= insertItem;
newNode->llink= NULL;
newNode->rlink= NULL;
if(root== NULL)
{
root= newNode; //case1:树为空.
}
else
{
current= root;
while(current!= NULL) //case2,3,4搜索才知道!
{
trailCurrent= current;
if(current->info== insertItem)
{
cout<< "the elem is already exist!\n"; //case2:元素已经存在
return;
}
else
{
if(current->info> insertItem)
{
current= current->llink; //case3:锁定左侧位置...
}
else
{
current= current->rlink; //case4:锁定右侧位置...
}
}
}//endwhile
//case3,4根据大小进行链接
if(trailCurrent->info< insertItem)
{
trailCurrent->rlink= newNode;
}
else
{
trailCurrent->llink= newNode;
}
}//end else
}
template <class elemType>
voidbSearchTreeType<elemType>::insert(const elemType& insertItem)
{
nodeType<elemType>*newNode = new nodeType<elemType>;
nodeType<elemType>*current;
nodeType<elemType>*trailCurrent;
newNode->info= insertItem;
newNode->llink= NULL;
newNode->rlink= NULL;
if(root== NULL)
{
root= newNode; //case1:树为空.
}
else
{
current= root;
while(current!= NULL) //case2,3,4搜索才知道!
{
trailCurrent= current;
if(current->info== insertItem)
{
cout<< "the elem is already exist!\n"; //case2:元素已经存在
return;
}
else
{
if(current->info> insertItem)
{
current= current->llink; //case3:锁定左侧位置...
}
else
{
current= current->rlink; //case4:锁定右侧位置...
}
}
}//endwhile
//case3,4根据大小进行链接
if(trailCurrent->info< insertItem)
{
trailCurrent->rlink= newNode;
}
else
{
trailCurrent->llink= newNode;
}
}//end else
}
6. 二叉排序树的删除存在以下几种情况【此处可能复杂些】:
//删除一个节点,要首先判断元素值在二叉排序树中是否存在,
//若不存在则返回;
//若存在则需要锁定其对应位置为1根节点;2叶节点;3其余节点。
//根据要删除的节点是否含有左右子树的不同,分为4种情况考虑,
//见deleteFromTree()函数。
Cpp代码
template <class elemType>
voidbSearchTreeType<elemType>::deleteNode(const elemType& deleteItem)
{
//1.查找节点
//2.1找不到,不存在;
//2.2找到,删除,调用函数
nodeType<elemType>*current;
nodeType<elemType>*trailCurrent;
boolbFound = false;
if(root== NULL)
{
cout<< "Can't delete an Empty BST" << endl;
return;
}
else
{
current= root;
trailCurrent= root;
while(current != NULL && !bFound)
{
if(current->info== deleteItem)
{
bFound= true;
}
elseif(current->info > deleteItem)
{
trailCurrent= current;
current= current->llink; //左
}
else
{
trailCurrent= current;
current= current->rlink; //右
}
}//endwhile
if(current== NULL)
{
cout<< deleteItem << " is not Exist in the BST!\n" <<endl;
}
elseif(bFound)
{
if(current== root)
{
deleteFromTree(root); //可能是根节点
}
elseif(trailCurrent->info > deleteItem)
{
deleteFromTree(trailCurrent->llink);//左半分支,调整trailCurrent的指向
}
elseif(trailCurrent->info < deleteItem)
{
deleteFromTree(trailCurrent->rlink); //右半分支,调整trailCurrent的指向
}
}//endif bFound
}//end else
}
template <class elemType>
voidbSearchTreeType<elemType>::deleteNode(const elemType& deleteItem)
{
//1.查找节点
//2.1找不到,不存在;
//2.2找到,删除,调用函数
nodeType<elemType>*current;
nodeType<elemType>*trailCurrent;
boolbFound = false;
if(root== NULL)
{
cout<< "Can't delete an Empty BST" << endl;
return;
}
else
{
current= root;
trailCurrent= root;
while(current != NULL && !bFound)
{
if(current->info== deleteItem)
{
bFound= true;
}
elseif(current->info > deleteItem)
{
trailCurrent= current;
current= current->llink; //左
}
else
{
trailCurrent= current;
current= current->rlink; //右
}
}//endwhile
if(current== NULL)
{
cout<< deleteItem << " is not Exist in the BST!\n" <<endl;
}
elseif(bFound)
{
if(current== root)
{
deleteFromTree(root); //可能是根节点
}
elseif(trailCurrent->info > deleteItem)
{
deleteFromTree(trailCurrent->llink);//左半分支,调整trailCurrent的指向
}
elseif(trailCurrent->info < deleteItem)
{
deleteFromTree(trailCurrent->rlink); //右半分支,调整trailCurrent的指向
}
}//endif bFound
}//end else
}
//[原理]:某节点的前驱是该节点左子树的最右端的节点(中序遍历的结果)
Cpp代码
template <class elemType>
voidbSearchTreeType<elemType>::deleteFromTree(nodeType<elemType>*&p)
{
nodeType<elemType>*temp;
nodeType<elemType>*current;
nodeType<elemType>*trailCurrent;
if(p== NULL)
{
cout<< "The BST is NULL!" << endl;
return;
}
if(p->llink== NULL && p->rlink == NULL) //情况1,左右节点都为空(叶节点)
{
temp= p;
p= NULL;
deletetemp;
}
elseif( p->rlink == NULL) //情况2,右子树为空,左非空
{
temp= p;
p= temp->llink;
deletetemp;
}
elseif(p->llink == NULL) //情况3,左子树为空,右非空
{
temp= p;
p= temp->rlink;
deletetemp;
}
else //情况4,左右都非空[用中序遍历的前一个节点替换]
{
current= p->llink;
trailCurrent= NULL;
while(current->rlink!= NULL)
{
trailCurrent= current; //trailCurrent最终指向准备删除节点的前一个节点
current= current->rlink;
}
p->info= current->info; //信息赋值
if(trailCurrent== NULL) //仅一个左孩子节点
{
p->rlink = current->llink;
}
else
{
trailCurrent->rlink= current->llink; //给删除前点的前面一个节点调整指针指向
}
deletecurrent;
}
}
发表评论
-
SQLite 增删改查的工具类
2014-05-03 00:23 864SQLite 增删改查的工具类 -
将android工程打包生成apk文件
2014-04-21 18:56 6921.)生成keystore 按照下面的命令行 在C:\Pr ... -
android - 自定义标题栏(在标题栏中增加按钮和文本居中)
2012-10-09 10:57 2205现在很多的Android程序都在标题栏上都显示了一些按钮和标题 ... -
改变背景颜色
2012-10-08 10:47 790package com.tony.tabstudy; imp ... -
按钮文字变色
2012-09-26 14:15 853按钮文字变色 我们首先添加一个ColorStateLis ... -
ListView与Button共存问题
2012-09-25 09:34 609ListView 和 其它能触发点击事件的widget无法一起 ... -
ListView与Button共存问题
2012-09-20 17:06 592http://blog.csdn.net/xinqiqi123 ... -
获取手机SIM卡电话号码信息
2012-09-24 09:25 1126<uses-permission android:nam ... -
android判断用户网络类型
2012-09-18 20:42 4496Nettestactivity代码 ... -
android权限大全
2012-09-24 09:25 612访问登记属性 android.permission.AC ... -
android中实现百度地图
2012-09-24 09:26 1452android实现GPS定位 实现GPS定位功能主要是 ... -
android listView点击拓展出一些子item
2012-08-20 22:23 770android有些应用中listView点击item就会在 ... -
Activity的启动模式(android:launchMode)
2012-08-20 21:58 787在android里,有4种activity ... -
android面试题
2012-08-16 13:10 776打包下载: <ignore_js_op> Andr ... -
二叉树
2012-08-08 22:41 644http://blog.163.com/qhx_405/blo ... -
二叉树遍历
2012-08-08 22:27 688二叉树遍历 博客分类: 算法 数据结构CC++C#F# ... -
Android开发_如何调用系统默认浏览器访问
2013-11-04 11:20 675一、启动android默认浏览器 Intent ... -
图片滚动的几种常用组件的使用
2014-05-04 01:31 689图片滚动的几种常用组件的使用 写在前面:屏幕切换指的是在 ... -
android签名
2012-07-29 19:17 773Android 签名详解(三种方法) 2012 - 7 ...
相关推荐
二叉树、二叉搜索树的构建,前序、中序、后序的 递归和非递归遍历;前序中序序列构建二叉树……
二叉树的非递归遍历,使用C++实现二叉树的非递归遍历,对正在学习算法的同学应该挺有帮助的
主要介绍了C语言排序方法,包含10种排序,数据结构课程设计实例二叉树建立遍历冒泡排序快速排序_二叉排序树_二叉树层次遍历_二叉树非递归遍历_二叉树建立括号匹配直接插入选择代码大学生本科毕业设计期末作业排序...
1.建立完全二叉树 2.先序非递归遍历二叉树函数 & 先序递归遍历二叉树验证 3.中序非递归遍历二叉树函数 & 中序递归遍历二叉树验证 4.后序非递归遍历二叉树函数 & 后序递归遍历二叉树验证
数据结构非递归先序、中序、后序遍历二叉树,数据结构非递归先序、中序、后序遍历二叉树
二叉树的非递归遍历 二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历二叉树的非递归遍历
二叉树的递归遍历、非递归遍历和层次遍历
先序非递归遍历二叉树: a b c 中序递归遍历二叉树: b a c 中序非递归遍历二叉树: b a c 后序递归遍历二叉树: b c a 后序非递归遍历二叉树: b c a 二叉树的深度是2 二叉树的结点个数是3 Press any key to ...
1.采用二叉链表作为存储结构,创建一棵二叉树; 2.用递归及非递归算法对二叉树实现先序遍历; 3.用递归及非递归算法对二叉树实现中序遍历; 4.用递归及非递归算法对二叉树实现后序遍历。 5.用递归遍历算法中的访问...
中根顺序递归建立二叉树,递归及非递归遍历二叉树。C++面向过程实现
非递归中序遍历二叉树(算法2): 层次遍历二叉树: 递归计算单分支结点: 递归计算双分支结点: 递归计算叶子数: 二叉数的深度: 交换二叉树的左右子树: 二叉树已左右交换。 递归先序遍历二叉树: 递归...
二叉树的中序、前序、后序的递归、非递归遍历算法
二叉树递归非递归遍历(递归前中后,非递归前中后,层次遍历)
自己写的相当全的二叉树函数操作集合,包括二叉树的递归遍历和非递归遍历,以及计算二叉树的深度和叶子节点等
链式二叉树的前序创建、递归遍历、利用堆栈的非递归遍历、前序销毁以及求二叉树的深度
数据结构实用教程之二叉树,其中包含了:二叉树的定义、二叉树的递归遍历、二叉树基本操作。 数据结构实用教程之二叉树,其中包含了:二叉树的定义、二叉树的递归遍历、二叉树基本操作。 数据结构实用教程之二叉树,...
二叉树深度 二叉树前序遍历 递归实现 二种非递归实现 二叉树中序遍历: 递归实现 非递归实现 二叉树后序遍历: 递归实现 非递归实现 二叉树层次遍历 二叉树层次创建,创建方法遵循卡特兰数 ...
数据结构 二叉树的三种非递归遍历 利用栈实现的非递归遍历,前序利用递归实现输入,中序,后序利用栈实现
数据结构中的单链表;二叉树遍历;折半查找;二叉排序树;内部排序。有具体实现代码。
数据结构 二叉树三种遍历的非递归算法(背诵版). 数据结构 二叉树三种遍历的非递归算法(背诵版). 数据结构 二叉树三种遍历的非递归算法(背诵版).