代码随想录第十四天|二叉树理论基础、递归遍历、迭代遍历

二叉树理论基础

二叉树种类:

1. 满二叉树

如果一棵二叉树只有度为0的结点和度为2的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。节点数量2^k-1,k是深度。

2. 完全二叉树

在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2^(h-1) 个节点。比如优先级队列实际上是堆,堆即为完全二叉树,同时保证父子节点顺序关系。

3.二叉搜索树(logn)

二叉搜索树是一个有序树对布局没要求,对顺序有要求。若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉排序树。

4.平衡二叉搜索树(AVL)

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。插入是log(n)搜索也是log(n)。map和set的底层就是平衡二叉搜索树,因此元素有序。注意unordered_set或unordered_map是用哈希表实现。


二叉树存储方式

1.链式存储

用指针实现。通过左指针和右指针指向下一个子节点。

2.顺序存储

用数组实现。如果父节点的数组下标是 i,那么它的左孩子就是 i * 2 + 1,右孩子就是 i * 2 + 2。

更常使用链式存储,但要清楚如何用数组实现。


二叉树的遍历方式

深度优先搜索:先一直往下遍历,直到触底进行回退,前中后序搜索都属于深度优先搜索。可以用递归法(用栈)或者迭代法(非递归,用队列)。

广度优先搜索:一层层或者一圈圈进行遍历,二叉树中层序遍历就是广度优先搜索。层序遍历就是迭代法,使用队列实现。

前序遍历:中左右

中序遍历:左中右

后续遍历:左右中


二叉树的定义方式

struct TreeNode{

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) :val(x),left(NULL),right(NULL)

};



递归遍历

1.确认递归函数的参数和返回值

2.确定终止条件

3.确定单层递归的逻辑

前序遍历

void traversal(*cur,vector<int> &num){

if(cur==NULL)

return;

num.push_back(cur->val);

traversal(cur->left,num);

traversal(cur->right,num);

}

中序遍历

void traversal(*cur,vector<int> &num){

if(cur==NULL)

return;

traversal(cur->left,num);

num.push_back(cur->val);

traversal(cur->right,num);

}

后序遍历

void traversal(*cur,vector &num){

if(cur==NULL)

return;

traversal(cur->left,num);

traversal(cur->right,num);

num.push_back(cur->val);

}

完成了144.145.94三道分别是前后中序遍历的题目。


迭代遍历

前序遍历

前序遍历是中左右,使用stack先把中push,然后pop,再把右push,左push,这样弹出即为中左右。记得中间check一下node是否为null

vector<int> preorderTraversal(TreeNode* root) {

        stack<TreeNode *> st;

        vector<int> result;

        if(root==NULL)

            return result;

        st.push(root);

        while(!st.empty()){

            TreeNode *Node=st.top();

            st.pop();

            if(Node!=NULL)

            {

                result.push_back(Node->val);

                st.push(Node->right);

                st.push(Node->left);

            }

        }

        return result;

    }

后序遍历

后序遍历是左右中,可以在前序遍历的基础上,变成中右左,最后再reverse数组变成左右中。

    vector<int> postorderTraversal(TreeNode* root) {

        stack<TreeNode *> st;

        vector<int> result;

        if(root==NULL)

            return result;

        st.push(root);

        while(!st.empty()){

            TreeNode *Node=st.top();

            st.pop();

            if(Node!=NULL)

            {

                result.push_back(Node->val);

                st.push(Node->left);

                st.push(Node->right);

            }

        }

        reverse(result.begin(),result.end());

        return result;

    }

中序遍历

中序遍历是左中右,需要先一直到最底的左节点,直到左节点不存在,通过st.top()找到中间节点,取值弹出再接着遍历右节点。

vector<int> inorderTraversal(TreeNode* root) {

        stack<TreeNode*> st;

        vector<int> result;

        TreeNode* cur=root;

        while(cur!=NULL||!st.empty())

        {

            if(cur!=NULL)

            {

                st.push(cur);

                cur=cur->left;

            }

            else

            {

                cur=st.top();

                st.pop();

                result.push_back(cur->val);

                cur=cur->right;

            }

        }

        return result;

    }


 统一迭代

统一迭代是通过在访问过的节点后放空指针的方式进行标记,暂时搁置。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 215,133评论 6 497
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,682评论 3 390
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 160,784评论 0 350
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,508评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,603评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,607评论 1 293
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,604评论 3 415
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,359评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,805评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,121评论 2 330
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,280评论 1 344
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,959评论 5 339
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,588评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,206评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,442评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,193评论 2 367
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,144评论 2 352

推荐阅读更多精彩内容