树的链表表示

树的链表表示法

//二叉树的链表表示法
#include<iostream>
using namespace std;
//树的节点结构体
struct node {
  int data;
  node *left;
  node *right;
};
//头节点指针
node *head = NULL;
//建立节点
node *CreatNode(int k) {
  node *newnode = new node;
  newnode->data = k;
  newnode->left = NULL;
  newnode->right = NULL;
  return newnode;
}
//建树
void CreatTree(int k) {
  if (head == NULL) head = CreatNode(k);//头节点
  else {
    node *p = head;
    while (p != NULL) {
      if (k > p->data) {//右子树
        if (p->right == NULL) {
          p->right = CreatNode(k);
          break;
        }
        p = p->right;
      } else if (k <= p->data) {//左子树
        if (p->left == NULL) {
          p->left = CreatNode(k);
          break;
        }
        p = p->left;
      }
    }
  }
}
//递归打印树
void PrintTree(node *p) {
  if (p != NULL) {
    cout << p->data << " ";
    PrintTree(p->left);
    PrintTree(p->right);
  }
}
int main() {
  int k;
  while (cin >> k, k != -1) CreatTree(k);
  PrintTree(head);
}