树结构及其算法-用链表来实现二叉树

目录

树结构及其算法-用链表来实现二叉树

C++代码

树结构及其算法-用链表来实现二叉树

以链表实现二叉树就是使用链表来存储二叉树，也就是运用动态分配内存和指针的方式来建立二叉树。

使用链表来表示二叉树的好处是节点的增加与删除操作相当容易，缺点是很难找到父节点，除非在每一个节点多增加一个指向父节点的指针。

struct TreeNode {int data;TreeNode* leftNode;TreeNode* rightNode;TreeNode(int tempData, TreeNode* tempLeftNode = nullptr, TreeNode* tempRightNode = nullptr) {this->data = tempData;this->leftNode = tempLeftNode;this->rightNode = tempRightNode;}
};

C++代码

#include<iostream>
using namespace std;struct TreeNode {int data;TreeNode* leftNode;TreeNode* rightNode;TreeNode(int tempData, TreeNode* tempLeftNode = nullptr, TreeNode* tempRightNode = nullptr) {this->data = tempData;this->leftNode = tempLeftNode;this->rightNode = tempRightNode;}
};class Tree {
private:TreeNode* treeNode;
public:Tree() {treeNode = nullptr;}TreeNode* GetTreeNode() {return this->treeNode;}void AddNodeToTree(int* tempData, int tempSize) {for (int i = 0; i < tempSize; i++) {TreeNode* currentNode;TreeNode* newNode;int flag = 0;newNode = new TreeNode(tempData[i]);if (treeNode == nullptr)treeNode = newNode;else {currentNode = treeNode;while (!flag) {if (tempData[i] < currentNode->data) {if (currentNode->leftNode == nullptr) {currentNode->leftNode = newNode;flag = 1;}elsecurrentNode = currentNode->leftNode;}else {if (currentNode->rightNode == nullptr) {currentNode->rightNode = newNode;flag = 1;}elsecurrentNode = currentNode->rightNode;}}}}cout << "完成建立二叉树" << endl;}void Inorder(TreeNode* tempTree) {if (tempTree != nullptr) {Inorder(tempTree->leftNode);cout << tempTree->data << " ";Inorder(tempTree->rightNode);}}
};int main() {int data[]{ 6, 3, 5, 9, 7, 8, 4, 2 };cout << "原始数据：" << endl;for (int i = 0; i < 8; i++)cout << data[i] << " ";cout << endl;Tree* tree = new Tree;tree->AddNodeToTree(data, 8);tree->Inorder(tree->GetTreeNode());return 0;
}

输出结果