美文网首页
Tree

Tree

作者: jmychou | 来源:发表于2016-11-02 22:46 被阅读10次

    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");

    }

    相关文章

      网友评论

          本文标题：Tree

          本文链接：https://www.haomeiwen.com/subject/aolbuttx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|Tree|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！