剑指offer (3)

  • R4y 
  • 未分类

有幸的划水了第一波腾讯的笔试。虽说整体过程的题目还是算容易,不过实际上还是由不少的困难。这次是自己的一点总结帖。

离线开锁 声波锁 和 2FA 技术。

二叉树 (BinTree)

基本结构

定义:

二叉树在图论中是这样定义的:二叉树是一个连通的无环图,并且每一个顶点的度不大于3 。有根二叉树还要满足根结点的度不大于2。有了根结点之后,每个顶点定义了唯一的父结点,和最多2个子结点。然而,没有足够的信息来区分左结点和右结点。如果不考虑连通性,允许图中有多个连通分量,这样的结构叫做森林。

二叉树中每个节点都是他的左右字数的前驱,左右子树也是器根节点的后继。

名词:words

  • 兄弟 具有同一父节点的节点
  • 祖先/子孙 如果y在x为根节点的子树中且 y <> x 则x 是y的祖先
  • 层数 规定根层数为0,其余结点层数等于其父节点层数加一。
  • 度数 节点的飞控字数个数即为树的度。
  • 树的高度 所有节点中的最大的层数称为二叉树的高度。
  • 树叶/分支 左右子树均为空的结点称为树叶,否则是称为分支节点。
  • 特殊二叉树
    • 满二叉树 如果任意节点都有两棵非空子树或者树叶。
    • 完全二叉树 只有最下面的两侧的节点度数小于2 其他的层各节点的度数等于2 。

二叉树

性质:

  • 第i层最多有 2^i个节点

数据存储结构

顺序存储结构

对应一个二叉树,我们使用语言实现它

#define Maxsize 100     //假设一维数组最多存放100个元素typedef char Datatype;  //假设二叉树元素的数据类型为字符typedef struct{         Datatype bt[Maxsize];    int btnum;}Btseq;

这里的顺序存储结构,实际上是可以看作,是吧二叉树压扁,投影在一个数组里。

如上图 A是根,B是其左节点,C是其右节点。那么我们在顺序存储中得到的数组的内容是:

ABCD^EFGH^^^I^^

链式存储结构

这里是使用链式结构,具体代码如下:

typedef char Datatype;  //定义二叉树元素的数据类型为字符typedef struct  node   //定义结点由数据域,左右指针组成{     Datatype data;    struct node *lchild,*rchild;}Bitree;

这个结构是见解明了了。一个三个元素,本身的数据。左子树和右子树。
BitTree

二叉树的遍历

这个问题算是一个超级基本的问题了,基本上是逃不过的。不过之前的印象深刻滚瓜烂熟。突然遇到还是懵逼一会。所以及时总结,加强记忆。

通常来说对二叉树的遍历有以下的三种方式。

  • NLR:前序遍历(Preorder Traversal 亦称(先序遍历)) (根左右)
  • LNR:中序遍历(Inorder Traversal) (左根右)
  • LRN:后序遍历(Postorder Traversal) (左右根)

这里采用第二种存储方式.如果我们对其孩子节点进行一次访问,那么我们对其指针进行一次指向即可。

node lChild = *this->lchild;

这里采用递归的方法。对整个的二叉树的结构进行遍历,并打印其值

前序遍历

void preTraversal(node* root){cout << root->data;                    //先进行根操作if(root->lchild != NULL)                // 实际上的遍历的类型在这里是其操作顺序决定的,    preTraversal(root->lchild);if(root->rchild != NULL)    preTraversal(root->rchild);}

中序遍历

void preTraversal(node* root){if(root->lchild != NULL)                // 实际上的遍历的类型在这里是其操作顺序决定的,    preTraversal(root->lchild);cout << root->data;                    // 当上面的递归开始返回的时候,第一次执行的是我们的左叶子节点                                    // 当第一次返回后,现在是该节点的父节点,即根节点if(root->rchild != NULL)                // 之后继续查找右节点    preTraversal(root->rchild);        // 这次调用,会打印右节点的值}

后序遍历

void preTraversal(node* root){if(root->lchild != NULL)                // 实际上的遍历的类型在这里是其操作顺序决定的,    preTraversal(root->lchild);            if(root->rchild != NULL)                    preTraversal(root->rchild);cout << root->data;        }

这里递归的思路是一定要清楚,如果我们画出了调用栈,那个更清楚。

Q&A

Q: 某二叉树前序遍历访问顺序是abdgcefh,中序遍历访问顺序是dgbaechf,则后序遍历的结点访问顺序是多少?

A: 这个是超经典的一类问题了,可能考试都要考它。实际上我们的分析,思路如下:我们要做到的是还原二叉树。从第一个我们可以得到 根节点是 a,中序遍历的话是左根右的顺序,所以我们可以找到在中续遍历中找到a,把其分为agb,和aechf两个子树。

之后周而复始,bdg也是根左右。cefh也是根左右。之后c取出分e,hf两个子树。

留下点什么吧