最近要面试整理的二叉树知识
/*
若它的左子树不为空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树分别为二叉排序树。
*/
#include <iostream>
using namespace std;
#define MAXSIZE 100
typedef struct BiTNode{
int data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
/**
* 递归查找二叉排序树 T 中是否存在 key
* 指针 f 指向 T 的 双亲，其初始调用值为NULL
* 若查找成功，则指针 p 指向该数据元素结点，并返回TRUE
* 若查找不成功， 则指针 p 指向查找路径上访问的最后一个结点并返回FALSE
*/
/*
原理：
先将要查找的关键字和根节点进行比较;
若和根节点值相同，则返回根节点值；若比根节点小，就递归查找左子树，若比根节点大，则递归查找右子树
*/
int SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{
if(!T) //为空树或者为空节点
{
*p = f;
return false;
}
else if(key == T->data)
{
*p = T;
return true;
}
else if(key < T->data) //在左子树中递归查找
{
return SearchBST(T->lchild,key,T,p);
}
else
{
return SearchBST(T->rchild,key,T,p);
}
return false;
}
/**
* 二叉排序树的插入
* 当二叉排序树中不存在关键字等于 key 的数据元素时，插入 key 并返回TRUE
*/
/*
原理：
如果在原有的二叉排序树中没有要插入的关键字，则将关键字与查找的结点p（在查找操作中返回的结点）的值进行比较
若p为空，则插入关键字赋值给该节点
若小于结点p的值，则插入关键字作为结点p的左子树；
若大于结点p的值，则插入关键字作为结点p的右子树；
*/
int InsertBST(BiTree *T,int key)
{
BiTree p,s;
if(!SearchBST(*T,key,NULL,&p))
{
s = (BiTree)malloc(sizeof(BiTNode));
s->data = key;
s->lchild = s->rchild = nullptr;
if(!p)
{
*T = s;
}
else if(key < p->data)
{
p->lchild = s;
}
else
{
p->rchild = s;
}
return true;
}
return false;
}
/*
原理：
叶子结点；（很容易实现删除操作，直接删除结点即可）
仅有左或者右子树的结点；（容易实现删除操作，删除结点后，将它的左子树或者右子树整个移动到删除结点的位置）
左右子树都有的结点。（实现删除操作很复杂）：将它的直接前驱或者直接后继作为删除结点的数据
*/
int Delete(BiTree *p)
{
BiTree q,s;
if((*p)->rchild == nullptr)//需要重接它的左子树
{
q = *p;
*p = (*p)->lchild;
free(q);
}
else if((*p)->lchild == nullptr)//需要重接它的右子树
{
q = *p;
*p = (*p)->rchild;
free(q);
}
else
{
q = *p;
s = (*p)->lchild;
while (s->rchild)
{ // 向右到尽头，找到待删结点的前驱
q = s;
s = s->rchild;
}
(*p)->data = s->data; // s 指向被删除结点的直接前驱 （将被删结点前驱的值取代被删结点的值）
if (q != *p)
q->rchild = s->lchild; // 重接 q 的右子树
else
q->lchild = s->lchild; // 重接 q 的左子树
free(s);
}
return true;
}
int DeleteBST(BiTree* T,int key)
{
if(!*T)
{
return false;
}
else
{
if(key == (*T)->data)
{
}
else if(key < (*T)->data)
{
return DeleteBST(&(*T)->lchild,key);
}
else
{
return DeleteBST(&(*T)->rchild,key);
}
}
return true;
}
//中序遍历
void InOrderTraverse(BiTree T)
{
if (!T)
return;
InOrderTraverse(T->lchild);
//printf("%d ", T->data);
cout<< T->data << ' ';
InOrderTraverse(T->rchild);
}
int main()
{
int i;
int a[10] ={62,88,58,47,35,73,51,99,37,93};
BiTree T = NULL;
for (i = 0; i < 10; i++)
{ // 通过插入操作来构建二叉排序树
InsertBST(&T, a[i]);
}
InOrderTraverse(T);
system("PAUSE");
return 0;
}
/* 那么从树根开始： 如果当前结点t 大于结点u、v，说明u、v都在t 的左侧，所以它们的共同祖先必定在t 的左子树中，故从t 的左子树中继续查找； 如果当前结点t 小于结点u、v，说明u、v都在t 的右侧，所以它们的共同祖先必定在t 的右子树中，故从t 的右子树中继续查找； 如果当前结点t 满足 u <t < v，说明u和v分居在t 的两侧，故当前结点t 即为最近公共祖先； 而如果u是v的祖先，那么返回u的父结点，同理，如果v是u的祖先，那么返回v的父结点。 */
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==NULL)
return NULL;
while(root){
if(p->data>root->data&&q->data>root->data)
root=root->right;
else if(p->data<root->data&&q->data<root->data)
root=root->left;
else return root;
}
}
本文由 Ryan 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为:
2019/01/28 16:34