2 راه برای تحقق درخت باینری
1، روش پیوندی. مشابه یک لیست پیوندی، به جای ساختار داده های مرتبط فیزیکی، از پیوندهای منطقی توسط مراجع استفاده کنید
2، آرایه یک ساختار داده با پیوند فیزیکی است و ما می توانیم آن را در منطق نیز درک کنیم.
به عنوان مثال 
بنابراین اگر گره والد i باشد، فرزند سمت چپ i*2+1 و فرزند سمت راست i*2 + 2 خواهد بود.
و اگر درخت دودویی نباشد و درختی باشد که هر یک از والدین 3 فرزند داشته باشد. در این شرایط، اگر گره والد i باشد، فرزند از چپ به راست، فرزند اول i*3+1، فرزند دوم i*3+2، فرزند سوم i*3 +3 خواهد بود. و غیره.
و تشخیص درخت اولیه اولیه آسان است:
public class MyTree {
public class TreeNode {
public E val;
public TreeNode lefTNode;
public TreeNode rightNode;
public TreeNode() {
}
public TreeNode(E val){
this.val = val;
}
public TreeNode(E val, TreeNode leftNode, TreeNode rightNode) {
this.val = val;
this.lefTNode = leftNode;
this.rightNode = rightNode;
}
}
4 روش برای عبور از درخت باینری وجود دارد
1، پیش سفارش: وسط -> چپ -> راست
2، ترتیب: چپ -> وسط -> راست
3، Postorder: چپ -> راست -> وسط
4, Levelorder: ترتیب آرایه
با توجه به ریشه یک درخت باینری، پیمایش پیش سفارش مقادیر گره های آن را برگردانید.
مثال 1:
ورودی: ریشه = [1,null,2,3]خروجی: [1,2,3]
مثال 2:
ورودی: root = []خروجی: []
مثال 3:
ورودی: root = [1]خروجی: [1]
1.
public List preorderTraversal(TreeNode root) {
List list = new ArrayList<>();
if(root != null){
list.add(root.val);
if(root.left!=null){
list.addAll(preorderTraversal(root.left));
}
if(root.right!=null){
list.addAll(preorderTraversal(root.right));
}
}
return list;
}
2.
صفحه اصلی
public List inorderTraversal(TreeNode root) {
List list = new ArrayList<>();
if(root != null){
list.addAll(inorderTraversal(root.left));
list.add(root.val);
list.addAll(inorderTraversal(root.right));
}
return list;
}
صفحه اصلی
public List postorderTraversal(TreeNode root) {
List list = new ArrayList<>();
if(root != null){
list.addAll(postorderTraversal(root.left));
list.addAll(postorderTraversal(root.right));
list.add(root.val);
}
return list;
}
