Tree

include<iostream>

include<stack>

include<queue>

include <list>

using namespace std;

/*
二叉樹(shù)定義
*/
typedef struct BTNode{
char data;

struct BTNode *lchild;
struct BTNode *rchild;

}BTNode;

/*
構(gòu)建二叉樹(shù)
*/
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();              //訪問(wèn)棧頂，判斷若有右節(jié)點(diǎn)則右節(jié)點(diǎn)進(jìn)棧，否則出棧。
    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);
        }
    }
}

}

/*

  • 求二叉樹(shù)的深度
    */
    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的節(jié)點(diǎn)是否存在
    */

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個(gè)節(jié)點(diǎn)的值
    */

void ShowK(BTNode T, int k) {
if (T != NULL) {
/ ++n; //定義全局變量n
if(n==k){
cout<<"第"<<k<<"個(gè)節(jié)點(diǎn)的值為: "<<T->data<<endl;
return;
}*/

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

}

/*

  • 求二叉樹(shù)的寬度
    */
    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;
    }

/*

  • 二叉樹(shù)第K層的節(jié)點(diǎn)個(gè)數(shù)
    */

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;

}

/*

  • 求葉子節(jié)點(diǎn)個(gè)數(shù)
    */

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;

}

/*
*前序和中序重建二叉樹(shù)
*/

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) {      //先序遍歷的第一個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)
        break;
    }
}
T->data = *pre;

T->lchild = RecreateByPI(pre + 1, in, i);      //i左邊遞歸建立左子樹(shù)
T->rchild = RecreateByPI(pre + i + 1, in + i + 1, nodeNum - 1 - i);    //i右邊遞歸建立右子樹(shù)
return T;

}

/*

  • 中序和后序重建樹(shù)
    */

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;

}

/*

  • 兩個(gè)節(jié)點(diǎn)的公共祖先
    */

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();       //在左樹(shù)沒(méi)找到,就彈出左樹(shù)元素
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;

}

/*

  • 求二叉樹(shù)節(jié)點(diǎn)的最大距離
    */

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;     //最大距離為左子樹(shù)最大高度,或者右子樹(shù)最大高度,或者左右深度之和

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

}

/*

  • 打印根節(jié)點(diǎn)到葉子節(jié)點(diǎn)路徑
    */
    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(); //記錄葉子節(jié)點(diǎn)路徑方法
    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 << " "; //打印棧或隊(duì)列元素,但不出棧
    it++;
    }
    cout << endl;
    }

      PrintRToL(T->lchild);
  PrintRToL(T->rchild);
  li.pop_back();           //第三次訪問(wèn)的時(shí)候,出棧,意味著此節(jié)點(diǎn)的左右子樹(shù)已經(jīng)遍歷完畢,包括葉子節(jié)點(diǎn)

    }
    }

/*
累加和為指定值的最長(zhǎng)路徑
*/
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");

}

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問(wèn)題, 分享了一些自己做題目的經(jīng)驗(yàn)。 張土汪：刷leetcod...
    土汪閱讀 12,931評(píng)論 0贊 33
  • depth：n的depth為從root到n的路徑的長(zhǎng)度height：n的height為從n到一個(gè)leaf的最長(zhǎng)路徑...
    LonelyGod小黃老師閱讀 349評(píng)論 0贊 0
  • Validate Binary Search Tree Method: Traverse and Divide a...
    TQINJS閱讀 691評(píng)論 0贊 0
  • 總結(jié)類(lèi)型： 完全子樹(shù)（#222） BST（左右子樹(shù)值的性質(zhì)，注意不僅要滿(mǎn)足parent-child relatio...
    __小赤佬__閱讀 779評(píng)論 0贊 0
  • 以下是數(shù)據(jù)結(jié)構(gòu)部分的主要知識(shí)點(diǎn)的思維導(dǎo)圖 在這段時(shí)間基本上刷的都是跟二叉樹(shù)有關(guān)的題目，所以下面主要針對(duì)二叉樹(shù)部分進(jìn)...
    衣忌破閱讀 527評(píng)論 0贊 0

友情鏈接更多精彩內(nèi)容