二叉樹的下一個節點

二叉樹的下一個節點

給定一個二叉樹和其中的一個節點,找出中序遍歷的下一個節點?

樹中的節點除了有左右孩子指針,還有指向父節點的指針

思路:

2. 如果一個節點沒有右子樹:

參考代碼:

#include <iostream>using namespace std;typedef struct BTNode{ int value; BTNode* left; BTNode* right; BTNode* parent;}BTNode;BTNode* getNext(BTNode* node){ if(node == NULL) return NULL; BTNode* next = NULL; if(node->right != NULL) { BTNode* pRight = node->right; while(pRight->left != NULL) { pRight = pRight->left; } next = pRight; } else if(node->parent != NULL) { BTNode* current = node; BTNode* pParent = node->parent; while(pParent != NULL && current == pParent->right) { current = pParent; pParent = pParent->parent; } next = pParent; } if(next) cout<<next->value<<endl; return next;}BTNode* creatPreTree(int* arr,int& i,int size){ BTNode* root = NULL; if(i < size && arr[i] != #) { root = (BTNode*)malloc(sizeof(BTNode)); root->left = NULL; root->right = NULL; root->parent = NULL; root->value = arr[i]; root->left = creatPreTree(arr,++i,size); if(root->left) root->left->parent = root; root->right = creatPreTree(arr,++i,size); if(root->right) root->right->parent = root; } return root;}void printTree(BTNode* root){ if(root == NULL) return; cout<< root->value<<" "; printTree(root->left); printTree(root->right);}int main(){int i = 0;BTNode* root = NULL;int arr[]={1,2,3,#,#,4,#,#,5,6,#,#,7,#,#};root = creatPreTree(arr,i,15);printTree(root);cout<<endl;getNext(root);return 0;}

推薦閱讀：