Tree

include<iostream>

include<stack>

include<queue>

include <list>

using namespace std;

/*
二叉树定义
*/
typedef struct BTNode{
char data;

struct BTNode *lchild;
struct BTNode *rchild;

}BTNode;

/*
构建二叉树
*/
BTNode *Create(BTNode T){
char ch;
cin >> ch;
if (ch == '#'){
T = NULL;
}
else{
T = (BTNode)malloc(sizeof(BTNode));
T->data = ch;
T->lchild = Create(T->lchild);
T->rchild = Create(T->rchild);
}
return T;
}

/*

  • 先序遍历递归
    */
    void Preorder(BTNode *T){

    if (T != NULL){
    cout << T->data << " ";
    Preorder(T->lchild);
    Preorder(T->rchild);
    }
    }

/*

  • 先序遍历非递归
    */

void Preorder2(BTNode *T){
stack<BTNode *> sta;
BTNode *p = T;
if (T != NULL){
sta.push(T);
while (!sta.empty()){
p = sta.top();
cout << p->data << " ";
sta.pop();

        if (p->rchild != NULL){
            sta.push(p->rchild);
        }

        if (p->lchild != NULL){
            sta.push(p->lchild);
        }
    }
}

}
/*

  • 中序遍历递归
    */
    void Inorder(BTNode *T){
    if (T != NULL){
    Inorder(T->lchild);
    cout << T->data << " ";
    Inorder(T->rchild);
    }
    }

/*

  • 中序遍历非递归
    */

void Inorder2(BTNode *T){
stack<BTNode *> sta;
BTNode *p = T;

if (T != NULL){
    while (!sta.empty() || p != NULL){
        while (p != NULL){
            sta.push(p);
            p = p->lchild;
        }
        if (!sta.empty()){
            p = sta.top();
            sta.pop();
            cout << p->data << "    ";
            p = p->rchild;
        }
    }
}

}
/*

  • 后序遍历递归
    */

void Postorder(BTNode *T){
if (T != NULL){
Postorder(T->lchild);
Postorder(T->rchild);
cout << T->data << " ";
}
}

/*
后序遍历非递归
*/
void Postorder2(BTNode *T){
stack<BTNode *> sta;
BTNode *p = T;
BTNode *q=NULL;

while (p != NULL || !sta.empty())
{
    while (p != NULL){
        sta.push(p);
        p = p->lchild;
    }
    p = sta.top();              //访问栈顶，判断若有右节点则右节点进栈，否则出栈。
    if (p->rchild == NULL || p->rchild == q){
        cout << p->data << "    ";
        q = p;
        sta.pop();
        p = NULL;
    }
    else{
        p = p->rchild;
    }
}

}
/*
双栈法 后序遍历非递归
*/
void Postorder3(BTNode *T){
stack<BTNode *> sta,stb;
BTNode *p = T;
sta.push(p);
while (!sta.empty()){
p = sta.top();
sta.pop();
stb.push(p);

    if (p->lchild != NULL){
        sta.push(p->lchild);
    }

    if (p->rchild != NULL){
        sta.push(p->rchild);
    }

}

while (!stb.empty()){
    cout << stb.top()->data << "    ";
    stb.pop();
}

}

/*
层次遍历
*/

void Levelorder(BTNode *T){
queue<BTNode *> qu;
BTNode *p = T;
if (p!=NULL)
{
qu.push(p);
while (!qu.empty()){
p = qu.front();
cout << p->data << " " ;
qu.pop();
if (p->lchild != NULL){
qu.push(p->lchild);
}

        if (p->rchild!=NULL){
            qu.push(p->rchild);
        }
    }
}

}

/*

  • 求二叉树的深度
    */
    int GetDepth(BTNode *T) {

    /* if(T!=NULL){
    ++n;
    n=GetDepth(T->lchild,n)>GetDepth(T->rchild,n) ? GetDepth(T->lchild,n) : GetDepth(T->rchild,n);
    }*/
    int ld, rd;
    if (T == NULL) {
    return 0;
    }
    else {
    ld = GetDepth(T->lchild);
    rd = GetDepth(T->rchild);

      return (ld > rd ? ld : rd) + 1;

    }
    }

/*

  • 查找data为k的节点是否存在
    */

int FindData(BTNode *T, char k) {
//queue<BTNode *> qu;
BTNode p = T;
/ if(T!=NULL){
qu.push(p);
while(!qu.empty()){ //层次遍历查找
p=qu.front();
if(p->data==k){
return 1;
}
qu.pop();
if(p->lchild!=NULL){
qu.push(p->lchild);
}
if(p->rchild!=NULL){
qu.push(p->rchild);
}

}
return  0;
}*/

if (T == NULL) {
    return 0;
}
else {
    if (T->data == k) {        //先序遍历查找
        return 1;
    }

    if (FindData(T->lchild, k) > 0) {
        return 1;
    }
    else {
        return FindData(T->rchild, k);
    }

}

}

/*

  • 输出先序遍历第K个节点的值
    */

void ShowK(BTNode T, int k) {
if (T != NULL) {
/ ++n; //定义全局变量n
if(n==k){
cout<<"第"<<k<<"个节点的值为: "<<T->data<<endl;
return;
}*/

    ShowK(T->lchild, k);
    ShowK(T->rchild, k);
}

}

/*

  • 求二叉树的宽度
    */
    int GetWidth(BTNode *T) {

    queue<BTNode *> qu;
    int width = 1;
    int currwidth = 1;
    int nextwidth = 0;
    BTNode *p = T;
    if (T != NULL) {
    qu.push(p);
    while (!qu.empty()) {
    while (currwidth > 0) {
    p = qu.front();
    currwidth--;
    qu.pop();

              if (p->lchild != NULL) {
              qu.push(p->lchild);
              nextwidth++;
          }
          if (p->rchild != NULL) {
              qu.push(p->rchild);
              nextwidth++;
          }
      }

      if (nextwidth > width)
          width = nextwidth;
      currwidth = nextwidth;
      nextwidth = 0;
  }

  return width;

    }
    return 0;
    }

/*

  • 二叉树第K层的节点个数
    */

int GetNum(BTNode *T, int k) {
queue<BTNode *> qu;
BTNode *p = T;
int currwidth = 1;
int nextwidh = 0;
int i = 0;
if (p != NULL) {
qu.push(p);
while (!qu.empty()) {
++i;
if (i == k) {
return currwidth;
}
while (currwidth > 0) {
p = qu.front();
currwidth--;
qu.pop();

            if (p->lchild != NULL) {
                qu.push(p->lchild);
                nextwidh++;
            }

            if (p->rchild != NULL) {
                qu.push(p->rchild);
                nextwidh++;
            }
        }
        currwidth = nextwidh;
        nextwidh = 0;
    }
}

return 0;

}

/*

  • 求叶子节点个数
    */

int Getleaves(BTNode *T) {
queue<BTNode *> qu;
BTNode *p = T;
int n = 0;
if (p != NULL) {
qu.push(p);
while (!qu.empty()) {
p = qu.front();

        qu.pop();
        if (p->lchild != NULL) {
            qu.push(p->lchild);
        }

        if (p->rchild != NULL) {
            qu.push(p->rchild);
        }

        if (p->lchild == NULL && p->rchild == NULL) {
            ++n;
        }
    }
}
return n;

}

/*
*前序和中序重建二叉树
*/

BTNode *RecreateByPI(char *pre, char *in, int nodeNum) {

if (pre == NULL || in == NULL || nodeNum < 1) {
    return NULL;
}
int i = 0;
BTNode *T;
T = (BTNode *)malloc(sizeof(BTNode));

for (; i < nodeNum; ++i) {
    if (*(in + i) == *pre) {      //先序遍历的第一个节点为根节点
        break;
    }
}
T->data = *pre;

T->lchild = RecreateByPI(pre + 1, in, i);      //i左边递归建立左子树
T->rchild = RecreateByPI(pre + i + 1, in + i + 1, nodeNum - 1 - i);    //i右边递归建立右子树
return T;

}

/*

  • 中序和后序重建树
    */

BTNode *RecreateByIL(char *last, char *in, int nodeNum) {
if (last == NULL || in == NULL || nodeNum < 1) {
return NULL;
}
int i = 0;
BTNode *T = (BTNode )malloc(sizeof(BTNode));
for (; i < nodeNum; ++i) {
if ((in + i) == *(last + nodeNum - 1)) {
break;
}
}

T->data = *(in + i);
T->lchild = RecreateByIL(last, in, i);
T->rchild = RecreateByIL(last + i, in + i + 1, nodeNum - i - 1);

return T;

}

/*

  • 两个节点的公共祖先
    */

BTNode *FindAns(BTNode *T, char a, char b) {
if (T == NULL) {
return NULL;
}
if (T->data == a || T->data == b) {
return T;
}

BTNode *left = FindAns(T->lchild, a, b);
BTNode *right = FindAns(T->rchild, a, b);

if (left != NULL && right != NULL) {
    return T;
}

return (left != NULL) ? left : right;

}

/*

  • 记录路径寻找公共祖先
    */

bool FindPath(BTNode *T, list<char> &li, char c) {
if (T == NULL) {
return false;
}
li.push_back(T->data);
if (T->data == c) {
return true;
}

bool find = FindPath(T->lchild, li, c) || FindPath(T->rchild, li, c);

if (find) {
    return true;
}
li.pop_back();       //在左树没找到,就弹出左树元素
return false;

}

char FindAns2(BTNode *T, char a, char b) {
if (T == NULL) {
return -1;
}

list<char> l1, l2;
bool b1 = FindPath(T, l1, a);
bool b2 = FindPath(T, l2, b);
char ans;

list<char>::iterator i1 = l1.begin();
list<char>::iterator i2 = l2.begin();
if (b1 && b2) {

    while (i1 != l1.end() && i2 != l2.end()) {
        if (*i1 == *i2) {
            ans = *i1;
        }
        else {
            break;
        }

         
        i1++;
        i2++;
    }
}

return ans;

}

/*

  • 求二叉树节点的最大距离
    */

int mas = 0;

int MaxLegthTwoNode(BTNode *T) {

if (T == NULL) {
    return 0;
}

if (T->lchild == NULL && T->rchild == NULL) {
    return 0;
}

int a = GetDepth(T->lchild) + GetDepth(T->rchild);
int b = MaxLegthTwoNode(T->lchild);
int c = MaxLegthTwoNode(T->rchild);

int dis = (a > b ? a : b) > c ? (a > b ? a : b) : c;     //最大距离为左子树最大高度,或者右子树最大高度,或者左右深度之和

if (dis > mas) {
    mas = dis;
}
return dis;

}

/*

  • 打印根节点到叶子节点路径
    */
    list<char> li;
    void PrintRToL(BTNode T) {
    /    queue<BTNode *> qu;
    BTNode *p = T;
    if (p != NULL) {
    qu.push(p);
    while (!qu.empty()) {
    p = qu.front();

    qu.pop();
    if (p->lchild != NULL) {
    qu.push(p->lchild);
    }
    if (p->rchild != NULL) {
    qu.push(p->rchild);
    }

    if (p->lchild == NULL && p->rchild == NULL) {
    list<char> li;
    if (FindPath(T, li, p->data)) {
    list<char>::iterator it = li.begin(); //记录叶子节点路径方法
    while (it != li.end()) {
    cout << it << " ";
    it++;
    }
    }
    cout<<endl;
    }
    }
    }    /

    if (T != NULL){
    li.push_back(T->data);
    if (T->lchild == NULL && T->rchild == NULL){
    list<char>::iterator it = li.begin();
    while (it != li.end()){
    cout << *it << " "; //打印栈或队列元素,但不出栈
    it++;
    }
    cout << endl;
    }

      PrintRToL(T->lchild);
  PrintRToL(T->rchild);
  li.pop_back();           //第三次访问的时候,出栈,意味着此节点的左右子树已经遍历完毕,包括叶子节点

    }
    }

/*
累加和为指定值的最长路径
*/
int s, i, tmp;
list<char> l2;
void printMaxSum(BTNode *T, int sum){
if (T != NULL){
li.push_back(T->data);
s += (T->data - '0');
++i;
if (s == sum){
if (tmp < i){
tmp = i;
l2.clear();

            if (!li.empty()){
                list<char>::iterator it = li.begin();
                while (it != li.end())
                {
                    l2.push_back(*it);
                    ++it; 
                }
            }
        }
    
    }

    printMaxSum(T->lchild,sum);
    printMaxSum(T->rchild,sum);

    s -= (li.back() - '0');
    --i;
    li.pop_back();
}

if (li.empty()){
    list<char>::iterator it = l2.begin();
    while (it != l2.end())
    {
        cout << *it << "    ";
        ++it;
    }
}

}

/*
按层打印和ZigZag打印
*/

void printZigZag(BTNode T){
queue<BTNode> qu;
stack<char> st;
BTNode *p = T;
int currWidth = 1;
int nextWidth = 0;
int i = 1;
if (p != NULL){
qu.push(p);

    while (!qu.empty()){
        if (i % 2 == 0){
            cout << "Level " << i << " from right to left : ";
        }
        else{
            cout << "Level " << i << " from left to right : ";
        }
        while (currWidth > 0){
            currWidth--;
            p = qu.front();
            qu.pop();
            if (i % 2 == 0){
                st.push(p->data);
            }
            else{
                cout << p->data << " ";
            }
        
            if (p->lchild != NULL){
                qu.push(p->lchild);
                nextWidth++;
            }

            if (p->rchild != NULL){
                qu.push(p->rchild);
                nextWidth++;
            }
        }
        while (!st.empty()){
            cout << st.top() << " ";
            st.pop();
        }
        cout << endl;
        ++i;
        currWidth = nextWidth;
        nextWidth = 0;
       
    }
}

}

void mmain(){
BTNode *T = NULL;
T = Create(T);

cout << "先序遍历:" << endl;
Preorder(T);
cout << endl;
/*
cout << "先序遍历非递归" << endl;
Preorder2(T);
cout << endl;

cout << "中序遍历:" << endl;
Inorder(T);
cout << endl;

cout << "中序遍历非递归:" << endl;
Inorder2(T);
cout << endl;

cout << "后序遍历:" << endl;
Postorder(T);
cout << endl;

cout << "后序遍历非递归:" << endl;
Postorder2(T);
cout << endl;

cout << "后序遍历非递归:" << endl;
Postorder3(T);
cout << endl;

cout << "层次遍历:" << endl;
Levelorder(T);
cout << endl;*/

printZigZag(T);

cout << endl;
system("pause");

}

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 196,099评论 5赞 462
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 82,473评论 2赞 373
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 143,229评论 0赞 325
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,570评论 1赞 267
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 61,427评论 5赞 358
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,335评论 1赞 273
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,737评论 3赞 386
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,392评论 0赞 254
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,693评论 1赞 294
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,730评论 2赞 312
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,512评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,349评论 3赞 314
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,750评论 3赞 299
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,017评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,290评论 1赞 251
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,706评论 2赞 342
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,904评论 2赞 335

推荐阅读更多精彩内容

  • LeetCode/LintCode ReviewPage 题解-总结
    背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪：刷leetcod...
    土汪阅读 12,712评论 0赞 33
  • Tree
    depth：n的depth为从root到n的路径的长度height：n的height为从n到一个leaf的最长路径...
    LonelyGod小黄老师阅读 309评论 0赞 0
  • LeetCode and LintCode: Binary Tree
    Validate Binary Search Tree Method: Traverse and Divide a...
    TQINJS阅读 584评论 0赞 0
  • Tree
    总结类型： 完全子树（#222） BST（左右子树值的性质，注意不仅要满足parent-child relatio...
    __小赤佬__阅读 671评论 0赞 0
  • Tree 小结
    以下是数据结构部分的主要知识点的思维导图 在这段时间基本上刷的都是跟二叉树有关的题目，所以下面主要针对二叉树部分进...
    衣忌破阅读 454评论 0赞 0