Problem:
　　在二叉樹中找到一個節(jié)點(diǎn)的后繼節(jié)點(diǎn)
　　【題目】 現(xiàn)在有一種新的二叉樹節(jié)點(diǎn)類型如下：
　　public class Node {
　　public int value;
　　public Node left;
　　public Node right;
　　public Node parent;
　　public Node(int data) { this.value = data; }
　　}
　　該結(jié)構(gòu)比普通二叉樹節(jié)點(diǎn)結(jié)構(gòu)多了一個指向父節(jié)點(diǎn)的parent指針。
　　假設(shè)有一 棵Node類型的節(jié)點(diǎn)組成的二叉樹，
　　樹中每個節(jié)點(diǎn)的parent指針都正確地指向自己的父節(jié)點(diǎn)，
　　頭節(jié)點(diǎn)的parent指向null。只給一個在二叉樹中的某個節(jié)點(diǎn) node，
　　請實(shí)現(xiàn)返回node的后繼節(jié)點(diǎn)的函數(shù)。在二叉樹的中序遍歷的序列中，
　　node的下一個節(jié)點(diǎn)叫作node的后繼節(jié)

Solution:
　　在中序遍歷的順序中，每一個節(jié)點(diǎn)的后一個節(jié)點(diǎn)即為該節(jié)點(diǎn)的后繼節(jié)點(diǎn)，
　　先驅(qū)節(jié)點(diǎn)即為中序順序的前面節(jié)點(diǎn)。

　　節(jié)點(diǎn)x的后繼節(jié)點(diǎn)為：
　　　　【若有右子樹】即為該節(jié)點(diǎn)的右子樹最左的節(jié)點(diǎn)
　　　　【若無右子樹】：
　　　　　　通過前驅(qū)指針，向上回溯父節(jié)點(diǎn)，并判斷該節(jié)點(diǎn)是否為該父節(jié)點(diǎn)的左子樹，
　　　　　　若是，則該父節(jié)點(diǎn)為該節(jié)點(diǎn)的后繼節(jié)點(diǎn)。不是，父節(jié)點(diǎn)繼續(xù)向上回溯其父。
　　　　　　若一直找不到，則該節(jié)點(diǎn)的后繼節(jié)點(diǎn)為空。

?

Code:

　　

1 #pragma once 2 #include <iostream> 3 #include <vector> 4 #include <queue> 5 6 using namespace std; 7 8 struct Node 9 { 10 int val; 11 Node* lchild; 12 Node* rchild; 13 Node* parent; 14 Node(int a = -1) :val(a), lchild(NULL), rchild(NULL),parent(NULL) {} 15 }; 16 17 void Create(Node*& root, vector<int>num)//層序構(gòu)造樹 18 { 19 queue<Node*>q; 20 root = new Node(num[0]); 21 q.push(root); 22 int i = 1; 23 while (i < num.size() && !q.empty()) 24 { 25 Node* p = q.front(); 26 q.pop(); 27 if (!p)//空節(jié)點(diǎn)p 28 break; 29 if (num[i] > 0) 30 { 31 p->lchild = new Node(num[i++]); 32 p->lchild->parent = p; 33 } 34 if (num[i] > 0) 35 { 36 p->rchild = new Node(num[i++]); 37 p->rchild->parent = p; 38 } 39 q.push(p->lchild); 40 q.push(p->rchild); 41 } 42 } 43 44 void MidTravel(Node *root) 45 { 46 if (!root) 47 return; 48 MidTravel(root->lchild); 49 cout << root->val << " "; 50 MidTravel(root->rchild); 51 } 52 53 Node* FindNode(Node* node) 54 { 55 if (node->rchild)//有右子樹，那么后繼節(jié)點(diǎn)即為右子樹的最左的節(jié)點(diǎn) 56 { 57 Node* p = node->rchild; 58 while (p->lchild) 59 p = p->lchild; 60 return p; 61 } 62 //無右子樹 63 //后繼節(jié)點(diǎn)為該節(jié)點(diǎn)為某個父節(jié)點(diǎn)的左子樹 64 Node *f;//父親指針 65 f = node->parent; 66 while (!f) 67 { 68 if (node == f->lchild) 69 return f; 70 node = f; 71 f = node->parent; 72 } 73 return NULL; 74 } 75 76 void Test() 77 { 78 Node* root = NULL; 79 vector<int>num = { 1,2,3,4,5,6,7,8,9,10,11,12,-1,-1,-1 }; 80 Create(root, num);//層序構(gòu)造樹 81 82 cout << "=============查看中序遍歷==============" << endl; 83 MidTravel(root); 84 cout << endl << endl; 85 86 Node* p = NULL; 87 p = root->rchild; 88 cout << "節(jié)點(diǎn) " << p->val << " 的后繼節(jié)點(diǎn)為："; 89 p = FindNode(p); 90 if (p) 91 cout << p->val << endl; 92 else 93 cout << "空。" << endl; 94 95 p = root->lchild->rchild; 96 cout << "節(jié)點(diǎn) " << p->val << " 的后繼節(jié)點(diǎn)為："; 97 p = FindNode(p); 98 if (p) 99 cout << p->val << endl; 100 else 101 cout << "空。" << endl; 102 103 p = root->rchild->rchild; 104 cout << "節(jié)點(diǎn) " << p->val << " 的后繼節(jié)點(diǎn)為："; 105 p = FindNode(p); 106 if (p) 107 cout << p->val << endl; 108 else 109 cout << "空。" << endl; 110 111 } 112

?

轉(zhuǎn)載于:https://www.cnblogs.com/zzw1024/p/10994766.html

總結(jié)

以上是生活随笔為你收集整理的左神算法基础班4_4_3在二叉树中找到一个节点的后继节点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。